2023-09-04

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.