정렬 알고리즘(2. 선택정렬)

선택정렬

개념

평균	최악	메모리	안정성
$O(N^2)$	$O(N^2)$	$O(1)$	X

선택은 하나를 고른다는 의미와 같습니다.
선택해서 정렬한다! 라는 의미로 이해하고 동작 과정을 살펴본다면 조금 더 이해하기 편할거에요.

선택 정렬은 주어진 범위에서 가장 작은 값 혹은 가장 큰 값을 선택하고 기준이 되는 인덱스와 바꿔가며 정렬을 진행하는 방식입니다.

동작 과정

1. 기준 인덱스(0)부터 끝까지 범위에서 가장 작은 값을 찾기(2)
2. 기준 인덱스와 해당 값 변경
3. 기준 인덱스 위치 증가
4. 인덱스를 순차적으로 증가시키며 해당 과정 반복

→ 해당 과정을 1회 통과마다 가장 작은 값이 가장 왼쪽에 배치됩니다.

즉, 가장 작은 값이 순회마다 왼쪽에 배치되며 매 순회마다 살펴보는 요소의 수는 1개씩 줄어들게 됩니다.(= 이미 최솟값으로 고정되기 때문)

선택 정렬의 시간 복잡도

선택 정렬은 총 N-1회의 반복을 진행합니다.
순회를 하며 방문하는 요소의 수는 N-1 → N-2 → ... 1 로 줄어들게 되는데 모든 항이 평균적으로 $\frac{N}{2}$ 만큼 방문하게 됩니다.
또, 원본 배열을 가지고 정렬을 진행하기때문에 별도의 메모리 소요는 없기때문에 공간복잡도는 $O(1)$이 됩니다.

이를 정리해보면 아래와 같습니다.

• 총 반복 횟수: N-1
• 평균 반복 요소 수: $\frac{N}{2}$
• 시간 복잡도: $O(\frac{N(N-1)}{2}) ⇒ O(N^2)$
• 공간복잡도: $O(1)$
• 안정성: ❌
  

정렬의 과정 중 같은 값이더라도 정렬의 순서가 달라지기때문에 안정성을 보장할 수 없습니다.

구현

void selectionSort(int[] arr) {
        int len = arr.length;

        for(int i = 0 ; i < len -1; i++){
            int minIdx = i;

            // findMinIdx
            for (int j = i+1; j < len; j++) {
                if(arr[j] < arr[minIdx]){
                    minIdx = j;
                }
            }

            // swap
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;

        }
    }

‼️주의
앞서 동작 과정을 봐서 알다시피 매 반복마다 방문하는 요소의 수는 1씩 줄어들게 되기때문에 len -1 이 아닌 len - i - 1이 되게 됩니다.

---

선택정렬은 버블 정렬과 다르게 정렬의 안정을 보장하지 못합니다.
이러한 특성은 객체를 비교할때 단점으로 작용하기 때문에 선택정려보다는 버블 정렬을 사용하도록하세효!🙂