• Category
  • Bubble, Selection, insertion: O(n^2)
  • Bucket Sort: O(n+N) —Hash table
  • Merge Sort: O(nlogn) Divide and conQuer slower then insertion at n<15

    1. Recursive ver Downward Pass→Upward Pass O(n) O(n) each level * O(log n) levels →O(nlogn)

      Untitled

    2. Non-Recursive ver(Usual Way) No downward Pass →O(nlogn)

      Untitled

  • QuickSort Best: O(nlogn); Left and right are equal Worst: O(n^2); left=0 or right=0 / pivot is smallest / input is sorted Divide and Conquer

    • Divide

      1. Select pivot
        1. Median key value
        2. First/last element: if sorted worst case
        3. random: ‘expensive’
        4. middle element
        5. median-of-three
      2. partition: left(key values<pivot) , pivot , Right(key values > pivot)

      In-Place partitioning

      1. set pivot as leftmost
      2. find leftmost element > pivot
      3. find rightmost element <pivot
      4. swap L & R if L is left of R

      Untitled

    • Conquer ans=[left pivot right]