기본 정렬 - 선택 정렬(selection sort) 알고리즘

1. 선택 정렬 (Selection sort)

: 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와의 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행하게 된다.

• 제자리 정렬(in-place sorting) 알고리즘의 하나 - 정렬되지 않은 값들 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법이다.
• 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 다음 회전에서는 두 번째 자료를 가지고 비교한다. 

​

2. 예제

- 배열에 1, 6, 4, 5, 3 이 저장되어있다고 가정 -> 오름차순 정렬

 

1회전 :

​

2회전 :

3회전 :

​

4회전 :

결과 :

 

3. Java 선택정렬 예제

public class selectionSort {
    public static void main(String[] args) {
       
        int[] data = {3, 8, 6, 1, 5};
       
        //selection Sort
        int temp = 0 ; // 데이터 Swap용 임시변수
       
        for( int i = 0; i < data.length-1; i++){
            for (int j = i+1; j < data.length; j++){               
                if(data[i] > data[j]){ 
                                       
                    temp = data[i];
                    data[i] = data[j];
                    data[j] = temp;
                }
            }
            ShowArray(data); //현재 i번째 데이터 출력
        }
      
        System.out.println("/////////////selection sort 결과");
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i]+"  "); 
        }
       
    }
   
   // 각 회전때의 결과를 확인하기 위한 메소드
    private static void ShowArray(int[] data){
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i]+"  ");
        }
        System.out.println();
    }
}

 

4. 시간 복잡도

데이터의 개수를 n개라고 가정한다면,

첫 회전에서의 비교 횟수 : 1 ~ n -1 => n - 1 회

두 번째 회전에서의 비교 횟수 : 2 ~ n - 2 => n - 2 

즉, (n - 1) + (n - 2) + ...... + 2 + 1 => n(n - 1)/2가 되므로 O(n^2)만큼의 시간이 걸린다.