Objective: Implement merge sort, quicksort, heapsort and evaluate the performance in the worst and average case.
목적: mergesort, quicksort, heapsort를 직접 구현하고 최악의 경우와 일반적인 경우에 시간효율성을 계산하고 이를 분석한다.
Language(언어): Python3
1. Sorting in the Average case (일반적인 상황에서의 time complexity)
- Input data were randomly arranged before sorting function
In the average case, the time complexities of the above sorting algorithms are all n*log(n). However, quick-sort is the fastest algorithm in average case among them, and heap sort was slowest.
Further study
In the heap-sort case, it is not faster than quicksort, but if there is new input data, heap sort can sort it by using max-heapify which takes only log(n).
In the merge-sort case, It is not faster than quicksort, but if there is too big data that cannot be sorted in several times, the merge sort can have an advantage because it uses divide-conquer-combine process.
In the quick-sort case, it is much faster than others in the average case, but if there is too small data, the cost of function call recursively can be inefficient.
일반적인 케이스에는 모두 시간복잡도가 n*log(n)으로 나타났다. 하지만 그 중에서도 quick-sort가 가장 빠른 것으로 나왔고, heap-sort가 가장 느렸다.
Heapsort의 경우, quicksort보다 빠르진 않지만, max-heapify(아래 알고리즘 참고)를 통해 새로 추가된 input이 있으면 log(n)시간 만에 정렬이 가능하다.
Mergesort의 경우, quicksort보다 빠르진 않지만, 매우 큰 데이터가 있어서 반드시 몇 단계로 나눠서 정렬을 해야하는 경우가 있을 수 있는데, 그럴 경우 merge-sort가 divide-conquer-combine process(분할 병합과정)을 거치기 때문에 더욱 유리할 수 있다.
Quicksort의 경우, 매우 빠른 것으로 나왔지만, 데이터 수가 작을 경우에는 재귀함수를 호출하는 것이 비효율적일 수 있다.
2. Sorting in the worst case (최악의 경우 분석)
Input data were arranged as worst-case (sorted as descending order) (input data가 내림차순으로 정렬되어있을 때)
In the worst case, the time complexity of quick-sort is n^(2) and merge-sort and heap-sort take n*log(n). Consequently, as the number of input increases, the time complexity of quick-sort increases rapidly compared to the heap and merge sort. It is because pivot will divide data inefficiently like (1, n-1). Otherwise, the time-complexity of the heap and merge sort is quite similar to the running time in the average case.
To sum up, if new data is randomly arranged, quick-sort can be an efficient algorithm in running time. However, if input data is unknown or if there is some possibility it is arranged as a descending order, selecting a quick-sort algorithm can be risky.
Consequently, before selecting a sorting algorithm, people need to consider the information of data and the objective of sorting.
최악의 경우에는, 시간복잡도가 각각 quicksort는 n^(2), mergesort와 heapsort는 각각 n*log(n)으로 나왔다.
결과적으로 인풋의 수가 많아질수록 quicksort의 시간보잡도는 급격히 늘어갔다. 왜냐하면 계속해서 quicksort의 pivot이 데이터를 (1,n-1)로 비효율적으로 나누게 되기 때문이다. 반면에 heapsort와 mergesort의 경우는 average case와 비슷한 퍼포먼스를 보였다.
결론적으로, 입력데이터가 랜덤하게 정렬되어 있다면, quicksort가 가장 시간적인 측면에서 효율적일 수 있지만, 데이터를 잘 모르거나 반대로 정렬되어있을 가능성이 있다면 quicksort의 선택은 위험할 수도 있다.
따라서 알고리즘을 선택하기 이전에 데이터의 특성을 충분히 고려하여야 한다.
Mergesort Algorithm
def Merge(A,p,q,r):
n1 = q-p+1
n2 = r-q
L=[]
R=[]
for i in range(0,n1+1):
L.append(i)
for j in range(0,n2+1):
R.append(j)
for i in range(0,n1):
L[i] = A[p+i]
for j in range(0,n2):
R[j] = A[q+j+1]
L[n1] = float('inf')
R[n2] = float('inf')
i=0
j=0
for k in range(p,r+1):
if L[i] <= R[j]:
A[k] = L[i]
i = i+1
else:
A[k] = R[j]
j = j+1
def MergeSort(A,p,r):
if p<r:
q = (p+r)//2
MergeSort(A,p,q)
MergeSort(A,q+1,r)
Merge(A,p,q,r)
Heapsort Algorithm
def parent(i):
return(i//2)
def left(i):
return(2*i+1)
def right(i):
return(2*i+2)
def Max_Heapify(A,i):
l = left(i)
r = right(i)
if l <= len(A)-1 and A[l] < A[i]:
smallest = l
else:
smallest = i
if r <= len(A)-1 and A[r] < A[smallest]:
smallest = r
if smallest != i:
temp = A[i]
A[i] = A[smallest]
A[smallest] = temp
Max_Heapify(A,smallest)
def Build_Max_Heap(A):
for i in range((len(A)//2),-1,-1):
Max_Heapify(A,i)
def HeapSort(A):
Build_Max_Heap(A)
for _ in range(0,len(A)-1):
Answer.append(A[0])
A[0] = A[len(A)-1]
A.pop()
Max_Heapify(A,0)
Answer.append(A[0])
Quicksort Algorithm
def QuickSort(A,p,r):
if p<r:
q = partition(A,p,r)
QuickSort(A,p,q-1)
QuickSort(A,q+1,r)
def partition(A,p,r):
x = A[r]
i = p-1
for j in range(p,r):
if A[j] <= x:
i = i+1
temp = A[i]
A[i] = A[j]
A[j] = temp
temp = A[i+1]
A[i+1] = A[r]
A[r] = temp
return i+1If you have any questions, feel free to leave a comment.
Cheers :)