ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Sort] 삽입 정렬(Insertion sort)
    CSE/Sort 2015. 6. 12. 15:33

    삽입 정렬(Insertion Sort)





     


    [출처: 위키]



    정의:  자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 

    자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.



    정의는 위와 같습니다!!




    그림으로 보시죠!!



     





     


    정렬할 배열은 위와 같습니다.


    버블버블때 썼던 놈 그대로 합죠!!


     





    1단계:



     


    네. 1 단계는 맨 처음 요소가 부분 집합으로 꾸려져있죠??


    그리고 10  이란 놈이 부분 집합의 놈들과 비교를 해서 들어갈 자리를 물색 합니다...



    10 < 69 


    이므로...!



    아래 처럼 정렬이 됩니다!







    1단계 끝!!!










    2단계:


     


     



    이번엔 30을 저 안에서 비교를 하여, 

    30의 자리를 찾아야 합니다!


    30의 자리는 딱봐도 10과 69의 사이 겠죠???


    그래서 요 단계에서는


    먼저, 

    30 < 69 비교를 통해 자리를 한번 Check!


    그라고나서, 10 < 30을 통해 다시 Check 하여 자기 자리를 잡게 됩니다! 아래처럼!





     


    그럼 2단계 끝!!












    3단계:




     


    자 인제, 2를 부분 집합에서 정렬을 시켜야 합니다!



    2는 딱봐도 맨앞에 들어가야 겠죠???


    계속해서 비교를 통해 자기 자리를 찾는 겁니다.


    69...

    30...

    10...


    위 숫자들과 비교를 통해 자기자리를 찾는 거죠.




     



    이번 단계도 끝입니다!!


















    4단계:




      



    16을 마지막으로 정렬 해야 합니다!!


    16은 10과 30  사이에 들어가야 겠죠???








    이녀석은 


    결국 아래 자리에 들어가고 정렬이 끝나게 됩니다!!



     




    뭔가 너무 생략된 느낌이라 죄송스럽네용...


    바로 복잡도랑 코드랑 

    보도록 하죠 ㅜㅜ


    moon_special-20 









     




    이 삽입 정렬의 시간 복잡도(Time Complexity)는 아래와 같습니다!



    Worst, Average





     



    Best 일 경우만


     



    입니다!!






    그럼 소스 코드 보겠습니다!!!



    InsertionMain.java

     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    package Insertion;
     
    public class InsertionMain {
        public static void main(String[] args) {
            int [] arr = {691030216};
            
            InsertionSort.insertionSort(arr);
        }
    }
     
    cs



    InsertionSort.java

     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
     
    package Insertion;
     
    import Selection.SelectionSort;
     
    public class InsertionSort {
        public static void insertionSort(int[] arr) {
            for (int i = 1; i < arr.length; i++) {
                int tmp = arr[i];
                int aux = i - 1;
     
                while ((aux >= 0) && (arr[aux] > tmp)) {
                    arr[aux + 1] = arr[aux];
                    aux--;
                }
     
                arr[aux + 1] = tmp;
                System.out.println("삽입 정렬 " + i + "단계:");
                SelectionSort.printArr(arr);
            }
        }
    }
     
    cs






    실행 결과 입니다.




     



    이것으로 삽입 정렬 포스팅을 마치겠습니다!!


     


    'CSE > Sort' 카테고리의 다른 글

    [Sort] 기수 정렬(Radix Sort)  (0) 2015.06.12
    [Sort] 합병 정렬(Merge Sort)  (0) 2015.06.12
    [Sort] 셸 정렬(Shell Sort)  (0) 2015.06.12
    [Sort] 퀵 정렬(Quick sort)  (1) 2015.06.12
    [Sort] 버블 정렬(Bubble Sort)  (0) 2015.06.12
    [Sort] 선택 정렬(Selection Sort)  (0) 2015.06.12

    댓글

Designed by Tistory.