정렬 - 선택정렬

선택 정렬

선택 정렬은 첫 for문을 통해 기준 요소를 하나 지정한 뒤, 내부 for문으로 min 혹은 max 의 위치를 찾고, 기준 요소와 찾은 요소를 필요 시 swap 하는 형태이다.

버블 정렬과는 달리 swap 의 실행이 최대 n-1 번만 일어난다는 특징이 있다.

generateRandomArray, printArray, swap

static int arrayLength = 20;
int *myArray = generateRandomArray(arrayLength); // 랜덤으로 값이 초기화된 배열 생성

printArray(myArray, arrayLength); // 정렬 전 배열 출력

for (int i = 0; i < arrayLength; i++) { // 배열의 첫 번재 요소부터 뒤쪽으로 탐색하는데,
    int selectedLocation = i; // 최소 값의 초기화는 현재 위치의 값으로
    for (int j = i; j < arrayLength; j++) { // 현재 위치에서 뒤쪽으로 탐색하면서
        if (myArray[j] < myArray[selectedLocation]) selectedLocation = j; // 최소 값 위치 갱신
    }

    swap(&myArray[i], &myArray[selectedLocation]); // 현재 위치와 찾아낸 최소 값을 가진 위치를 변경한다
}

printArray(myArray, arrayLength); // 정렬 후 배열 출력

이 또한 오름차순으로 정렬한 예제이다.

2중 for문을 통해서 min 혹은 max 의 위치를 찾은 후, 내부 for문을 나와서 첫 번째 for 문에서 swap을 실행하는 것이 구조적 특징이다.

하지만 이 또한 2중 for문을 통해 min max 를 찾는 과정에서 O(N²) 의 복잡도를 가지게 된다.