[Data Structure] 9. 정렬

이 카테고리에 정리된 내용은 강의시간에 필기한 내용이 주를 이룹니다. 교수님께서 강의 하신 내용들 중에 핵심들과 부가적인 내용들을 요약하여 게시했습니다. 강의시간에 생능출판사의 C언어로 쉽게 풀어쓴 자료구조 책을 사용했기 때문에 정리하는 순서도 이 책의 순서에 따라 하기로 했습니다. 순전히 정리용이기 때문에 시험기간이나 복습용으로는 적절하지만 순수한 학습용으로는 적절하지 않을 수 있습니다.

목록보기

 

9.1 정렬

– 정렬 (sorting) : 크기순으로 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것.

– record : 정렬될 대상. 레코드의 삽입될 각각의 데이터 범주를 field라 하고, 그 필드 중 레코드와 레코드를 식별해주는 역할을 하는 필드를 key라고 함.

– 단순/비효율 방법 : 삽입정렬, 선택정렬, 버블정렬 등

– 복잡/효율 방법 : 퀵정렬, 힙정렬, 합병정렬, 기수정렬 등

– 안정성(stability) : 입력 데이터에 동일한 키 값을 갖는 레코드가 여러 개 존재할 경우, 이들 레코드들의 상대적인 위치가 정렬 후에도 바뀌지 않는 것.

 

9.2 선택정렬

– 선택정렬(selection sort) : 가장 이해하기 쉬운 정렬 방법. 정렬되지 않은 리스트에서 가장 작은/큰 값을 찾아 빈 리스트에 차례로 이동시키는 것.

 

9.3 삽입정렬

– 삽입정렬(insertion sort) : 손안의 카드를 정렬하는 방법과 유사. 새로운 데이터를 기존의 정렬된 리스트 사이의 올바른 자리를 찾아 삽입.

 

9.4 버블정렬

– 버블정렬(bubble sort) :  인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환하는 비교-교환과정을 반복해서 진행.

 

9.5 쉘정렬

– 쉘정렬(shell sort) : 삽입정렬이 어느 정도 진행된 리스트에 대해서는 대단히 빠르다는 것에 착안한 방법. 전체리스트를 한번에 정렬하지 않고, 먼저 정렬해야할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입정렬을 이용하여 정렬. 모든 부분 리스트가 정렬되면 쉘정렬은 다시 전체의 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 되풀이.

 

9.6 합병정렬

– 합병정렬(merge sort) : 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할 부분을 정렬한 후, 두 개의 정렬된 리스트를 합하여 전체가 정렬된 리스트를 얻고자 함.

– 분할정복(divide and conquer) : 합병정렬에서 분할하고 정렬하고 결합하는 과정을 나타낸 기법.

 

9.7 퀵정렬

– 퀵정렬 (quick sort) : 평균적으로 매우 빠른 속도. 퀵정렬도 분할정복에 근거함. 합병정렬과는 달리 피벗(pivot)을 이용하여 비균등하게 분할. 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. 결과적으로 피벗을 중심으로 왼쪽은 피벗보다 작은 요소들로 구성되고, 오른쪽은 피벗보다 큰 요소들로 구성되게 된다. 이 상태에서 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하면 정렬 완료. 단, 레코드가 13개 이하이면 기본 소트가 더 효율적이다.

 

9.8 힙정렬

– 힙정렬(heap sort) : 최소히프를 기준으로, 부모노드의 값이 자식 노드의 값보다 작고, 루트는 가장 작은 값을 가지게 된다.

 

9.9 기수정렬

– 기수(radix) : 자릿수

– 기수정렬(radix sort) : 입력 데이터에 대해 어떤 비교연산도 하지 않고 정렬이 가능한 기법. 추가 메모리가 필요. 레코드가 한정되어있다고 확신할 수 잇을 때, 각각의 레코드를 특정 범주 버킷(bucket)을 만들어 삽입.

 

9.10 정렬알고리즘 비교

– 정렬 알고리즘의 비교

알고리즘 / 최선 / 평균 / 최악

삽입 / O(n) / O(n^2) / O(n^2)

선택 /  O(n^2) / O(n^2) / O(n^2)

버블 / O(n^2) / O(n^2) / O(n^2)

쉘 / O(n) / O(n^1.5) / O(n^1.5)

퀵 / O(nlog2n) / O(nlog2n) / O(n^2)

힙 /O(nlog2n) /O(nlog2n) /O(nlog2n)

합병 /O(nlog2n) /O(nlog2n) /O(nlog2n)

기수 / O(dn) /O(dn) /O(dn)

 

목록보기