Sorting Techniques and Algorithms

Overview

Vocabulary Words

sort, sorting, sorting technique, list, array, array size, array length, ascending order, least to greatest, descending order, greatest to least, pseudocode, algorithm, bubble sort, insertion sort, selection sort, merge sort, counting sort, bucket sort, heap sort, comparison sort, binary insertion sort, quick sort, tournament sort

Objectives

Students will:

(1.) Discuss several sorting techniques
(2.) Sort arrays in ascending order using several sorting techniques
(3.) Discuss the advantages and disadvantages of each sorting technique.
(4.) Write programs in C++, Java, C#, Python of each sorting technique

Bubble Sort

The Bubble sort is the sorting technique that sorts an array in ascending order using this algorithm:
(1.) Compare the first element with the second element
(2.) If the first element is greater than the second element, interchange the elements (move the first element to the second position, and the second element to the first position)
(3.) If the first element is less than or equal to the second element, leave 'as is'.
(4.) Compare the second element with the third element
(5.) If the second element is greater than the third element, interchange the elements (move the second element to the third position, and the third element to the second position)
(6.) If the second element is less than or equal to the third element, leave 'as is'.
(7.) Compare the third element with the fourth element
...and continue that way until the array is sorted.

Example 1:
Sort the array: $9, 5, 7, 3, 8$ using Bubble Sort

$Array:\:\: \begin{array} {|r|r|}\hline 9 & 5 & 7 & 3 & 8 \\ \hline \end{array} \\[3ex]$

Teacher: Can you imagine having to go three rounds just to sort a simple array?
Student: Yes...and several steps in each round.
There has got to be a better way to do this.
Teacher: Of course. We shall explore more techniques.
But, let us write the pseudocode for this technique.

Pseudocode for Bubble Sort

First Method
$n$ = array size
sortArray bubbleSort($a_1, ..., a_n$ where $n \ge 2$)
for $i = 1$ to $n - 1$
   for $j = 1$ to $n - i$
    if $a_j \gt a_{j + 1}$ then interchange $a_j$ and $a_{j + 1}$

Second Method
$n$ = array size
sortArray bubbleSort($a_1, ..., a_n$ where $n \ge 2$)
for $i = 1$ to $n - 1$
   for $j = n$ to $i + 1$
    if $a_j \lt a_{j - 1}$ then interchange $a_j$ and $a_{j - 1}$

Insertion Sort

The Insertion sort is the sorting technique that sorts an array in ascending order using this algorithm:
(1.) Compare the second element with the first element
(2.) If the second element is less than the first element, interchange the elements (move the second element to the first position, and the first element to the second position)
(3.) If the second element is greater than or equal to the first element, leave 'as is'.
(4.) Compare the third element with the first element
(5.) If the third element is less than the first element, move the third element to the first position
(6.) If the third element is greater than the first element, compare the third element with the second element.
(7.) If the third element is less than the second element, interchange the elements
(move the third element to the second position, and the second element to the third position)
(8.) If the third element is greater than the second element, leave 'as is'
...and continue that way until the array is sorted.

Example $1$:
Sort the array: $9, 5, 7, 3, 8$ using Insertion Sort

$Array:\:\: \begin{array} {|r|r|}\hline 9 & 5 & 7 & 3 & 8 \\ \hline \end{array} \\[3ex]$

Student: This one seems easier than Bubble sort
Even though it has four rounds.
Teacher: Can you figure out your own technique?
A technique that will be faster?
Well, let's discuss more techniques

Pseudocode for Insertion Sort

First Method
$n$ = length of array
sortArray InsertionSort($a_1, ..., a_n$ where $n \ge 2$)
for $j = 2$ to $n$
   $i = 1$
   while $a_j \gt a_i$
    $i = i + 1$
   $m = a_j$
   for $k = 0$ to $j - i - 1$
    $a_{j - k} = a_{j - k - 1}$
   $a_i = m$

Second Method
$n$ = length of array
sortArray InsertionSort($a_1, ..., a_n$ where $n \ge 2$)
for $j = 2$ to $n$
   $key = a_j$
   $i = j - 1$
   while $i \gt 0$ and $a_i \gt key$
    $a_{i + 1} = a_i$
    $i = i - 1$
   $a_{i + 1} = key$