> For the complete documentation index, see [llms.txt](https://2ood.gitbook.io/2ood-knowledge-base/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://2ood.gitbook.io/2ood-knowledge-base/lecture-notes/algorithms/2023-09-04.md).

# 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.