정렬 그림으로 개념정리(버블정렬, 교환정렬, 삽입정렬, 선택정렬, 쉘정렬, 힙정렬, 퀵정렬, 기수 정렬) - 자료구조, 컴퓨터 알고리즘
정렬(Sorting)?
- 리스트나 기록의 요소를 재배열 하는 것 .. 오름차순, 내림차순으로 정렬한다
- 정렬시에는 primary key, secondary key 를 이용하기도 함
왜인지 모르지만 정렬과 탐색은 항상 같이 배운다
** 아래의 예시들은 모두 왼→오 오름차순 정렬
1. 버블 정렬( Bubble Sort) = 교환 정렬( Exchange Sort)
이름 답게 하나씩 비교하면서 정렬을 하는 방식이다.
list[0]과list[1]과 비교 : list[1]이 크면 둘이 바꾸기
→ list[1]과 list[2] 비교 : list[2]가 크면 둘이 바꾸기
... continue
이걸 시작점~ 끝까지 한번 하는게 한 번의 수행
Best case(정렬이 이미 되어있는 상황)
: 정렬을 할 필요가 없으니까 비교연산만 n-1 번 => Θ(n)
Worst case(거꾸로 정렬되어있는 상황)
매번 비교연산을 n-1, n-2, n-3번 ... 해야하므로 => Θ(n^2)
Initialize n = Length of Array
BubbleSort(Array, n)
{
for i = 0 to n-2
{
for j = 0 to n-2
{
if Array[j] > Array[j+1]
{
swap(Array[j], Array[j+1])
}
}
}
}
2. 선택 정렬 (Selection Sort)
위의 예시를 참고하면 되는데 list에서 가장 큰 값(cmax)를 찾고 해당 값과 리스트의 마지막 값을 교환
(리스트의 마지막에 있던 요소는 원래 cmax의 위치로 가게 됨)
-> 한 번의 수행을 통해 하나의 요소가 정렬됨
다음 수행에서는 정렬 안된 요소(첫 cmax를 제외한 값들) 중 max값을 찾아서 cmax를 초기화
...continue
* 시간 복잡도
이 정렬의 경우 best case, worst case, average time complexity 모두 같다.
정렬 여부와 상관없이 비교를 반복하기 때문!
* 선택정렬 psuedo code
procedure selection sort
list : array of items
n : size of list
for i = 1 to n - 1
/* set current element as minimum*/
min = i
/* check the element to be minimum */
for j = i+1 to n
if list[j] < list[min] then
min = j;
end if
end for
/* swap the minimum element with the current element*/
if indexMin != i then
swap list[min] and list[i]
end if
end for
end procedure
3. 삽입 정렬(Insertion Sort)
정렬된 부분 // 정렬 안된 부분으로 나누어서 정렬하는 방식
앞(왼쪽)에서 부터 정렬 후 정렬 안된 부분의 요소를 순차적으로 정렬된 부분의 올바른 위치에 삽입한다
* 삽입 정렬 psuedo code
procedure insertionSort( A : array of items )
int holePosition
int valueToInsert
for i = 1 to length(A) inclusive do:
/* select value to be inserted */
valueToInsert = A[i]
holePosition = i
/*locate hole position for the element to be inserted */
while holePosition > 0 and A[holePosition-1] > valueToInsert do:
A[holePosition] = A[holePosition-1]
holePosition = holePosition -1
end while
/* insert the number at hole position */
A[holePosition] = valueToInsert
end for
end procedure
4. 쉘 정렬(Shell Sort)
요소들을 요소가 t개인 부분리스트로 나누어 각 리스트의 k번째 끼리 정렬하는 방식
Shell 정렬의 장점:
- 각 비교연산에 대해 inversion이 없으므로 시간복잡도가 Θ(n^2) 보다 좋을 것
procedure shellSort()
A : array of items
/* calculate interval*/
while interval < A.length /3 do:
interval = interval * 3 + 1
end while
while interval > 0 do:
for outer = interval; outer < A.length; outer ++ do:
/* select value to be inserted */
valueToInsert = A[outer]
inner = outer;
/삽입 정렬을 이용해 inner 번째 요소들 정렬/
/*shift element towards right*/
while inner > interval -1 && A[inner - interval] >= valueToInsert do:
A[inner] = A[inner - interval]
inner = inner - interval
end while
/* insert the number at hole position */
A[inner] = valueToInsert
end for
/* calculate interval*/
interval = (interval -1) /3;
end while
end procedure
5. 퀵 정렬(Quick Sort)
퀵 정렬은 특이하게 pivot값을 이용한다.
pivot 이란?
1. (회전하는 물체의 균형을 잡아 주는) 중심점[축] 2. (가장 중요한) 중심[중심축]
(출처: 네이버 영어사전)
설정한 pivot값을 기준으로
이 과정을 반복한다.
pivot값을 어떻게 설정하느냐의 방식으로는 2가지가 있는데
1) 가장 왼쪽 or 오른쪽 or 가운데 등 특정 위치를 기준으로 설정
2) 매 수행마다 리스트 내의 random 한 값을 기준으로 설정
* 퀵 정렬 psuedo code
<재귀적 방법>
function partitionFunc(left, right, pivot)
leftPointer = left
rightPointer = right - 1
while True do
while A[++leftPointer] < pivot do
//do-nothing
end while
while rightPointer > 0 && A[--rightPointer] > pivot do
//do-nothing
end while
if leftPointer >= rightPointer
break
else
swap leftPointer,rightPointer
end if
end while
swap leftPointer,right
return leftPointer
end function
procedure quickSort(left, right)
if right-left <= 0
return
else
pivot = A[right]
partition = partitionFunc(left, right, pivot)
quickSort(left,partition-1)
quickSort(partition+1,right)
end if
end procedure
6. 힙 정렬(Heap Sort)
힙정렬을 수행하려면 maxheap, minheap에 대한 개념이 필요하다.
간단하게 말하면 max heap의 각 노드는 자신의 자식 노드보다 값이 크거나 같은 완전 이진트리 이다.
힙 정렬의 과정
1. heap 만들기
2. heap 정렬하기
더 구체적으로 살펴보면
1. max heap을 만든다(Heapify) => 그럼 root에 제시된 요소들 중 max값이 존재
2. root와 heap의 마지막 요소를 swap
3. 기존의 root값( 즉, heap의 마지막 요소) 를 제외하고 heap을 재구성(Heapify)
4. 2,3의 과정을 반복한다.
해당 예시를 살펴보면 모든 노드는 각자의 자식 노드보다 크다 (maxheap이 이미 구성되어 있는 상태)
이제 위의 2,3 과정을 반복하는 것이다.
* 힙 정렬 psuedo code
Heapify(A as array, n as int, i as int)
{
max = i
leftchild = 2i + 1
rightchild = 2i + 2
if (leftchild <= n) and (A[i] < A[leftchild])
max = leftchild
else
max = i
if (rightchild <= n) and (A[max] > A[rightchild])
max = rightchild
if (max != i)
swap(A[i], A[max])
Heapify(A, n, max)
}
Heapsort(A as array)
{
n = length(A)
for i = n/2 downto 1
Heapify(A, n ,i)
for i = n downto 2
exchange A[1] with A[i]
A.heapsize = A.heapsize - 1
Heapify(A, i, 0)
}
7. 기수 정렬 (Radix sort)
이 정렬 방식에는 조건이 2개 있다.
1. 정렬하고자 하는 key 값들은 모두 음수가 아닌 정수로 진수가 통일되어 있어야 한다.
2. 모든 key 값은 같은 자리수여야 한다.
이 정렬 방식은 그냥 그림으로 보는게 쉽다
얘를 들어 3자리 수면
모든 key 값을 100의자리 "숫자" 기준으로 정렬
=> 10의 자리 "숫자" 기준으로 정렬
=> 1의 자리 "숫자" 기준으로 정렬
끝 이다.
* 기수 정렬 psuedo code
void radixsort{
for (i=1; i<=numdigits; i++){
distribute(i);
coalesce;
}
}
}
void distribute( index l){
for(j=0; j<=9;j++)
list[j]=NULL;
p= masterlist;
while(p!=NULL){
j=value of ith digit in p->key;
q=p;
p=p->link
link q to the end of list[j];
}
}
void coalesce(){
index j;
masterlist=NULL;
for (j=0;j<=9;j++)
link the node in list[j] to the end of masterlist
}
참고자료
이화여대 이상호 교수님 컴퓨터 알고리즘 수업자료
fullyunderstood.com/pseudocodes/heap-sort/
www.tutorialspoint.com/data_structures_algorithms/quick_sort_algorithm.htm
www.tutorialspoint.com/data_structures_algorithms/shell_sort_algorithm.htm
fullyunderstood.com/pseudocodes/bubble-sort/
www.tutorialspoint.com/data_structures_algorithms/selection_sort_algorithm.htm
www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm
www.geeksforgeeks.org/radix-sort/
Radix Sort - GeeksforGeeks
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
www.geeksforgeeks.org