선택 정렬 - 오름 차순 정렬

선택 정렬(Selection Sort)은 정렬되지 않은 데이터 중에서 가장 작은 데이터를 찾아 가장 앞의 데이터와 순차적으로 교환해나가는 알고리즘입니다.

전체 데이터가 n개이면, 데이터 교체가 일어나는 회수는 최대 n-1번이며, 전체 비교 회수는 n(n-1)/2번입니다. 따라서 계산 시간복잡도는 O(n^2)입니다.

[알고리즘]

1. 첫 번째 위치로 있을 가장 낮은 값을 찾기 위해서
2.  두 번째부터 끝까지 차례로 낮은 값인지를 비교하여 첫 번째 값을 결정합니다.
3.  그 과정에서 현재 위치의 값보다 작은 값을 만나면(비교대상 값 < 현 위치 값) 서로 교환 해줍니다.
4.  
5. 그 후 두 번째로 낮은 수를 찾기 위해서
6.  세 번째부터 마지막까지 현재 두 번째 자리의 수보다 낮은 값이 있는지 확인합니다.
7.  마찬가지로 작은 값을 만나서 서로 값을 교환 해줍니다.
8.  
9. 그렇게 ... 마지막 위치까지 교환을 하면 
10. 최종적으로 오름차순으로 정렬된 결과를 얻게 됩니다. 

[자바 소스코드]

1. public class SelectionSort {
2.    
3.     public static void main(String[] args) {
4.         int data[] = { 74, 45, 25, 90, 12, 65, 24, 40, 9, 80 }; // 원본값을 배열로 설정
5.         int temp;
6.         int indexMin;
7.  
8.         System.out.print("정렬 이전 원 데이타 : ");
9.         printArray(data);
10.         System.out.println("----------------------------------------------------");
11.  
12.         for(int i=0; i < data.length - 1; i++){ // 기준위치를 0~n-2 까지하고
13.             indexMin = i;
14.             for(int j=i+1; j < data.length; j++){// 비교할 값 위치는 기준위치+1 ~ n-1까지로 하여 최소값을 찾음
15.                 if(data[j] < data[indexMin]){
16.                     indexMin = j;
17.                 }
18.             }
19.             temp = data[indexMin];
20.             data[indexMin] = data[i];
21.             data[i] = temp;
22.            
23.             System.out.print(i+1 + "번째 선택 정렬 중 데이타 : ");
24.             printArray(data);
25.        }
26.      
27.        System.out.println("-----------------------------------------------------");
28.        System.out.print("선택 정렬 후 데이타 : ");
29.        printArray(data);
30.     }
31.    
32.     static void printArray(int data[]){
33.        for(int i=0; i<data.length; i++){
34.            System.out.print(data[i] + " ");
35.        }
36.        System.out.println();
37.     }
38. }

[실행 결과]

 - for 루프가 진행되는 과정을 보면 소팅 결과를 보다 명확하게 이해 할 수 있습니다. 

1. 정렬 이전 원 데이타 : 74 45 25 90 12 65 24 40 9 80
2. ----------------------------------------------------
3. 1번째 선택 정렬 중 데이타 : 9 45 25 90 12 65 24 40 74 80
4. 2번째 선택 정렬 중 데이타 : 9 12 25 90 45 65 24 40 74 80
5. 3번째 선택 정렬 중 데이타 : 9 12 24 90 45 65 25 40 74 80
6. 4번째 선택 정렬 중 데이타 : 9 12 24 25 45 65 90 40 74 80
7. 5번째 선택 정렬 중 데이타 : 9 12 24 25 40 65 90 45 74 80
8. 6번째 선택 정렬 중 데이타 : 9 12 24 25 40 45 90 65 74 80
9. 7번째 선택 정렬 중 데이타 : 9 12 24 25 40 45 65 90 74 80
10. 8번째 선택 정렬 중 데이타 : 9 12 24 25 40 45 65 74 90 80
11. 9번째 선택 정렬 중 데이타 : 9 12 24 25 40 45 65 74 80 90
12. -----------------------------------------------------
13. 선택 정렬 후 데이타 : 9 12 24 25 40 45 65 74 80 90