알고리즘 3장 - 정렬 문제 : 삽입 정렬 -

알고리즘 3장

- 정렬 문제 : 삽입 정렬 -

 

정렬 문제는 n개의 숫자들의 배열을 입력으로 받게 되면 입력된 숫자의 배열이 특정 조건을 만족하도록 다시 나열한 결과를 출력으로 나타내는 문제이다. 이번 장에서는 정렬 문제 중에서 삽입 정렬에 대해서 학습할 것이다.

삽입 정렬은 말 그대로 삽입을 이용한 정렬 알고리즘이다. 삽입이라는 것은 어떤 대상을 다른 대상 사이에 넣는다는 말로 어떤 값을 어디에 삽입할 것인가라는 점이 매우 중요하게 된다. Key 값과 정렬된 리스트가 주어졌을 때, key 값을 정렬된 리스트의 알맞은 위치에 삽입을 해야 하는 문제이다. 예를 들어 key 값이 3이고 정렬된 배열이 <1, 2, 4, 5, 6>일 때 키를 알맞은 위치에 삽입한 배열은 <1, 2, 3, 4, 5, 6>으로 정렬이 될 수 있다.

삽입 정렬의 방법은 key 값을 하나씩 추가하면서 정렬을 하는 방식이다. A이라는 배열이 존재한다면 첫 번째는 A[2]을 정렬된 배열 A[1]에 집어넣는다. 두 번째는 A[3]을 정렬된 배열 A[1..2]에 집어넣는다. 계속 되는 과정으로 N-1번째는 A[n]을 정렬된 배열 A[1..n-1]에 집어넣는다. 위와 같이 배열 A에 원소를 하나씩 추가하면서 정렬을 하게 된다.

예시를 통해 알아보게 되면 <5, 2, 4, 6, 1, 3>이라는 배열이 주어진다고 생각을 해보자. 여기에서 삽입 정렬을 통해 오름차순으로 정렬을 할 것이다. 처음에 2가 key 값이 되어 앞에 나온 5와 2를 비교하여 2가 더 작은 숫자이므로 순서가 바뀌어 정렬된다. <2, 5, 4, 6, 1, 3>의 형태로 나타나게 되는데 이 후에는 4가 key 값으로 된다. 4가 5랑 비교를 하게 되고 작은 값이므로 앞으로 이동하게 되고 2랑 비교하여 큰 값이므로 뒤에 위치하게 되어 <2, 4, 5, 6, 1, 3>으로 바뀌게 된다. 이후에는 key 값이 6으로 되고 5보다 크므로 그대로 넘어가게 된다. 이후 1이 key 값이 되고 1을 앞의 값들과 계속 비교하여 가장 앞에 위치하게 된다. 이런 과정을 거쳐 <1, 2, 3, 4, 5, 6>으로 정렬이 완성된다.

간단한 코드의 형식을 보게 되면 다음과 같다. A라는 배열의 길이만큼 돌게 되는데 시작이 두 번째 배열의 값부터 진행하게 된다. 이 때 각각의 값을 넘어가면서 key 값으로 지정되게 되고 그 값이 더 크면 앞의 값과 바꾸는 과정을 반복하게 된다.

성능 분석을 통해 알고리즘을 판단할 수 있는데 수행 시간이 반복문에 의해 다른 값을 가질 수 있게 된다. 반복문이 key 값과 앞의 값을 비교하는 연산을 진행하는데 작은 값을 가져서 앞의 많은 값들과 비교하게 되면 연산을 많이 하게 되지만 만약 큰 값을 가지고 있다면 연산을 바로 빠져나와 진행을 하지 않아도 되므로 이에 따라 수행 시간이 다르게 된다.