[week 12] C++ 복습_7장 1차원 배열과 문자열 (2)

20211118_C++_공부기록

 

• 함수로부터 배열 반환
• 배열 정렬 - 선택 정렬
• 배열 탐색 - 선형 탐색 & 이진 탐색

---

• 함수로부터 배열 반환

C++에서는 함수에서 배열을 반환하는 것을 허용하지 않는다. 

해결책 : 두 개의 배열 인수를 전달하여 문제를 해결한다.

int[] reverse(const int list[], int size); //불가

#include <iostream>
using namespace std;

void reverse(const int list[], int newList[], int size)
{
    for (int i = 0, j = size - 1; i < size; i++, j--)
        newList[j] = list[i];
}

void printArray(int list[], int size)
{
    for (int i = 0; i < size; i++)
        cout << list[i] << " ";
}

int main()
{
    const int SIZE = 6;
    int list[] = { 1, 2, 3, 4, 5, 6 };
    int newList[SIZE]; //reverse를 넣을 빈배열 생성

    reverse(list, newList, SIZE);

    cout << "배열을 역순으로 출력하면: ";
    printArray(newList, SIZE);
    cout << endl;
    return 0;
}

---

• 배열 정렬_선택 정렬

1. 목록에서 가장 작은 수를 찾아 그 수와 제일 처음에 있는 수를 서로 교환

2. 그 다음, 남은 수들 중에서 가장 작은 수를 찾아 제일 앞에서 두 번째의 값과 교환

3. 이런 방법으로 목록에 단 한 개의 숫자만 남을 때까지 이 과정을 반복

 

선택 정렬

#include <iostream>
using namespace std;

void selectionSort(double[], int);
void printArray(const double list[], int arraySize);

int main()
{
	double list[] = { 2,9,5,4,8,1,6 };
	selectionSort(list, 7);
	printArray(list, 7);
	return 0;
}

void selectionSort(double list[], int size)
{
	for (int i = 0; i < size; i++)
	{
		double min = list[i];
		int minIndex = i;
		for (int j = i + 1; j < size; j++)
		{
			if (list[j] < min)
			{
				min = list[j];
				minIndex = j;
			}
		}

		if (minIndex != i)
		{
			list[minIndex] = list[i];
			list[i] = min;
		}
	}
}

void printArray(const double list[], int arraySize)
{
	for (int i = 0; i < arraySize; i++)
		cout << list[i] << " ";
}
//1 2 4 5 6 8 9

---

• 배열 탐색_선형 탐색

- 탐색(searching) : 배열에서 특정 요소를 찾는 작업

 

- 선형 탐색 : 찾는 값이 키(key)일 때, 이 키와 배열 내의 모든 요소를 연속적으로 비교하여 검색하는 방법

- 배열 요소와 키가 일치할 때까지 또는 일치되는 요소가 찾아지지 않은 채고 배열의 끝에 다다를 때까지 함수는 탐색을 계속한다.

#include <iostream>
using namespace std;

int linearSearch(int[], int, int);//리스트, 사이즈, 키값

int main()
{
	int list[] = { 1,4,4,2,5,-3,6,2 };
	int i = linearSearch(list, 8, 4); //1
	int j = linearSearch(list, 8, -4); //-1
	int k = linearSearch(list, 8, -3); //5

	cout << i << " " << j << " " << k << endl;
	return 0;
}

int linearSearch(int list[], int size, int key)
{
	for (int i = 0; i < size; i++)
	{
		if (list[i] == key)
			return i; //키와 일치하는 배열 요소의 인덱스 반환
	}
	return -1; //탐색 실패, -1반환
}

---

• 배열 탐색_이진 탐색

- 이진 탐색은 배열이 미리 정렬되어 있어야 한다. (오름차순 가정)

- 이진 탐색은 배열 중앙 요소와 키(key)를 비교하는 것으로 시작하여 다음 세 경우에 따라 검색해 나간다.

ü키가 중앙값보다 작다면, 배열의 앞쪽 절반에서 탐색을 계속

ü키가 중앙값과 같다면 원하는 키 값을 찾았으므로 탐색을 끝냄

ü키가 중앙값보다 크면, 배열의 뒤쪽 절반에서 탐색을 계속

탐색_이진 탐색

//이진 탐색
#include <iostream>
using namespace std;

int binarySearch(const int[], int, int); //리스트, 사이즈, key

int main()
{
	int list[] = { 2,4,7,10,11,45,50,59,60,66,69,70,79 };
	int i = binarySearch(list, 13, 2); //0
	int j = binarySearch(list, 13, 45); //5 
	int k = binarySearch(list, 13, 12); //-1

	cout << i << " " << j << " " << k << endl;
	return 0;
}

int binarySearch(const int list[], int size, int key)
{
	int low = 0;
	int high = size - 1;

	while (low <= high)
	{
		int mid = (low + high) / 2;
		if (key == list[mid])
			return mid; //인덱스값 반환
		else if (key < list[mid])
			high = mid - 1;
		else
			low = mid + 1;
	}
	return -1; //탐색에 실패하면 -1 반환
}