c언어로 쉽게 풀어쓴 자료구조 — 12장 정렬

12.1 정렬

정렬은 물건을 크기순으로 오름차순이나 내림차순으로 나열하는 것을 의미한다.

예를들어 책들을 제목순, 저자순, 발간연도순으로 정렬이 가능하고 사람은 나이나 키, 이름을 이용하여 정렬할 수 있다.

보통 정렬시킬 대상을 레코드라고 부르고 레코드는 필드라고 하는 단위로 나누어진다.

정렬 알고리즘

내부정렬은 크게 두가지로 나누어진다.

❶단순하지만 비효율적인 방법 : 삽입정렬, 선택정렬, 버블 정렬 등

❷복잡하지만 효율적인 방법 : 퀵 정렬, 히프 정렬, 합병 정렬, 기수 정렬 등

12.2 선택 정렬

선택정렬은 가장 이해하기 쉽다. 왼쪽 리스트와 오른쪽 리스트가 있다고 가정하면 초기상태에서 왼쪽 리스트에는 정렬이 완료된 숫자들이 들어가게 되고 오른쪽 리스트에는 정렬되지 않은 숫자들이 배치되는데 선택 정렬은 오른쪽 리스트가 공백상태가 될 때까지 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 작업을 되풀이하는 정렬 기법이다.

선택 정렬 알고리즘

가장작은 것을 선택해서 앞으로 보내는 알고리즘이다.

선택 정렬 복잡도 분석

비교횟수 : (n+1) + (n+2) + … + 1 = n(n-1) / 2 = O(n²)

이동횟수 : 3(n-1)

전체 시간의 복잡도 : O(n²)

12.3 삽입정렬

삽입정렬은 손안의 카드를 정렬하는 방법과 유사하다. 삽입정렬은 선택정렬과 유사하며 정렬되어 있는 리스트에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복한다.

삽입 정렬 알고리즘

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

삽입 정렬 복잡도 분석

비교횟수 : 1 + 2 + … + (n-1) = n(n-1) / 2 = O(n²)

이동횟수 : (n² + 3n -4) / 2 = O(n²)

전체 시간의 복잡도 : O(n²)

12.4 버블 정렬

버블정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 비교-교환 과정은 전체 숫자가 전부 정렬될 때까지 계속한다.

버블 정렬 알고리즘

버블 정렬 복잡도 분석

비교횟수 : n(n-1)/2 = O(n²)

이동횟수 : (최악일 때) 비교연산횟수 * 3

전체 시간의 복잡도 : O(n²)

12.5 쉘 정렬

삽입 정렬이 어느정도 정렬된 배열에 대해서는 대단히 빠른것에 착안한 방법이다.

삽입 정렬과는 다르게 전체의 리스트를 한번에 정렬하지 않고 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고 각 부분 리스트를 삽입정렬을 이용하여 정렬한다.

쉘 정렬 알고리즘

간격을 정해서 부분리스트 정렬을 오름차순이 될 때 까지 계속 반복한다.

쉘 정렬 복잡도 분석

전체 시간의 복잡도 : 최악의 경우 O(n²), 평균 O(n¹.5)

12.6 합병 정렬

합병정렬은 하나의 리스트를 분할정복 기법으로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것이다.

여기서 분할정복 기법은 문제를 2개의 문제로 분리하고 각각을 해결한 후 결과를 모아서 원래의 문제를 해결하는 전략이다.

합병 정렬 알고리즘

합병 정렬 복잡도 분석

전체 시간의 복잡도 : O(nlog2n)

12.7 퀵 정렬

퀵정렬은 평균적으로 매우 빠르고 분할-정복법에 근거한다. 합병정렬과 비슷하게 전체 리스트를 2개의 부분리스트로 분할하고, 각각의 부분 리스트를 다시 퀶정렬하는 전형적인 분할-정복법을 사용한다.

퀵 정렬 알고리즘

먼저 리스트 안에 있는 한 요소를 피벗으로 선택하고 피벗보다 작은 요소들은 피벗의 왼쪽으로 옮기고 피벗보다 큰 요소들은 피벗의 오른쪽으로 옮긴다. 이상태에서 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬된다.

퀵 정렬 복잡도 분석

전체 시간의 복잡도 : O(nlog2n)

12.8 히프 정렬

히프는 우선순위 큐를 완전 이진 트리로 구현하는 방법으로 히프는 최댓값이나 최솟값을 쉽게 추출할수 잇는 자료구조이다. 가장작은 원소부터 차례대로 추출하여 정렬하는 방법을 히프 정렬이라 한다.

12.9 정렬 알고리즘의 비교