C++ Chapter 6.3 : 배열과 선택 정렬

 정렬  : 원소들끼리 서로 크기를 비교하여 원소들이 크기 순서대로 위치할 수 있도록 자리를 바꿔주는$($swap$)$ 작업.

오름차순으로 정렬하면 최소값이 맨 왼쪽에, 최대값이 맨 오른쪽에 위치하게 되며 크기 순서대로 나열된 형태가 된다.

/* 비교 */
n = 5 일때 
i = 0   와   j = 1 2 3 4    들 비교
i = 1   와   j = 2 3 4      들 비교
i = 2   와   j = 3 4        들 비교
i = 3   ->   j = 4

i는 0부터 시작해서 n-2 까지 (i = n - 1 일땐 뒤에 숫자가 남아있는게 없어서 비교할게 없다.)
j는 i + 1 부터 시작해서 n - 1까지

#include <iostream>

using namespace std;

void printArray(const int array[], const int length) 
// 배열 원소들을 출력할때 배열 길이도 알아야하므로 같이 넘겨준다. 값이 바뀔 일은 없으니 const
{
    for (int index = 0; index < length; ++index)
    cout << array[index] << " ";
    cout << endl;
}

int main()
{
    const int length = 5;

    int array[length] = { 3, 5, 2, 1, 4 };

    cout << "Your first value is: " << endl;

    printArray(array, length);

    for (int i = 0; i < length - 1; ++i)
    {
    	int smallestIndex = i;

    	for (int j = i + 1; j < length; ++j)
    	{
    		if (array[smallestIndex] > array[j])
    		{
   				smallestIndex = j; 
    		}
    	}

        // 작은 for문이 끝나면, 즉 해당 i와 비교된 j들 중 가장 작은 원소값의 인덱스가 smallestIndex에 저장된다.  
    	// 작은 for문이 끝난 후 인덱스가 smallestIndex인 원소와 인덱스가 i인 원소와 자리를 바꿔준다. 
        // 자연스레 가장 작은 값이 앞에 위치하게 된다. 
        int temp = array[smallestIndex];
        array[smallestIndex] = array[i]; 
        array[i] = temp;

        cout << "your array is: " << endl;
        printArray(array, length);
    }
    cout << "Now your array is: " << endl;
    printArray(array, length); // 정렬된  1 2 3 4 5 가 출력 될 것.

    return 0;
}

/* 정렬 과정 */

1. array[0]   과   array[1],array[2],array[3],array[4]    들 비교
smallestIndex = 3  (array[3] = 1 이 가장 작으므로)
array[0]과 array[3] 자리 바꾸기 
❤ {1, 5, 2, 3, 4}

2. array[1]   과   array[2],array[3],array[4]    들 비교
smallestIndex = 2  (array[2] = 2 이 가장 작으므로)
array[1]과 array[2] 자리 바꾸기 
❤ {1, 2, 5, 3, 4}

3. array[2]   과   array[3],array[4]    들 비교
smallestIndex = 3  (array[3] = 3 이 가장 작으므로)
array[2]과 array[3] 자리 바꾸기 
❤ {1, 2, 3, 5, 4}

4. array[3]   과   array[4]    들 비교
smallestIndex = 4  (array[4] = 4 이 가장 작으므로)
array[3]과 array[4] 자리 바꾸기 
❤ {1, 2, 3, 4, 5}

5. 최종 {1, 2, 3, 4, 5}