크레이지J의 탐구생활

정렬 알고리즘을 구현해 보고, 성능을 비교해 보자.
대략적으로 성능이 좋지 않은 순서대로 해 보겠다.

Selection Sort

복잡도: O(n^2)

아무 생각없이 바로 만들 수 있는 sorting 코드.
이중 루프를 돌면서 왼쪽부터 가장 작은 값을 찾아 넣음. (크면 바꾼다. swap 이것을 계속 반복하면 가장 작은 값이 index 0에 들어가게 된다.)
(일반적으로 성능 상관없이 정렬 작업할 때)

루프가 하나 끝나면 index 0가 최소값이 되고, 다음 루프로 index 1에 그 다음 작은 값이 들어가는 것을 반복한다.

-> 루프 0
index 0자리를 선택하여 나머지 전체에서 가장 작은 값을 넣고, (n-1번 비교)
index 0를 선택한 것을 index 1 부터 n-1까지 비교하면서 작은값이 있으면 swap. ; n-1인덱스에 가장 큰값이 이동됨.
-> 루프 1
index 1을 선택하여 그 다음 작은 값을 찾아 넣고. (n-2번 비교)
index 1을 선택한 것을 index 2부터 n-1까지 비교. ; n-2인덱스에 그 다음으로 큰 값이 이동됨.
...

ex)
loop i=0. j=1-4
5 1 9 3 4 : 인덱스 0, 1을 비교하여 대소위치 변경. swap
1 5 9 3 4 : 인덱스 0, 2를 비교하여 대소위치 변경
1 5 9 3 4 : 인덱스 0, 3를 비교하여 대소위치 변경
1 5 9 3 4 : 인덱스 0, 4를 비교하여 대소위치 변경
1 5 9 3 4 : 결과
인덱스0에 가장 작은 값 찾기 완료.
loop i=1. j=2-4
1 5 9 3 4 : 인덱스 1, 2을 비교하여 대소위치 변경
1 5 9 3 4 : 인덱스 1, 3를 비교하여 대소위치 변경 swap
1 3 9 5 4 : 인덱스 1, 4를 비교하여 대소위치 변경
1 3 9 5 4 : 결과
인덱스1에 2번째 작은 값 찾기 완료.
...
(왼쪽부터 위치를 하나 찍고 이후 나머지 것들과 모두 비교. 오른쪽으로 한 칸씩 이동)

void selection_sort(int arr[], int size) {
    for(int i = 0 ; i < size - 1 ; i++) 
        for (int j = i + 1 ; j < size ; j++) 
            if(arr[i] > arr[j]) {
                // swap(arr[i], arr[j]);
                int t = arr[i] ;
                arr[i] = arr[j] ;
                arr[j] = t ;
            }
}