CS1-FULL-FALL2021
459
Sorting
460
why study sorting?
Sorting is a classic subject in computer science. There
are three reasons for studying sorting algorithms.
• First, sorting algorithms illustrate many creative
approaches to problem solving and these
approaches can be applied to solve other problems.
• Second, sorting algorithms are good for practicing
fundamental programming techniques using selection
statements, loops, methods, and arrays.
• Third, sorting algorithms are excellent examples to
demonstrate algorithm performance.
461
what data to sort?
The data to be sorted might be integers, floats, words, or
anything.
For simplicity, we will assume:
! data to be sorted are integers,
! data are sorted in ascending order, and
! data are stored in an list or a numpy array
462
Insertion Sort
myList = [2, 9, 5, 4, 8, 1, 6] // Unsorted
The insertion sort
algorithm sorts a
list of values by
repeatedly
inserting an
unsorted element
into a sorted
sublist until the
whole list is
sorted.
2 9 5 4 8 1 6
Step 1: Initially, the sorted sublist contains the
first element in the list . Insert 9 into the sublist .
2 9 5 4 8 1 6
Step2: The sorted sublist is {2, 9}. Insert 5 into
the sublist.
2 5 9 4 8 1 6
Step 3: The sorted sublist is {2, 5, 9}. Insert 4
into the sublist.
2 4 5 9 8 1 6
Step 4: The sorted sublist is {2, 4, 5, 9}. In sert 8
into the sublist.
2 4 5 8 9 1 6
Step 5: The sorted sublist is {2, 4, 5, 8, 9}. In sert
1 into the sublist.
1 2 4 5 8 9 6
Step 6: The sorted sublist is {1, 2, 4, 5, 8, 9}.
Insert 6 into the sublist.
1 2 4 5 6 8 9
Step 7: The entire list is now sorted.
463
Insertion Sort
2 9 5 4 8 1 6
2 9 5 4 8 1 6
2 5 9 4 8 1 6
2 4 5 8 9 1 6
1 2 4 5 8 9 6
2 4 5 9 8 1 6
1 2 4 5 6 8 9
myList = [2, 9, 5, 4, 8, 1, 6] // Unsorted
464
How to Insert?
The insertion sort
algorithm sorts a list
of values by
repeatedly inserting
an unsorted element
into a sorted sublist
until the whole list
is sorted.
[0] [1] [2] [3] [4] [5] [6]
2 5 9 4 list Step 1: Save 4 to a temporary variable currentElement
[0] [1] [2] [3] [4] [5] [6]
2 5 9 list Step 2: Move list[2] to list[3]
[0] [1] [2] [3] [4] [5] [6]
2 5 9 list Step 3: Move list[1] to list[2]
[0] [1] [2] [3] [4] [5] [6]
2 4 5 9 list Step 4: Assign currentElement to list[1]
465
https://visualgo.net/en/sorting
Insertion Sort Animation
466
Bubble Sort
2 5 9 4 8 1
2 5 4 9 8 1
2 5 4 8 9 1
2 5 4 8 1 9
(a) 1st pass
2 4 5 8 1 9
2 4 5 8 1 9
2 4 5 1 8 9
(b) 2nd pass
2 4 5 1 8 9
2 4 1 5 8 9
(c) 3rd pass
2 1 4 5 8 9
(d) 4th pass
2 9 5 4 8 1
(e) 5th pass
2 5 4 8 1 9
2 4 5 1 8 9
2 4 1 5 8 9
1 2 4 5 8 9
467
Bubble Sort Animation
https://visualgo.net/en/sorting
468
Quick Sort
Quick sort, developed by C. A. R. Hoare (1962), works
as follows:
• The algorithm selects an element, called the pivot, in
the array.
• Divide the array into two parts such that all the
elements in the first part are less than or equal to the
pivot and all the elements in the second part are
greater than the pivot.
• Recursively apply the quick sort algorithm to the first
part and then the second part.
469
Quick Sort
5 2 9 3 8 4 0 1 6 7
pivot
(a) The original array
4 2 1 3 0 5 8 9 6 7
pivot
(b)The original array is partitioned
0 2 1 3 4 (c) The partial array (4 2 1 3 0) is partitioned
0 2 1 3 (d) The partial array (0 2 1 3) is
partitioned
1 2 3
pivot
pivot
pivot
(e) The partial array (2 1 3) is
partitioned
470
Partition
5 2 9 3 8 4 0 1 6 7
pivot low high
(a) Initialize pivot, low, and high
5 2 9 3 8 4 0 1 6 7
pivot low high
(b) Search forward and backward
5 2 1 3 8 4 0 9 6 7
pivot low high
(c) 9 is swapped with 1
5 2 1 3 8 4 0 9 6 7
pivot low high
(d) Continue search
5 2 1 3 0 4 8 9 6 7
pivot low high
(e) 8 is swapped with 0
5 2 1 3 0 4 8 9 6 7
pivot low high
(f) when high < low, search is over 4 2 1 3 0 5 8 9 6 7 pivot (g) pivot is in the right place The index of the pivot is returned Merge Sort 2 9 5 4 8 1 6 7 2 9 5 4 8 1 6 7 split 2 9 split 5 4 2 split 9 5 4 8 1 6 7 8 1 6 7 2 9 merge 4 5 1 8 6 7 2 4 5 9 1 6 7 8 1 2 4 5 6 7 8 9 merge merge divide conquer