삽입 정렬 - 오름차순 정렬

삽입 정렬(Insert Sort) 

알고리즘 중에서도 가장 기초가 되는 것이 바로 sorting입니다.

sorting은 정말 다양한 종류가 있습니다.  그 중에서도 가장 기초가 되는것이 Insertion Sorting 과 Bubble Sorting입니다.
Insertion Sorting (삽입정렬)의 가장 큰 특징은 KEY 값이라고 생각한다.  KEY값을 기준으로해서 그 전값과 비교를 해서 삽입을 해주는 식으로 정렬을 한다. 

[자바 소스 코드]

1.  
2. public class Main {
3.        
4.     public static void main(String[] args) {
5.         int data[] = { 74, 45, 25, 90, 12, 65, 24, 40, 9, 80 }; // 원본값을 배열로 설정
6.        
7.         System.out.println("정렬 이전 원 데이타 : ");
8.         System.out.println("----------------------------------------------------");
9.         printArray original_data = new printArray(data);
10.        
11.         InsertSort i = new InsertSort(data);
12.        
13.         System.out.println("-----------------------------------------------------");
14.         System.out.print("선택 정렬 후 데이타 : ");
15.         printArray sorted_data = new printArray(data);
16.     }
17. }
18.  
19. class printArray {
20.    
21.     public printArray(int arrayData[]){
22.         for(int i=0; i<arrayData.length; i++){
23.             System.out.print(arrayData[i] + " ");
24.         }
25.         System.out.println();
26.      }
27. }
28.  
29. class InsertSort {
30.    
31.     public InsertSort (int[] arrayData) {
32.         int data_position;
33.         int temp;
34.        
35.         for (int i=1; i<arrayData.length; i++) {
36.             data_position = i;
37.             temp = arrayData[i];
38.            
39.             while (data_position > 0) {
40.                 arrayData[data_position] = arrayData[data_position-1];
41.                
42.                 if (arrayData[data_position-1] < temp) {
43.                     break;
44.                 }
45.                 data_position--;
46.             }
47.             arrayData[data_position]=temp;
48.            
49.             System.out.print(i + "번째 선택 정렬 중 데이타 : ");
50.             printArray sorting_data = new printArray(arrayData);
51.         }
52.     }
53. }

[실행 결과]

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