AI 401 FOUNDATİON PROGRAM
Data Structures
Chapter 03 – Simple Sorting Algorithms
Instructor: Dr. Orhan Abar
Sorting arrays
What:
Functions that put a list/array of elements into order
Numerical, lexical, or more complex relationships
Why:
A fundamental data processing operation
Usually done at very large scale, so efficiency matters
Simple approach: Bubble sort
Compare each element (except the last one) with its neighbor to
the right
If they are out of order, swap them
This puts the largest element at the very end
The last element is now in the correct and final place
Compare each element (except the last two) with its neighbor to
the right
If they are out of order, swap them
This puts the second largest element next to last
The last two elements are now in their correct and final places
Compare each element (except the last three) with its neighbor
to the right
Continue as above until you have no unsorted elements on the left
Example of bubble sort
72854 27548 25478 24578
27854 27548 25478 24578
27854 25748 24578 (done)
27584 25478
27548
Code for bubble sort
Analysis of bubble sort
for last in range(self.__nItems-1, 0, -1):
for inner in range(last):
if self.__a[inner] > self.__a[inner+1]:
# code for element swap omitted
Let n = nItems = number of items stored in the Array
The 1st time through the outer loop, n-1 comparisons are done
The 2nd time through the outer loop, n-2 comparisons are done
The 3rd time through the outer loop, n-3 comparisons are done
The final time through the outer loop 1 comparison is done
Sum of 1 + 2 + 3 + … (n-3) + (n-2) + (n-1) ?
• (n-1) * n / 2
Result is O(n2) comparisons
Performance of Bubble Sort
14000000
12000000
10000000
8000000
O
Time
6000000
4000000
2000000
0
0 1000 2000 3000 4000 5000 6000
Number of items to sort
Loop invariants
You run a loop in order to change things
Oddly enough, what is usually most important in
understanding a loop is finding an invariant: that is, a
condition that doesn't change
In bubble sort, we put the largest elements at the end,
and once we put them there, we don't move them again
The variable last starts at the last index in the array and
decreases to 0 (we exit the loop when last == 0)
Our invariant is: "Every element to the right of last is in the
correct place"
That is, for all i > last, if i < j, then a[i] <= a[j]
When this is combined with last == 0, we know that all elements
of the array are in the correct place
Selection sort
Given an array of length n,
Search elements 0 through n-1 and select the
smallest
Swap it with the element in location 0
Search elements 1 through n-1 and select the
smallest
Swap it with the element in location 1
Search elements 2 through n-1 and select the
smallest
Swap it with the element in location 2
Search elements 3 through n-1 and select the
smallest
Example and analysis of selection sort
The selection sort might swap an
72854 array element with itself--this is
harmless, and not worth checking
27854 for
Analysis:
24857 1st time through the outer loop, we do
n-1 comparisons
2nd time through the outer loop we do
24587
(n-2) comparisons
And so on… resulting in roughly
24578 – (1 + 2 + 3 + 4 + … + n-1) comparisons
You should recognize this as O(n2)
Code for selection sort
Invariant: at any time during the loop, every element to
the left of outer is in the correct place:
For all j < outer, if i < j then a[i] <= a[j]
Insertion sort
• Outline of algorithm:
– For each element in the Array (starting
with the 2nd)
• Find the first location to the left of the
element that is less than or equal
• Move everything to the right of that element
one space and insert the element
One step of insertion sort
sorted next to be inserted
3 4 7 121414202133381055 9 232816
tem
less than 10
p10
3 4 7 101214142021333855 9 232816
sorted
Insertion sort code
Invariant for Insertion Sort
At any given point in the algorithm, the elements to
the left of outer are always in order
When outer == 1 this is trivially true
After each pass, outer increases until it reaches the number
of items
Big O analysis of insertion sort
The 1st time through the outer loop we do one
comparison.
The 2nd time through the outer loop we do one or two
comparisons
The 3rd time through the outer loop we do one, or two, or
three comparisons
The Nth time through the outer loop we do one, two, …
or N comparisons, but on average about N/2
comparisons.
So, the total amount of work (numbers of comparisons
and moves) is roughly:
• (1 + 2 + 3 + 4 + … + N) / 2, or
• N * (N + 1) / 4
Discarding constants, we find that insertion sort is O(N2)
What would the Big-O of insertion sort be, if we were to
Summary
Bubble sort, selection sort, and insertion sort are all O(N2)
As we will see later, we can do much better than this with
somewhat more complicated sorting algorithms
Within O(N2),
Bubble sort is very slow, and should probably never be used for anything
Selection sort is intermediate in speed
Insertion sort is usually the fastest of the three--in fact, for small arrays
(say, 10 or 15 elements), insertion sort is faster than more complicated
sorting algorithms
Selection sort and insertion sort are “good enough” for small
arrays
Shuffling (unsorting) an Array
Even an apparently O(N2) algorithm
can be fast sometimes!
https://www.cs.usfca.edu/~galles/visualization/
ComparisonSort.html
IMPORTANT: Which of the 3 sorting algorithms
works very well if the Array is almost-sorted
already?
How could we prove it?
