선택정렬(Selection Sort)

[아이디어]

1. 데이터의 정렬되지 않은 첫번째 원소부터 선형탐색으로 가장 작은 값을 찾아 인덱스를 기록합니다.
2. 1에서 찾은 인덱스를 사용하여 가장 작은 값과 정렬되지 않은 첫번째 원소를 서로 교환합니다.
3. 1 ~ 2를 모든 원소 개수 - 1 만큼 반복합니다.

[특징]

1. 평균 시간 복잡도는 O(n²)입니다.
2. 동일한 값이 두개 이상일 때 정렬 후 데이터 간 순서가 보장되지 않습니다.
3. 제자리 정렬 알고리즘으로 swapping을 위한 임시 저장 메모리 외에 추가적인 메모리를 필요로 하지 않아 공간 복잡도는 O(1)입니다.

 

 

[구현]

1. python

def selection_sort(data, reverse_order):
    for i in range(len(data) - 1):
        index = i
        for j in range(i + 1, len(data)):
            if data[j] < data[index] and not reverse_order:
                index = j
            if data[j] > data[index] and reverse_order:
                index = j
        if i != index:
            data[i], data[index] = data[index], data[i]


data = [3, 4, 1, 2]
print('not-sorted:', ', '.join(map(str, data)))
selection_sort(data, False) #reverse_order = False -> 오름차순 정렬
print('sorted:', ', '.join(map(str, data)))

 

2. java

public class Main {

    public static void main(String[] args) {
        int[] data = new int[] {3, 4, 1, 2};
        int len = data.length;
        System.out.print("not-sorted: ");
        for(int i = 0; i < len; i++) {
            if(i < len - 1) {
                System.out.print(data[i] + ", ");
            }
            else {
                System.out.println(data[i]);
            }
        }

        selectionSort(data, false);    //reverseOrder = false -> 오름차순 정렬

        System.out.print("sorted: ");
        for(int i = 0; i < len; i++) {
            if(i < len - 1) {
                System.out.print(data[i] + ", ");
            }
            else {
                System.out.println(data[i]);
            }
        }
    }
    public static void selectionSort(int[] data, boolean reverseOrder) {
        int len = data.length;
        for(int i = 0; i < len - 1; i++) {
            int index = i;
            for(int j = i + 1; j < len; j++) {
                if (data[j] < data[index] && !reverseOrder) {
                    index = j;
                }
                if (data[j] > data[index] && reverseOrder) {
                    index = j;
                }
            }
            if(i != index) {
                int temp = data[i];
                data[i] = data[index];
                data[index] = temp;
            }
        }
    }
}

 

위의 구현 코드를 실행하면 다음과 같은 순서로 동작합니다.

 

1. 리스트에서 아직 정렬되지 않은 첫번째 요소를 기준점으로 잡습니다.

 

2. 기준 인덱스 + 1  ~ 마지막 인덱스 사이의 값 중에서 기준 인덱스 값인 3보다 작은 값 중 최소값을 찾습니다.

3. 조건에 만족하는 최소값은 1이므로 기준 값 최소값을 swapping 합니다.

4. 이제 첫번째 원소가 정렬되었습니다.

5. 리스트에서 아직 정렬되지 않은 첫번째 요소를 기준점으로 잡습니다.

6. 기준점+1 ~ 마지막 인덱스 사이에서 기준점 보다 작은 최소값을 찾습니다.

7. 조건에 만족하는 값은 2이므로 기준값과 2를 swapping합니다.

8. 이제 두 번째 원소까지 정렬 되었습니다.

9. 리스트에서 아직 정렬되지 않은 첫번째 요소를 기준점으로 잡습니다.

10. 기준점+1 ~ 마지막 인덱스 사이에서 기준점 보다 작은 최소값을 찾습니다.

11. 조건에 만족하는 값인 3이 있으므로 기준값과 swapping 합니다.

12. 이제 세 번째 원소까지 정렬되었습니다.

13. 마지막 요소는 가장 큰 값이 남을 수 밖에 없어 별도로 정렬하지 않습니다.

이제 정렬이 완료되었습니다.