지혜의 개발공부로그

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

Related Posts