[Algorithm] Sorting Problem - Insertion sort, Merge sort

1. Sorting Problem 이란?

 

• Input
  • n개의 숫자로 이루어진 sequence 
  • sequence를 이루는 각 요소를 KEY, 혹은 ITEM이라고 부름.
  • EX )  <5, 2, 9, 10, 1>
• OUTPUT
  • 주어진 조건에 따라 Input sequence를 재정렬한 sequence
  • EX ) <1, 2, 5, 9, 10>

 

2. Insersion Sort

 

Insertion Sort 란?
- Insertion 을 이용한 sorting algorithm

Insersion 이란?
- 새로운 KEY와 이미 정렬된 sorted list가 주어졌을 때, 정렬을 유지한 채 새로운 KEY를 list에 넣는 것.
- EX ) Insert "7" into <1, 2, 5, 9, 10>

 

Insertion sort는 Insertion 방법을 증가적으로 이용해서 정렬한다.

 

예를들어, <5, 2, 9, 10, 1>라는 정렬되지 않은 list A가 있다.

(1)  A[1]은 정렬되어 있을 테니 가만히 둔다.               =>   <5>
(2)  A[2]를 정렬된 A[1]에 Insertion한다.                      =>  <2, 5>
(3)  A[3]을 정렬된 A[1..2]에 Insertion 한다.                 =>  <2,  5,  9>
                                        ...
(N) A[n]을 정렬된 A[1...n-1]에 Insertion한다.              =>  <1, 2,  5,  9,  10>

 

3. Insertion sort 수도코드

 

 

4. Insertion sort 의 Performance

 

• Running Time
  • best : Θ(n)
  • worst : Θ(n^2) 
• Space Consumption
  • Θ(n)