Sorting

Problem:   Given an array of n real number A[1.. n].
Objective: Sort the elements of A in ascending order of their values.

Internal Sort

External Sort

• Sorting files from tape or disk.
• In this method, an external sort algorithm must access records sequentially, or at least in the block.

Memory Requirement

1. Sort in place and use no extra memory except perhaps for a small stack or table.
2. Algorithm that use a linked-list representation and so use N extra words of memory for list pointers.
3. Algorithms that need enough extra memory space to hold another copy of the array to be sorted.

Stability

The Decision Tree Model

A Lower Bound for the Worst Case

n! ≤ 2^h
Taking logarithms on both sides

(lg(n!) ≤ h
        h  ≥ lg(n!)

           h  ≥  (n/e)ⁿ          which is Ω(n lg n)

Bubble Sort

SEQUENTIAL BUBBLESORT (A)

for i ← 1 to length [A] do
    for j ← length [A] downto i +1 do
        If A[A] < A[j-1] then
            Exchange A[j] ↔ A[j-1]

Memory Requirement

Implementation

PARALLEL BUBBLE SORT (A)

1. For k = 0 to n-2
2. If k is even then
3.     for i = 0 to (n/2)-1 do in parallel
4.         If A[2i] > A[2i+1] then
5.             Exchange A[2i] ↔ A[2i+1]
6. Else
7.     for i = 0 to (n/2)-2 do in parallel
8.         If A[2i+1] > A[2i+2] then
9.             Exchange A[2i+1] ↔ A[2i+2]
10. Next k

Parallel Analysis

Insertion Sort

1. We start with an empty left hand [sorted array] and the cards face down on the table [unsorted array].
2. Then remove one card [key] at a time from the table [unsorted array], and insert it into the correct position in the left hand [sorted array].
3. To find the correct position for the card, we compare it with each of the cards already in the hand, from right to left.

• The worst-case running time gives a guaranteed upper bound on the running time for any input. That is, upper bound gives us a guarantee that the algorithm will never take any longer.
• For some algorithms, the worst case occurs often. For example, when searching, the worst case often occurs when the item being searched for is not present, and searches for absent items may be frequent.
• Why not analyze the average case? Because it's often about as bad as the worst case.

• For Insertion sort we say the worst-case running time is θ(n²), and the best-case running time is θ(n).
• Insertion sort use no extra memory it sort in place.
• The time of  Insertion sort is depends on the original order of a input. It takes a time in Ω(n²) in the worst-case, despite the fact that a time in order of n is sufficient to solve large instances in which the items are already sorted.

void insertionSort(int numbers[], int array_size)
{
  int i, j, index;

  for (i = 1; i < array_size; i++)
  {
          index = numbers[i];
          j = i;
          while ((j > 0) && (numbers[j − 1] > index))
          {
                   numbers[j] = numbers[j − 1];
                   j = j − 1;
          }
          numbers[j] = index;
  }
}

 

Selection Sort

SELECTION_SORT (A)

for i ← 1 to n-1 do
    min j ← i;
    min x ← A[i]
    for j ← i + 1 to n do
        If A[j] < min x then
            min j ← j
            min x ← A[j]
    A[min j] ← A [i]
    A[i] ← min x

Implementation

Shell Sort

SHELL_SORT (A)

for h = 1 to h £ N/9 do
    for (; h > 0; h != 3) do
        for i = h +1 to i £ n do
            v = A[i]
             j = i
            while (j > h AND A[j - h] > v
                    A[i] = A[j - h]
                    j = j - h
            A[j] = v
            i = i + 1

Implementation

void shellSort(int numbers[], int array_size)
{
  int i, j, increment, temp;

  increment = 3;
  while (increment > 0)
  {
    for (i=0; i < array_size; i++)
    {
      j = i;
      temp = numbers[i];
      while ((j >= increment) && (numbers[j-increment] > temp))
      {
        numbers[j] = numbers[j - increment];
        j = j - increment;
      }
      numbers[j] = temp;
    }
    if (increment/2 != 0)
      increment = increment/2;
    else if (increment == 1)
      increment = 0;
    else
      increment = 1;
  }
}

Heap Sort

PARENT (i)
        return floor(i/2)
LEFT (i)
        return 2i
RIGHT (i)
        return 2i + 1

Heap Property

Height of a node

Height of a tree

 node is 

 which is (

). This implies that an n-element heap has height  

It follows that h =  

Inserting Element in the Heap

Now we are done, because 15   20.

1. Heapify, which runs in O(lg n) time.
2. Build-Heap, which runs in linear time.
3. Heap Sort, which runs in O(n lg n) time.
4. Extract-Max, which runs in O(lg n) time.

Maintaining the Heap Property

Outline of Procedure Heapify

Heapify (A, i)

1. l ← left [i]
2. r ← right [i]
3. if l ≤ heap-size [A] and A[l] > A[i]
4.     then largest ← l
5.     else largest ← i
6. if r ≤ heap-size [A] and A[i] > A[largest]
7.     then largest ← r
8. if largest  ≠ i
9.     then exchange A[i] ↔ A[largest]
10.         Heapify (A, largest)

Analysis

 work), which is 

. Since we have a case in which Heapify's running time 

Example of Heapify
 

Building a Heap

BUILD_HEAP (A)

1. heap-size (A) ← length [A]
2. For i ←  floor(length[A]/2) down to 1 do
3.         Heapify (A, i)

Heap Sort Algorithm

HEAPSORT (A)

1. BUILD_HEAP (A)
2. for i ← length (A) down to 2 do
   exchange A[1] ↔ A[i]
   heap-size [A] ← heap-size [A] - 1
   Heapify (A, 1)

 is the total number of nodes in the tree, is even and 

 when 

 is odd. If these leaves are removed, the number of new leaves will be 

 or 

. If  this process is continued for h levels the number of leaves at that level will be 

.

Implementation

void heapSort(int numbers[], int array_size)
{
  int i, temp;

  for (i = (array_size / 2)-1; i >= 0; i--)
    siftDown(numbers, i, array_size);

  for (i = array_size-1; i >= 1; i--)
  {
    temp = numbers[0];
    numbers[0] = numbers[i];
    numbers[i] = temp;
    siftDown(numbers, 0, i-1);
  }
}


void siftDown(int numbers[], int root, int bottom)
{
  int done, maxChild, temp;

  done = 0;
  while ((root*2 <= bottom) && (!done))
  {
    if (root*2 == bottom)
      maxChild = root * 2;
    else if (numbers[root * 2] > numbers[root * 2 + 1])
      maxChild = root * 2;
    else
      maxChild = root * 2 + 1;

    if (numbers[root] < numbers[maxChild])
    {
      temp = numbers[root];
      numbers[root] = numbers[maxChild];
      numbers[maxChild] = temp;
      root = maxChild;
    }
    else
      done = 1;
  }
}

Merge Sort

• Choose the smaller of the two top cards.
• Remove it from its pile, thereby exposing a new top card.
• Place the chosen card face-down onto the output pile.
• Repeatedly perform basic steps until one input pile is empty.
• Once one input pile empties, just take the remaining input pile and place it face-down onto the output pile.

• The first part shows the arrays at the start of the "for k ← p to r" loop, where A[p . . q] is copied into L[1 . . n₁] and A[q + 1 . . r ] is
  copied into R[1 . . n₂].
• Succeeding parts show the situation at the start of successive iterations.
• Entries in A with slashes have had their values copied to either L or R and have not had a value copied back in yet. Entries in L and R with slashes have been copied back into A.
• The last part shows that the subarrays are merged back into A[p . . r], which is now sorted, and that only the sentinels (∞) are exposed in the arrays L and R.]

• Divide: Just compute q as the average of p and r, which takes constant time i.e. Θ(1).
• Conquer: Recursively solve 2 subproblems, each of size n/2, which is 2T(n/2).
• Combine: MERGE on an n-element subarray takes Θ(n) time.

• The top level has cost cn.
• The next level down has 2 subproblems, each contributing cost cn/2.
• The next level has 4 subproblems, each contributing cost cn/4.
• Each time we go down one level, the number of subproblems doubles but the cost per subproblem halves. Therefore, cost per level stays the same.

Quick Sort

Good points

• It is in-place since it uses only a small auxiliary stack.
• It requires only n log(n) time to sort n items.
• It has an extremely short inner loop
• This algorithm has been subjected to a thorough mathematical analysis, a very precise statement can be made about performance issues.

Bad Points

• It is recursive. Especially if recursion is not available, the implementation is extremely complicated.
• It requires quadratic (i.e., n²) time in the worst-case.
• It is fragile i.e., a simple mistake in the implementation can go unnoticed and cause it to perform badly.

QuickSort

1. If p < r then
2.     q Partition (A, p, r)
3.     Recursive call to Quick Sort (A, p, q)
4.     Recursive call to Quick Sort (A, q + r, r)

Partitioning the Array

PARTITION (A, p, r)

1. x ← A[p]
2. i ← p-1
3. j ← r+1
4. while TRUE do
5.     Repeat j ← j-1
6.     until A[j] ≤ x
7.     Repeat i ← i+1
8.     until A[i] ≥ x
9.     if i < j
10.         then exchange A[i] ↔ A[j]
11.         else return j

The running time of the partition procedure is 

Another argument that running  time of PARTITION on a subarray of size 

Array of Same Elements

Performance of Quick Sort

Best Case

T(n) = T(n/2) + T(n/2) + (n)
       = 2T(n/2) + (n)

        T(n) = (n lg n)

Worst case Partitioning

Randomized Quick Sort

RANDOMIZED_PARTITION (A, p, r)

i ← RANDOM (p, r)
Exchange A[p] ↔ A[i]
return PARTITION (A, p, r)

RANDOMIZED_QUICKSORT (A, p, r)

If p < r then
    q ← RANDOMIZED_PARTITION (A, p, r)
    RANDOMIZED_QUICKSORT (A, p, q)
    RANDOMIZED_QUICKSORT (A, q+1, r)

Analysis of Quick sort

Let T(n) be the worst-case time for QUICK SORT on input size n. We have a recurrence

T(n) = max_1≤q≤n-1 (T(q) + T(n-q)) + (n)             --------- 1

where q runs from 1 to n-1, since the partition produces two regions, each having size at least 1.
Now we guess that T(n) ≤ cn² for some constant c.
Substituting our guess in equation 1.We get

    T(n) = max_1≤q≤n-1 (cq² ) + c(n - q²)) + (n)
           = c max (q² + (n - q)²) +  (n)

Since the second derivative of expression q² + (n-q)²  with respect to q is positive. Therefore, expression achieves a maximum over the range 1≤ q  ≤ n -1 at one of the endpoints. This gives the bound max (q² + (n - q)²)) 1 + (n -1)^{2 =} n² + 2(n -1).
Continuing with our bounding of T(n) we get