자료구조 - Chapter 10

정렬(Sorting)

버블 정렬(Bubble Sort)

인접한 두 개의 데이터를 비교해 가면서 정렬을 진행하는 방식

두 데이터를 비교하여 정렬 순서상 위치가 바뀌어야 하는 경우에 두 데이터의 위치를 바꿔 간다.

두개의 세트로 움직인다고 생각하면 편하다.

 

예제 : 버블 정렬 구현하기

 

버블 쏘트 구현

ex10-1 BubbleSort.c

0.00MB

이중 for문을 이용하여 구현한다.

i는 단순히 마지막 원소를 밀어 넣는 개념이고 j는 이동하며 두개의 세트로 바꿔 나간다.

 

버블 정렬(Bubble sort) 성능 평가

• 비교의 횟수 : 두 데이터간의 비교 연산의 횟수
• 이동의 횟수 : 위치의 변경을 위한 데이터의 이동 횟수

빅오를 결정하는 기준은 비교의 횟수이다. 빅오 연산을 적용하면 O(n^2) 이다

 

선택 정렬(Selection Sort)

선택 정렬은 정렬 순서에 맞게 하나씩 선택해서 옮기는, 옮기면서 정렬이 되게하는 알고리즘

최소/최대를 찾아서 앞으로 가져온다고 생각하면 편하다.

 

예제 : 선택 정렬 구현하기

 

선택 정렬 구현

ex10-2 SelectSort.c

0.00MB

maxIdx 최소 / 최대 값을 찾는 변수를 두어 찾아서 정렬한다.

 

선택 정렬 성능 평가

비교 연산의 빅오는 O(n^2)으로 버블 정렬과 같지만, 이동 연산에 대한 빅오는 O(n)으로 버블 정렬보단 좋다.

 

십입 정렬(Insertion Sort)

 정렬 대상을 두 부분으로 나눠서, 정렬 안 된 부분에 있는 데이터를 정렬된 부분의 특정 위치에 삽입해 가면서

정렬을 진행하는 알고리즘

이동 값을 찾으면 하나씩 배열을 뒤로 밀어서 그 자리에 삽입한다고 생각하면 된다.

 

예제 : 삽입 정렬 구현하기

 

삽입 정렬 구현하기

ex10-3 InsertSort.c

0.00MB

삽입 정렬 성능 평가

선택 정렬과 동일하다.

 

힙 정렬(Heap Sort)

자료구조 힙을 통하여 정렬이 가능하다. 대신 힙의 루트 노드에 저장된 값이 가장 크거나 작아야한다.

 

예제 : 힙 정렬 구현하기

정렬시 배열에 루트 노드부터 단순히 꺼내기만 하면 된다.

힙 정렬 구현하기

ex10-4 HeapSort.c

0.00MB

UsefulHeap.c

0.00MB

UsefulHeap.h

0.00MB

힙 정렬 성능 평가

정렬 알고리즘 중 가장 좋은 성능을 보이는 알고리즘

• 힙의 데이터 저장 시간 복잡도 : O(log2N)
• 힙의 데이터 삭제 시간 복잡도 : O(log2N)

병합 정렬(Merge Sort)

병할 정렬은 분할 정복(divide and concuer) 알고리즘 디자인 기법에 근거하여 만들어진 정렬 방법

분할 정복하고 정복 후에 결합

• 1단계 분할(Divide) : 해결이 용이한 단계까지 문제를 분할해 나아간다.
• 2단계 정복(Conquer) : 해결이 용이한 단계까지 분할된 문제를 해결한다.
• 3단계 결합(Combine) : 분할해서 해결한 결과를 결합하여 마무리한다.

병합 정렬은 정렬 대상의 범위 정보를 전달한다.

 

예제 : 병합 정렬 구현하기

병합 정렬은 재귀를 통하여 실행한다. 재귀를 통해 분할하고 결합을 통해 재귀를 탈출해 반환한다.

 

병합 정렬 구현하기

ex10-5 MergeSort.c

0.00MB

병합 정렬 성능 평가

• 병합 정렬의 비교연산 빅오 : nlog(2N)
• 병합 정렬의 이동연산 빅오 : nlog(2N)

퀵 정렬(Quick Sort)

퀵 정렬도 병합 정렬과 마찬가지로 '분할 정복'에 근거하여 만들어진 정렬 방법

 

예제 : 퀵 정렬 구현하기

• left : 정렬 대상의 가장 왼쪽 지점을 가리키는 이름
• right : 정렬 대상의 가장 오른쪽 지점을 가리키는 이름
• pivot : 중심점, 중심축의 의미를 담고 있다.
• low : 피벗을 제외한 가장 왼쪽 위치에 지점을 가리키는 이름
• hight : 피벗을 제외한 가장 오른쪽 위치에 지점을 가리키는 이름

퀵정렬 구현하기

ex10-6 QuickSort.c

0.00MB

퀵 정렬 성능 평가

• 비교 연산 : O(nlog2N)
• 연산 횟수 : O(n^2)

기수 정렬(Radix Sort)

기수 정렬은 비교 연산을 진행하진 않는다.

버킷을 이용하여 데이터의 길이로 정렬을 시킨다.

 

또한 정수를 기수 정렬로 사용할 때, LSD 방식을 이용하여 적용한다.

자리수에 대하여 계쏙 버킷에 넣었다 빼는 형식으로 정렬을 진행한다.

 

예제 : 기수 정렬 구현하기

 

기수 정렬 구현하기

ex10-7 RadixSort.c

0.00MB

ListBaseQueue.c

0.00MB

ListBaseQueue.h

0.00MB