L4 QuickSort

Posted on Edited on In Views:

Outline:

  • Inversion

  • InsertionSort

  • Analysis of InsertionSort

  • QuickSort

  • Analysis of QuickSort

Ref:

  • 算法设计与分析(Algorithm design and analysis) by 黄宇

Inversion

  • Definition: Inversion
    • \(<x_i, x_j>\) is an inversion if \(x_i > x_j\) , but \(i < j\)
    • Sorting == Eliminating inversions

InsertionSort

Worst Case

  • Local comparison is done between is done between two adjacent elements
  • At most one inversion is removed by a local comparison
  • There do exist inputs with n(n-1)/2 inversions, such as ( n, n-1, ...., 3, 2, 1 ) （最坏情况，inversion最多）
  • The worst-case behavior of any sorting algorithm that remove at most one inversion per key comparison must in \(\Omega(n^2)\)​​​

Average Case

  • Computing the average number of inversions in inouts of size n ( n > 1 ):

    • Transpose: \[ x_1, x_2,x_3,\dots,x_{n-1},x_n \\ x_n,x_{n-1},\dots,x_3,x_2,x_1 \]

    • For any \(i, j\quad(1 \leq j \leq i \leq n)\)​ , the inversion \(( x_i, x_j )\) is in exactly one sequence in a transpose pair

    • The number of inversions (xi, xj) on n distinct integers is n(n-1)/2

    • So, the average number of inversions in all possible inputs is n(n-1)/4, since exactly n(n-1)/2 inversions appear in each transpose pair.

    • The average behavior of any sorting algorithm that remove at most one inversion per key comparison must in \(\Omega(n^2)\)

QuickSort

  • 每次递归，pivot的位置一定是对的

Worst Case: a Paradox

  • For a range of k positions, k - 1 keys are compared with the pivot( one is vacant )

    • if the pivot is the smallest, than the "large" segment has all the remaining k - 1, and the small segment is empty 最坏情况,每次问题的规模只减少1, 每次PARTITION代价是O(n)

    • If the elements in the array to be sorted has already ascending order( the Goal ), then the number os comparison that Partition has to do is:

      \(n - 1 + n - 2 + ... + 1 = n(n-1)/2 ∈ O(n^2)\)​

    • 考虑到所有输入等概率的情况,最坏情况的出现概率是很低的.

    所有元素只跟pivot比,左右两边里的任意两两之间没有比过. 这样才能用递归来分析

Analysis

3种方法

  • Guess and Prove 归纳法
  • Directly solve
  • Indication random variable

Space Complexity

  • Good news:
    • Partition is in-place 不占用额外的空间
  • Bad news:
    • In the worst case, the depth of recursion will be n - 1
    • So, the largest size of recursion stack will be in O(n)