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

---

선택 정렬(Selection Sort) 이란?

선택정렬은 가장 원리가 간단하면서 알고리즘의 효율로 봤을때 결코 좋은 알고리즘이로 볼 수 없다.(시간 복잡도로 본다면)

 

원리는 배열 원소에가 가장 큰/작은 수를 배열의 끝으로 보내는 작업을 계속 반복하는 것이다.

 

선택정렬에는 크게 2가지가 존재하고 정렬 목적에 따라 또 2가지로 나뉘게 된다.

---

최대 선택 정렬(오름차순) : 큰 수를 가장 오른쪽에 위치시키고 배열의 인덱스를 1씩 줄이는 방법

최대 선택 정렬(내림차순) : 작은 수를 가장 오른쪽에 위치시키고 배열의 인덱스를 1씩 줄이는 방법

최소 선택 정렬(오름차순) : 작은 수를 가장 왼쪽에 위치시키고 배열의 인덱스를 1씩 늘리는 방법

최소 선택 정렬(내림차순) : 큰 수를 가장 왼쪽에 위치시키고 배열의 인덱스를 1씩 늘리는 방법

---

이중 최대 선택 정렬 (오름차순)을 예로들어 설명한다면 A[n] 이라는 배열의 입력이 들어온다면 배열 A의 원소 1부터 n 까지의 수 중

가장 큰 수 A[k]를 잡아 제일 끝A[last]으로 보내고 배열 A의 두 번째 인덱스 까지 오게 하는 것이다.

 

이를 pseudo 코드로 보게된다면.

selectionSort(a[], n){                     ...1

    for last <- n downto 2{                ... 2
        A[1...last] 중 가장 큰 수를 찾고 A[k]라고 한다.        ... 3
        A[k] <-> A[last]; A[k]와 A[last]의 값을 교환.    ...4
    }
}

• 1: 이 알고리즘에서 입력 배열의 크기는 A[n]이다.

• 2: 선택정렬의 정렬 방식(가장 큰/작은 수를 기준으로)을 선택할 때 가장 큰 수 A[last]로 기준을 선택했기 때문에 배열의 반복은 배열의 크기 n 부터 배열의 크기가 하나씩 줄어드는 반복을 시작한다.

• 3: A[1...last] 중 가장 큰 수를 A[k]를 정하고 정렬을 할 준비를 한다.

• 4: 가장 큰 수 A[k]를 가장 마지막 인덱스로 보내고 다시 for문으로 가서 n의 수를 줄인다.

 

이 과정을 반복하고 last가 2 즉 A[2]가 된다면 A[1]과 비교하여 정렬을 하고 선택정렬을 마친다.

 

---

당연한 이야기겠지만 만약 위 pseudo 코드에 입력으로 A[1]이 들어왔다면 어떤 일이 일어날까?

for루프는 last가 n에서 시작해서 2까지 반복인데 last가 1으로 2보다 작다. 이 때는 for문을 한 번도 실행하지 않고 지나간다.

즉 A[1]로 정렬을 요구하면 아무 일도 하지 않고 끝나게 된다.

---

 

선택 정렬(Selection Sort)의 시간 복잡도

 

위의 pseudo 코드로 봤을 때 입력 배열 A[n]이면 (n은 입력의 크기)

 

for 반복

• 2. A[n] 부터 A[2]까지 총 n-1번 반복한다.
• 3. A[1...n] 중 가장 큰 수를 찾기 위해 총 n-1번의 반복이 필요하다.

 

교환

• 가장 큰 수 A[k]와 A[last]를 교환하는 것은 단순히 상수 시간이 든다.

 

결론: ∂[n^2]

Best	Avg	Worst
n^2	n^2	n^2

---

 

선택정렬의 특징

 

장점

• 구현하기 쉽다.
• 적은 양의 데이터에서 효과적이다.

단점

• 같은 레코드의 값 즉 수가 동일할 경우 안정된 정렬이 불가능하므로 안정성이 떨어진다.
• 데이터가 많아질 수록 효율성이 떨어진다.

---

선택 정렬(Selection Sort)의 자바 코드