[Sort] 삽입 정렬(Insertion sort)

삽입 정렬(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  사이에 들어가야 겠죠???

이녀석은 

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

 

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

바로 복잡도랑 코드랑 

보도록 하죠 ㅜㅜ

 

---

 

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

Worst, Average

 

Best 일 경우만

 

입니다!!

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

InsertionMain.java

 

package Insertion;
 
public class InsertionMain {
    public static void main(String[] args) {
        int [] arr = {69, 10, 30, 2, 16};
        
        InsertionSort.insertionSort(arr);
    }
}
 

InsertionSort.java

 

 
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);
        }
    }
}
 

실행 결과 입니다.

 

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