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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://2ood.gitbook.io/2ood-knowledge-base/lecture-notes/algorithms/2023-09-04.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.