[Lecture Summary] 03 Algorithm and Data Structure : Sorting

This contents is based on Lecture of link

Overview

Notation

• Permutation: array with same elements in a different order
• Sorting: $B[i-1] \le B[i]$

Type

• destructive sort = overwrites the original array
• inplace = destructive + do not use extra memory(uses $O(1)$ extra space!)

I/O

• Input : (Static) array $A$ of size $n$
• Output : (Static) sorted array $B$ being sorted permutation of A

Permutation Sort(POOR)

It tries every case and check it! (Brute Force)
Then, there are 2 steps: (1) enumerating cases and (2) check sorting.

Therefore, Running time takes about $\Omega(n!\cdot n)$

• $n!$ comes from enumerating permutation of size $n$ array
• $n$ comes from analyizing whether it is sorted or not.

Selection Sort

Find the largest element with index and swap it!(We can think of ascending order and start from the last index.)
Then, there are 2 steps: (1) “prefix_max” for find the index of largest element (2) “selection_sort” for sorting process

Prefix_max

• Base case : takes $\theta(1)$
• Recursive equation : $S(n) = S(n-1) + \theta(1)$
• Substitution : $S(n) = \theta(n)$
• Recurrence Tree: chain of $n$ nodes & $\theta(1)$ for each node(Every node takes constant time just for comparison!)
  • $\sum 1 = \theta(n)$

selection subset

• Base case : takes $\theta(1)$
• Recursive equation : $T(n) = T(n-1) + \theta(n)$
• Substitution : $T(n) = \theta(n^2)$
• Recurrence Tree: chain of $n$ nodes & $\theta(i)$ for each node(Every node takes time proportional to index because it contains prefix_max process which takes linear time complexity!)
  • $\sum i = \theta(n^2)$

Insert Sort

reverse version of selection sort!

Merge Sort

Recursively sorting half of the subset and merge a pair of subset!
Then there are 2 steps: (1) sort it and (2) merge it.

merge

• Base case: takes $\theta(1)$
• Recursive equation $S(n) = S(n-1) + \theta(1)$
• Substitution : $S(n) = \theta(n)$

merge subset

• Base case: takes $\theta(1)$
• Recursive equation $T(n) = 2T(n/2) + \theta(n)$
  • The second term on the right hand side : caused by running function merge!
    • What is repeatedly called function is function merge!
  • The first term on the right hand side : caused by 2 (sub) arrays
• Substitution : $T(n) = \theta(n\log(n))$
  • Satisfies equation!
• Recurrence Tree: Think of running for the whole elements of array. We can see it as a binary tree with depth of $\log_2(n)$ and $n$ leaves. For level $i$, there are $2^i$ nodes and every node takes $O(n/2^i)$.
  • $\sum_i (2^i)(n/2^i) = \sum_i n = \theta(n\log_2(n))$