Skip to main content

Introduction

Summary introductions of several sorting algorithms and how they work

keywords divide and conquer, merge sort, quick sort.

TODO #todo : dividing logic pseudocode #todo : combining logic pseudocode #todo: look for the space complexity of merge sort

HW

Exercise draw the steps of sorting.

Next time

Divide and Conquer : recap

Divide, Conquer, combine

Merge sort

steps.​

  • Divide input array into two parts (usually in half)
  • merge sort right one.
  • merge sort left one.
  • combine right and left ones.

Input : Array and indices p,q,r #todo 1: dividing logic pseudocode #todo 2: combining logic pseudocode #todo 3: look for the space complexity of merge sort

Big-O analysis of merge sort​

On each depth, it needs $n$ times to combine. The number of depth is $log(n)$ so, the time complexity is $nlog(n)$

#todo 4: worst case data of merge sort.

Selection Sort

Set the first element as minimum.

steps.​

  • traverse through all array and find the minimum element.
  • When found, swap with the first position.
  • Next is minimum for second position.

#todo 5: pseudocode for selection sort.

Time complexity of selection sort.​

On each round, it needs $n$ times to find a minimum. there are $n$ rounds. so, the time complexity is $O(n^2)$.

#todo 6: worst case data of selection sort.

Quick Sort

find the right sorted pivot to divide. swap each side's anomaly until two iteration overlap.

divide and conquer

steps.​

  • partition
    • find a pivot position.
    • put smaller element on the left, put bigger element on the right.
    • sort each part.
    • put the pivot target in between.
  • quick sort each partition.

caution. There are a lot of variations of implementing quick sort.

pseudocode

5 2 4 7 1 3 2 6 이 있다. 5를 pivot 으로 설정한다. 좌측부터 5보다 작은지 본다. 7은 5보다 크다. 멈춘다. 우측부터 5보다 큰지 본다. 2는 5보다 작다. 멈춘다. 7과 2를 바꾼다.

좌측 이동을 다시 시작한다. ... 좌측 iteration 과 우측 iteration이 겹칠때까지 한다. 두 iteration이 지나가면 우리 pivot 과 바꾼다?

#todo 7 : pseudocode of quick sort.

Time complexity of Quick sort.​

Best case : $O(nlog(n))$

  • best case happens when partition happens at the right middle.
  • (pivot element is a median of the list)

Worst case : $O(n^2)$

  • worst case happens when data is already sorted.
  • it should check n times for all n data. #todo 8: worst case data of quick sort.

#todo 9: protocol to find what is the best suitable sorting algorithms. #todo 10: checklist of checking the sorting algorithm is seamless.

ways to avoid the worst case of quick sort

  • Dont' talways select the pivot as first element.
  • ...
  • #todo 11: write more.