[알고리즘] selectionSort 선택정렬(pseudo-code, Java, 파이썬)

선택정렬

각 루프마다

1. 최대(최소) 원소를 찾는다

2. 최대(최소) 원소와 마지막(가장 앞에 있는) 원소를 교환한다

3. 마지막(가장 앞에 있는) 원소를 제외한다

– 하나의 원소만 남을 때까지 위의 루프를 반복

pseudo 코드

배열 끝에서부터 나머지 원소들 중 최대값과 교환하는 방식

Algorithm selectionSort(a,n)
    for i = n-1 down to 1
        //a[0]부터 a[i]까지 중 가장 큰 원소의 위치 index를 찾는다.
        index = 0
        for j = 1 to i
            if(a[index] < a[j]) then
            index = j
        //a[index]와 a[i]를 교환한다.
        int temp = a[index]
        a[index] = a[i]
        a[i] = temp

python 코드

배열 처음부터 나머지 원소들 중 최소값과 교환하는 방식

def selection_sort(arr):
    for i in range(len(arr)-1): #마지막원소는 이미 정렬되있음
        min_index = 0
        for j in range(i+1, len(arr)):
            if arr[i] > arr[min_index]:
                min_index = j
          arr[i], arr[min_index] = arr[min_index], arr[i]

Java 코드

배열 처음부터 나머지 원소들 중 최소값과 교환하는 방식

public class Selection{
    public void sort(int[] arr){
        int min_index;
        int temp;

        for(int i = 0; i < arr.length-1; i++){ //마지막 원소는 정렬되있음
            min_index = 0;
            for(int j = i+1; j < arr.length; j++){
                if(arr[i] > arr[min_index]){
                    min_index = j;
                }
            }
            temp = arr[i];
            arr[i] = arr[min_index];
            arr[min_index] = arr[i];
        }
    }
}

수행시간 분석

• 바깥 for문은 n-1 번 반복
• 안쪽 for문 비교횟수 n번
• 원소값 교환은 상수 시간

전체 원소 비교횟수:

n-1 + n-2 + ... + 2 + 1 = n(n-1)/2

시간복잡도 : n-1 + n-2 + …+ 2 + 1 = n(n-1)/2

T(n) = O(n^2)