선택 정렬(Selection Sort)

Sort

• 선택 정렬(Selection Sort)
• 버블 정렬(Bubble Sort)
• 삽입 정렬(Insertion Sort)

---

선택 정렬(Selection Sort)을 구현해 보았다.

void selection_sort(int arr[], int n)
{
    for(int i = 0 ; i < n-1 ; i++)
    {
        int minIndex = i;
        for(int j = i+1 ; j < n ; j++)
        {
            if(arr[j] < arr[minIndex]) minIndex = j;
        }
        if(minIndex != i) swap(arr[minIndex], arr[i]);
    }
}

마지막 원소인 n-1번째 원소는 자동 정렬되기 때문에 n-1전까지 반복해 주었다.

(i+1) ~ (n-1)번째 원소들 중 가장 작은 값을 찾아 i번째 원소와 교환한다.

이 때, 자기 자신이 가장 작은 원소일 경우 쓸데없는 작업을 줄이기 위해 교환을 하지 않는다.

---

4 5 3 2 4 1 배열이 주어졌을 때 첫 반복에서 최소값 1을 찾은다음 첫번째 원소인 4와 위치를 바꾸게 되면

앞에있던 4와 뒤에있는 4의 상대적인 위치가 처음 상태와 바뀌게 되어 Stable한 정렬이 되지 않는다.

4 5 3 2 4 1

1 5 3 2 4 4

---

1 2 3 4 4 5

→ 처음 상태와 비교했을 때, 빨간색 4와 파란색 4의 상대적 위치가 바뀌었다! (Stable하지 않다)

따라서 선택정렬을 Stable한 정렬이 되게 하려면 swap을 사용하지 않고 값들을 한 칸씩 뒤로 옮기는 작업이 필요하다.

4 5 3 2 4 1

1 4 5 3 2 4

---

1 2 3 4 4 5

→ 빨간색 4와 파란색 4의 상대적위치가 유지된채로 정렬되었다. (Stable하다)

Best Case	Worst Case	Average Case	Stable	Inplace
O(n^2)	O(n^2)	Ө(n^2)	???	Yes

 

---

삽입 정렬(Insertion Sort)

버블 정렬(Bubble Sort)