算法基础笔记0x02 —— 排序

Insertion Sort

  • Sort the first k numbers.
  • Insert k+1’st number v in the proper place.
    • Compare v with first k numbers from back to front.
    • Stop if find number < v.

Pseudocode


Complexity

  • Let n = length(A).
  • Total number of swaps at most (worst case)
    • $1+2+…+(n-1)=n*(n-1)/2 = O(n^2)$.

Pros and Cons

  • 需要一个单位的额外空间来交换
  • 对于较小的输入速度较快(n<=20)
  • However, not practical for large input size because $O(n^2)$ is too high.

Mergesort

  • Sort an array of numbers
  • Divide the array into 2 equal size subarrays.
  • Recursively sort each subarray.
    • If array size = 1, just return the array.
  • Merge two sorted subarrays into one sorted array.
    • Key is how to merge efficiently.


Pseudocode


Complexity

  • Mergesort’s main drawback is need for extra storage in L, R.
  • Sorting n numbers requires 2n storage.
  • Define
    • S(n) = time to mergesort n numbers. = 2S(n/2) + T(n).
    • T(n) time to merge two sorted arrays of n/2 numbers.
  • T(n) = O(n)
  • S(n) = O(nlogn)

Quicksort

  • To sort an array of n numbers, first choose a pivot element x from the array.
    • Different ways of choosing pivot.
    • Choice of pivot affects performance.
  • Move all array elements ≤ x before x, and all elements > x after x.
    • Called partitioning.
  • Recursively sort each side of x.
    • If a side has 0 or 1 elements, don’t recurse.
  • Now entire array is sorted.

Pseudocode



Complexity

Quicksort’s complexity depends on how balanced the pivot is.

  • Say the parts have sizes u, v.
  • Perfectly balanced if u = v.
    Let S(n) = time to quicksort n numbers.
    S(n) = S(u) + S(v) + cn.

Best case u = v.

  • S(n) ≤ 2 S(n/2) + cn.
    • Because u+v = n-1, so u=v=(n-1)/2.
  • Solves to S(n) = O(n log n).
  • In best case, Quicksort as fast as mergesort.

Worst case u = n-1, v=0 (or vice versa).

  • S(n) = S(n-1) + cn.
  • Solves to S(n) = O(n 2 ).
  • Worst case as bad as insertion sort.

Comparison

Insertion Sort vs. Mergesort

For large n, mergesort is much faster.
However, for small n insertion sort has less overhead and is very efficient.
Can combine mergesort and insertion sort.

  1. Divide problem into small groups (≈ 20 elements each).
  2. Use insertion sort to sort each group.
  3. Combine the sorted groups using merge.

Mergesort vs. Quicksort

Unlike mergesort, it doesn’t use any additional storage.
Quicksort spends more time finding a “nice” division of the problem, to make the combination step faster.

Mergesort Quicksort
Divide array in two parts. Trivial O(n)
Recursively sort each part. 2S(n/2) 2S(n/2)
Combine parts. O(n) Trivial

Even if partitions are partially balanced, quicksort is fast.

  • Say partitions are 90% imbalanced, i.e. u=0.9n, v=0.1n
  • Then S(n) ≤ S(0.9n) + S(0.1n) + cn.
  • Even in this case, S(n)=O(nlogn)!

Divide and Conquer

  • Divide the problem into smaller pieces.
  • Solve each recursively.
  • Combine the subsolutions into a complete solution

Resources

Visual Sorting

Example Code

https://github.com/kiki0805/Basic-Algorithm/tree/master/sorting

Leave a Reply

Your email address will not be published.