09. Sorting

Sorting

Contents

• 0. Sorting so far...
  • (1) PQ-sort
  • (2) Selection-sort
  • (3) Insertion-sort
  • (4) Heap-sort
• 1. Merge-Sort
• 2. Quick-Sort
• Summary of Sorting Algorithms

0. Sorting so far...

(1) PQ-sort

• Insert the elements one by one with a series of insert(e) operations
• Remove the elements in sorted order with a series of removeMin() operations

(2) Selection-sort

• Inserting elements into a PQ (implemented with an unsorted list) without taking care of the order;
  • Removing an element from the PQ needs a search

(3) Insertion-sort

• Inserting elements into a PQ (implemented with a sorted list) while taking care of the order;
  • Removing an element at the front

(4) Heap-sort

• Inserting elements into a PQ (implemented with a heap) while keeping the heap-order;
  • Removing an element at the root of the heap (a downheap maybe necessary)

Summary of Sorting Algorithms

1. Merge-Sort

Divide-and-Conquer

• Divide-and-conquer is a general algorithm design paradigm:
  • Divide: divide the input data S in two disjoint subsets S_1 and S_2
  • Recur: solve the subproblems associated with S_1 and S_2
  • Conquer: combine the solutions for S_1 and S_2 into a solution for S
• The base case for the recursion are subproblems of size 0 or 1

Merge-Sort

• Merge-sort is a sorting algorithm based on the divide-and-conquer paradigm

• Like heap-sort

  • It uses a comparator
  • It has O(n log n) running time

• Unlike heap-sort

• It does not use an auxiliary priority queue

• It accesses data in a sequential manner (suitable to sort data on a disk)

• Merge-sort on an input sequence S with n elements consists of three steps:

  • Divide: partition S into two sequences S_1 and S_2 of about n/2 elements each
  • Recur: recursively sort S_1 and S_2
  • Conquer: merge S_1 and S_2 into a unique sorted sequence

Algorithm mergeSort(S, C)
  Input sequence S with n
    elements, comparator C
  Output sequence S sorted
    according to C
  if S.size() > 1
    (S1, S2) ← partition(S, n/2)
    mergeSort(S1, C)
    mergeSort(S2, C)
  else:
    S ← merge(S1, S2)

Merging Two Sorted Sequences

• The conquer step of merge-sort consists of merging two sorted sequences A and B into a sorted sequence S containing the union of the elements of A and B
• Merging two sorted sequences, each with n/2 elements and implemented by means of a doubly linked list, takes O(n) time

Algorithm merge(A, B)
  Input sequences A and B with n/2 elements each
  Output sorted sequence of A È B

  S ← empty sequence
  while (not A.empty()) and (not B.empty())
    if A.front() < B.front()
      S.addBack(A.front());
      A.eraseFront();
    else
      S.addBack(B.front());
      B.eraseFront();

  while not A.empty()
    S.addBack(A.front());
    A.eraseFront();

  while not B.empty()
    S.addBack(B.front());
    B.eraseFront();

  return S

Merge-Sort Tree

• An execution of merge-sort is depicted by a binary tree
• Each node represents are cursive call of merge-sort and stores
  • Unsorted sequence before the execution and its partition
  • Sorted sequence at the end of the execution
• The root is the initial call
• The leaves are calls on subsequences of size 0 or 1

Execution Example

Analysis of Merge-Sort

• The height h of the merge-sort tree is O(logn)
  • At each recursive call we divide in half the sequence,
• The overall amount or work done at the nodes of depth i is O(n)
  • We partition and merge 2^i sequences of size n/2^i
  • We make 2^(i+1) recursive calls
• Thus, the total running time of merge-sort is O(nlogn)

Summary of Sorting Algorithms

2. Quick-Sort

• Quick-sort is a randomized sorting algorithm based on the divide-and-conquer paradigm:
  • Divide: pick a random element x (called pivot) and partition S into
    • L elements less than x
    • E elements equal x
    • G elements greater than x
  • Recur: sort L and G
  • Conquer: join L, E and G

Partition

• We partition an input sequenceas follows:
  • We remove, in turn, each element y from S and
  • We insert y into L, E or G, depending on the result of the comparison with the pivot x
• Each insertion and removal is at the beginning or at the end of a sequence, and hence takes O(1) time
• Thus, the partition step of quick-sort takes O(n) time

Algorithm partition(S, p)
  Input sequence S, position p of pivot
  Output subsequences L, E, G of the elements of S less than, equal to, or greater than the pivot, respectively

  L, E, G ← empty sequences
  x ← S.erase(p)

  while not S.empty()
    y ← S.eraseFront()
    if y < x
      L.insertBack(y)
    else if y = x
      E.insertBack(y)
    else // y > x
      G.insertBack(y)
  return L, E, G

Quick-Sort Tree

• An execution of quick-sort is depicted by a binary tree
  • Each node represents are cursive call of quick-sort and stores
    • Unsorted sequence before the execution and its pivot
    • Sorted sequence at the end of the execution
  • The root is the initial call
  • The leaves are call son subsequences of size 0 or 1

Execution Example

Worst-case Running Time

• The worst case for quick-sort occurs when the pivot is the unique minimum or maximum element
• One of L and G has size n-1 and the other has size 0
• The running time is proportional to the sum n + (n - 1) + ... + 2 + 1
• Thus, the worst-case running time of quick-sort is O(n^2)

Expected Running Time

• Consider a recursive call of quick-sort on a sequence of sizes
  • Good call: the sizes of L and G are each less than 3s/4
  • Bad call: one of L and G has size greater than 3s/4

• A call is good with probability 1/2

  • 1/2 of the possible pivots cause good calls:

• The expected height of the quick-sort tree is O(logn)

• The amount or work done at the nodes of the same depth is O(n)

• Thus, the expected running time of quick-sort isO(nlogn)

In-Place Quick-Sort

• Quick-sort can be implemented to run in-place
• In the partition step, we use replace operations to rearrange the elements of the input sequence such that
  • The elements less than the pivot have rank less than h
  • The elements equal to the pivo thave rank between h and k
  • The elements greater than the pivot have rank greater than k
• The recursive calls consider
  • Elements with rank less than h
  • Elements with rank greater than k

Algorithm inPlaceQuickSort(S, l, r)
  Input sequence S, ranks l and r
  Output sequence S with the elements of rank between l and r rearranged in increasing order

  if l >= r
    return
  i ← a random integer between l and r
  x ← S.elemAtRank(i)
  (h, k) ← inPlacePartition(x)
  inPlaceQuickSort(S, l, h - 1)
  inPlaceQuickSort(S, k + 1, r)

In-Place Partitioning

• Send pivot to the end of the sequence

  • 

• Repeat until l and r cross:

  • Scan l to the right until finding an element>=x
  • Scan r to the left until finding an element<x
  • Swap elements at indices l and r

• Then swap the element at l and at the end (at x)

Example

Summary of Sorting Algorithms