[알고리즘] 선택 정렬(Selection Sort)

---

선택 정렬 기본

• 주어진 배열에서 최솟값을 찾아 정렬되지 않은 배열의 맨 앞의 값과 자리를 바꾸는 알고리즘
• 배열의 맨 앞부터 정렬이 완료됨

---

정렬 과정

과정 예시

13 28 23 25 19 : 최솟값 13 과 맨 앞의 값 28 스왑

13 19 23 25 28 : 다음 최솟값 19 와 맨 앞의 값 28 스왑

13 19 23 25 28 : 다음 최솟값은 23이므로 스왑 X

13 19 23 25 28 : 다음 최솟값은 25이므로 스왑 X

13 19 23 25 28 : 정렬 완료

---

시간 복잡도

• $O(N^2)$

---

구현

void selectionSort(int[] list) {
    int indexMin, temp;

    for (int i = 0; i < list.length - 1; i++) {
        indexMin = i;
        for (int j = i + 1; j < list.length; j++) {
            if (list[j] < list[indexMin]) {
                indexMin = j;
            }
        }
        // Swap
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    }
}

---