기초적인 정렬알고리즘(3) - 삽입정렬

선택정렬, 버블정렬을 배웠고 그 다음으로 배우게되는 삽입정렬은 이전에 배운 선택,
버블정렬의 수행시간보다 훨씬 빠른 시간안에 정렬이 될 가능성이 높다.
그럼 한번 알아보자!

선택, 버블정렬은 가장 큰 값을 뒤로보낸다는 목적이 서로 비슷했었다. 이와 다르게 삽입정렬은 두번째 기준 원소부터 시작해서 3,4 ,5 ... N번째 를 기준으로 정렬이 이루어진다.
그리고 이 기준값보다 앞에있는 값들을 미리 정렬을 시켜주면서 N번째까지 정렬이 이루어 지며  정렬을 할때 그 기준값에 맞춰서 정렬이 된 곳에 삽입해주므로 삽입정렬이라고 하는의미를 잘 기억해두자.

쉽게 말해서 "비교할 원소는 정렬된 곳에 삽입하며 정렬이 이루어진다." 라고 말할 수 있다.

예를들어 보자...

삽입정렬 - 오름차순

A[6] = { 4, 5, 3, 8, 2, 7 }

1회 과정 

4, 5, 3, 8, 2, 7   =>  2번째 위치한 기준값 '5'를 그 앞들의 숫자들과 비교.   4 5 3 8 2 7가
된다.

    

2회 과정

4, 5, 3, 8, 2, 7   =>  3번째 위치한 기준값 '3'을 앞의 숫자 5와 비교해보면 3이  5보다 작고 4보다 작은 위치이므로 4 앞에 위치하면 되는것이다. 그래서 3 4 5 8 2 7 이 된다.

이런식으로 (정렬된)앞의 숫자들을 비교하며 기준원소는 알맞은 위치에 들어가면되므로,
다음과 같은 결과가 나온다.

3회 과정   :   3, 4, 5, 8, 2, 7  => 3 4 5 8 2 7

4회 과정   :   3, 4, 5, 8, 2, 7  => 2 3 4 5 8 7
5회 과정   :   2, 3, 4, 5, 8, 7  => 2 3 4 5 7 8   => 정렬 완료.

이 과정들을 보면 두번째 값을 기준원소로 시작으로 N까지의 기준을 정하는 루프와 앞의 정렬된 숫자들과의 비교를 하는 루프구조가 필요하다는것을 짐작할 수 있을것이다. 이러한 루프의 수행시간은 큰 값을 찾는경우(선택정렬)나 앞뒤 하나씩 끝까지 비교하는(버블정렬)과 비슷한 시간으로 Theta(n의 제곱)의 수행시간이 걸릴것이다.

알고리즘을 살펴보면,



▶실행결과