An Introduction to Sorting
An Introduction to Sorting
*
Chapter Contents
Selection Sort
Iterative Selection Sort
Recursive Selection Sort
The Efficiency of Selection Sort
Insertion Sort
Iterative Insertion Sort
Recursive Insertion Sort
The Efficiency of Insertion Sort
Shell Sort
The Efficiency of Shell Sort
Comparing the Algorithms
*
Selection Sort
Sorting: Arrange things into either ascending or descending order
Task: rearrange books on shelf by height
Shortest book on the left
Approach:
Look at books, select shortest book
Swap with first book
Look at remaining books, select shortest
Swap with second book
Repeat …
*
Selection Sort
Before and after exchanging shortest book and the first book.
*
Selection Sort
A selection sort of an array of integers into ascending order.
*
Iterative Selection Sort
Iterative algorithm for selection sort
Algorithm selectionSort(a, n)
// Sorts the first n elements of an array a.
for (index = 0; index < n - 1; index++)
{ indexOfNextSmallest = the index of the smallest value among
a[index], a[index+1], . . . , a[n-1]
Interchange the values of a[index] and a[indexOfNextSmallest]
// Assertion: a[0] £ a[1] £ . . . £ a[index], and these are the smallest
// of the original array elements.
// The remaining array elements begin at a[index+1].
}
*
Recursive Selection Sort
Recursive algorithm for selection sort
Algorithm selectionSort(a, first, last)
// Sorts the array elements a[first] through a[last] recursively.
if (first < last)
{ indexOfNextSmallest = the index of the smallest value among
a[first], a[first+1], . . . , a[last]
Interchange the values of a[first] and a[indexOfNextSmallest]
// Assertion: a[0] £ a[1] £ . . . £ a[first] and these are the smallest
// of the original array elements.
// The remaining array elements begin at a[first+1].
selectionSort(a, first+1, last)
}
*
The Efficiency of Selection Sort
Iterative method for loop executes n – 1 times
For each of n – 1 calls, the indexOfSmallest is invoked, last is n-1, and first ranges from 0 to n-2.
For each indexOfSmallest, compares last – first times
Total operations: (n – 1) + (n – 2) + …+ 1 = n(n – 1)/2 = O(n2)
It does not depends on the nature of the data in the array.
Recursive selection sort performs same operations
Also O(n2)
*
Insertion Sort
If only one book, it is sorted.
Consider the second book, if shorter than first one
Remove second book
Slide first book to right
Insert removed book into first slot
Then look at third book, if it is shorter than 2nd book
Remove 3rd book
Slide 2nd book to right
Compare with the 1st book, if is taller than 3rd, slide 1st to right, insert the 3rd book into first slot
*
Insertion Sort
The placement of the third book during an insertion sort.
*
Insertion Sort
Partitions the array into two parts. One part is sorted and initially contains the first element.
The second part contains the remaining elements.
Removes the first element from the unsorted part and inserts it into its proper sorted position within the sorted part by comparing with element from the end of sorted part and toward its beginning.
The sorted part keeps expanding and unsorted part keeps shrinking by one element at each pass
*
Iterative Insertion Sort
Iterative algorithm for insertion sort
Algorithm insertionSort(a, first, last)
// Sorts the array elements a[first] through a[last] iteratively.
for (unsorted = first+1 through last)
{ firstUnsorted = a[unsorted]
insertInOrder(firstUnsorted, a, first, unsorted-1)
}
Algorithm insertInOrder(element, a, begin, end)
// Inserts element into the sorted array elements a[begin] through a[end].
index = end
while ( (index >= begin) and (element < a[index]) )
{ a[index+1] = a[index] // make room
index - -
}
// Assertion: a[index+1] is available.
a[index+1] = element // insert
*
Iterative Insertion Sort
An insertion sort inserts the next unsorted element into its proper location within the sorted portion of an array
*
Iterative Insertion Sort
An insertion sort of an array of integers into ascending order
*
Recursive Insertion Sort
Algorithm for recursive insertion sort
Algorithm insertionSort(a, first, last)
// Sorts the array elements a[first] through a[last] recursively.
if (the array contains more than one element)
{ Sort the array elements a[first] through a[last-1]
Insert the last element a[last] into its correct sorted position
within the rest of the array
}
*
Recursive Insertion Sort
Inserting the first unsorted element into the sorted portion of the array.
(a) The element is ≥ last sorted element;
(b) The element is < than last sorted element
*
Efficiency of Insertion Sort
Best time efficiency is O(n)
Worst time efficiency is O(n2)
If array is closer to sorted order
Less work the insertion sort does
More efficient the sort is
Insertion sort is acceptable for small array sizes
*
Shell Sort
A variation of the insertion sort
But faster than O(n2)
Done by sorting subarrays of equally spaced indices
Instead of moving to an adjacent location an element moves several locations away
Results in an almost sorted array
This array sorted efficiently with ordinary insertion sort
*
Shell Sort
Donald Shell suggested that the initial separation between indices be n/2 and halve this value at each pass until it is 1.
An array has 13 elements, and the subarrays formed by grouping elements whose indices are 6 apart.
*
Shell Sort
The subarrays after they are sorted, and the array that contains them.
*
Shell Sort
The subarrays by grouping elements whose indices are 3 apart
*
Shell Sort
The subarrays after they are sorted, and the array that contains them.
*
Efficiency of Shell Sort
Efficiency is O(n2) for worst case
If n is a power of 2
Average-case behavior is O(n1.5)
Shell sort uses insertion sort repeatedly.
Initial sorts are much smaller, the later sorts are on arrays that are partially sorted, the final sort is on an array that is almost entirely sorted.
*
Comparing the Algorithms
Best Average Worst
Case Case Case
Selection sort O(n2) O(n2) O(n2)
Insertion sort O(n) O(n2) O(n2)
Shell sort O(n) O(n1.5) O(n1.5) or O(n2)
The time efficiencies of three sorting algorithms, expressed in Big Oh notation.