# Sorting Algorithms

Tom Kelliher, CS23

Apr. 23, 1997

Solve the recurrences: # The Three ``Slow'' Sorts

• Bubble sort.
• Selection sort.
• Insertion sort.

How slow are they?

What distinguishes them?

# Lower Bound for Comparison-Based Sorting

Stirling's approximation: Permutations and decision trees: # Mergesort

Algorithm:

```Split the array, A, into two pieces, A1 and A2
Recursively sort each piece

Empty A

while neither A1 nor A2 is empty
if the first item in A1 is smaller than the first item in A2
add A1's item to the end of A, removing it from A1
else
Add A2's item to the end of A, removing it from A2
end_if
end_while

one of A1, A2 is not empty -- move its elements to the end of A
```

Efficiency:

• Number of comparisons.
• Memory used.

Internal/External sorting method.

# Quicksort

• Worst-case, average-case.
• Pivot Selection.
• Key: efficiency of partitioning.

Algorithm:

```QuickSort(A[], f, l)
{
if (f < l)
{
choose a pivot, p, from A[f...l]

// index of p is pIndex

QuickSort(A, f, pIndex - 1)
QuickSort(A, pIndex, l)
}
}
```

Satisfaction of recursive requirements?

## Selection of the Pivot Value

What happens if one of the partitions is always empty?

How can we guarantee a ``good'' pivot value?

## Partitioning the Array

```/**********************************************************************
* Precondition: A has len elements and A is the desired pivot
* element.
*
* Postcondition: Returns the index, s, of the pivot element.
* A[i] < A[s] for 0 <= i < s and A[s] <= A[j] for s < j < len.
**********************************************************************/

int partition(int A[], int len)
{
int s = 1;
int l = len - 1;

// invariant: A[i] < A for 1 <= i < s and
//            A <= A[j] for l < j < len.
while (s < l)
{
if (A[s] < A)   // A[s] belongs in first partition.
++s;
else   // A[s] belongs in second partition: make room.
{
swap(A[s], A[l]);
--l;
}
}

// A[s] could either be in first or second partition.
if (A[s] >= A)   // A[s] is in second partition --- don't move it.
--s;

swap(A, A[s]);   // Swap partition element with last element in
// first partition.
return s;
}
```

Number of comparisons?