Data Structure, O(NlogN) Sorting
29 Feb 2020 | Data Structure개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
잘못된 부분이 있다면 댓글로 남겨주세요! :)
O(NlogN) Sorting
- Worst case O(N^2)
- Averabe case O(NlogN)
- with divided and conquer approch
- Divide the target sequence into multiple sequences
- Recursively perform sorting of the sub-sequences
- Problem is
- How to divide
- Variants
- Quick Sort
- Heap Sort
- Merge Sort
- Pros and Cons?
- 단점: bad division leads into O(N) time complexity
- 장점: relatively good time complexity
Merge Sort

def merge_sort(lst):
if len(lst) == 1:
return lst
sub_lst_sort1 = []
sub_lst_sort2 = []
# decomposition
for i in range(len(lst)):
if len(lst) / 2 > i:
sub_lst_sort1.append(lst[i])
else:
sub_lst_sort2.append(lst[i])
# recurstion
sub_lst_sort1 = merge_sort(sub_lst_sort1)
sub_lst_sort2 = merge_sort(sub_lst_sort2)
# aggreagtion
idx_count1, idx_count2 = 0, 0
for i in range(len(lst)):
print(f'{sub_lst_sort1} | {sub_lst_sort2}')
if idx_count1 == len(sub_lst_sort1):
lst[i] = sub_lst_sort2[idx_count2]
idx_count2 += 1
elif idx_count2 == len(sub_lst_sort2):
lst[i] = sub_lst_sort1[idx_count1]
idx_count1 += 1
elif sub_lst_sort1[idx_count1] > sub_lst_sort2[idx_count2]:
lst[i] = sub_lst_sort2[idx_count2]
idx_count2 += 1
else:
lst[i] = sub_lst_sort1[idx_count1]
idx_count1 += 1
print(lst)
return lst
Heap Sort

- Basic idea
- QuickSort(Sequence)
- Given a sequence
- Select a pivot
- Pivot = a threshold to divide the sequence into two sub-sequences
- Divide the sequence into two sub-sequences
- Sequence with values less than the pivot
- Sequence with values greater than the pivot
- Return
- QuickSort(sequence with less) + Pivot + QuickSort(sequence with greater)
- Merge sort forces to divide the sequence in the middle
- Always the similar size of the sub-sequence
- This divides the sequence with the pivot
Quick Sort

- Basic idea
- Given a sequence
- Select a pivot
- Pivot = a threshold to divide the sequence into two sub-sequences
- Divide the sequence into two sub-sequences
- Sequence with values less than the pivot
- Sequence with values greater than the pivot
- Return
- QuickSort(sequence with less) + Pivot + QuickSort(sequence with greater)
- Merge sort forces to divide the sequence in the middle
- Always the similar size of the sub-sequence
- This divides the sequence with the pivot selection
- Pivot 을 잘못 선택하는 경우 최악의 시나리오 O(N^2)
def quick_sort(seq, pivot = 0):
if len(seq) <= 1:
return seq
pivot_value = seq[pivot]
less_lst = []
grater_lst = []
for i in range(len(seq)):
if i == pivot:
continue
elif seq[i] > pivot_value:
grater_lst.append(seq[i])
elif seq[i] <= pivot_value:
less_lst.append(seq[i])
result = quick_sort(less_lst) + [pivot_value] + quick_sort(grater_lst)
return result