Algorithms, Data Structures

and Computability
 Sorting Algorithms

• There are many sorting algorithms, such as:

❑ Bubble Sort
❑ Selection Sort
❑ Insertion Sort
❑ Merge Sort
❑ Quick Sort
 Sorting
• Sorting is one of the most studied problems in computer science – there is even a ‘world
cup for sorting’, the Sort Benchmark competition.
• Sorting provides instructive examples of how algorithms and data structures work together,
and of how the correct choice of data structure can make dramatic improvements in
execution speed and memory usage.
• sorting algorithms, starting with naive approaches based on comparison and exchange:
Bubble sort, Selection sort, and Insertion sort
• We also introduce a powerful programming technique: recursion.
• An understanding of recursion allows us to move on to consider more sophisticated
procedures for sorting, notably Quick Sort, one of the fastest sorting algorithms.
• Complexity analyses of all the algorithms considered, to derive estimates of the efficiency
of each.
Next lecture:
• You’ll then look at some of the trade-offs between speed and memory that have to be
accepted when choosing between recursive and iterative algorithms.
• Data structures themselves can be recursive like Heap that uses recursive the heap sort
algorithm.
 Bubble Sort
The bubble sort makes multiple passes through a list. It compares
adjacent items and exchanges those that are out of order. Each pass
through the list places the next largest value in its proper place. In
essence, each item “bubbles” up to the location where it belongs.

The figure in the next slide shows the first pass of a bubble sort. The
shaded items are being compared to see if they are out of order. If
there are n items in the list, then there are n−1 pairs of items that need
to be compared on the first pass. It is important to note that once the
largest value in the list is part of a pair, it will continually be moved
along until the pass is complete.
Visualize the Bubble Sort:
https://visualgo.net/en/sorting
Visualize the Bubble Sort:
https://visualgo.net/en/sorting

At the start of the second

pass, the largest value is now
in place. There are n−1 items
left to sort, meaning that there
will be n−2 pairs. Since each
pass places the next largest
value in place, the total
number of passes necessary
will be n−1. After completing
the n−1 passes, the smallest
item must be in the correct
position with no further
processing required.
 Bubble Sort Algorithm
The exchange operation, sometimes
def bubbleSort(alist): called a “swap,” is slightly different in
for passnum in range(len(alist)-1,0,-1): Python than in most other
for i in range(passnum): programming languages.
if alist[i]>alist[i+1]:
temp = alist[i] In Python, it is possible to perform
alist[i] = alist[i+1] simultaneous assignment. The
alist[i+1] = temp statement a,b=b,a will result in two
assignment statements being done at
alist = [54,26,93,17,77,31,44,55,20] the same time
bubbleSort(alist)
print(alist)

Press here to see the

run
Step by step
 Bubble Sort – Analysis
• Best-case: ➔ O(n)
• Array is already sorted in ascending order.
• The number of moves: 0 ➔ O(1)
• The number of key comparisons: (n-1) ➔ O(n)
• Worst-case: ➔ O(n2)
• Array is in reverse order:
• Outer loop is executed n-1 times,
• The number of moves: 3*(1+2+...+n-1) = 3 * n*(n-1)/2 ➔ O(n2)
• The number of key comparisons: (1+2+...+n-1)= n*(n-1)/2 ➔ O(n2)
• Average-case: ➔ O(n2)
• We have to look at all possible initial data organizations.
• So, Bubble Sort is O(n2)
 Selection Sort

The selection sort improves on the bubble sort by making only one
exchange for every pass through the list. In order to do this, a
selection sort looks for the largest value as it makes a pass and, after
completing the pass, places it in the proper location. As with a bubble
sort, after the first pass, the largest item is in the correct place. After
the second pass, the next largest is in place. This process continues
and requires n−1passes to sort n items, since the final item must be in
place after the (n−1)st pass.
 Visualize the Selection Sort:
https://visualgo.net/en/sorting

The figure shows the entire

sorting process. On each
pass, the largest remaining
item is selected and then
placed in its proper location.
The first pass places 93, the
second pass places 77, the
third places 55, and so on.
 Selection Sort (cont.)
def selectionSort(alist):
for fillslot in range(len(alist)-1,0,-1):
positionOfMax=0
for location in range(1,fillslot+1):
if alist[location]>alist[positionOfMax]:
positionOfMax = location

temp = alist[fillslot]
alist[fillslot] = alist[positionOfMax]
alist[positionOfMax] = temp

alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist)
print(alist)
Press here to see
the run
Step by step
 Selection Sort -- Analysis

• In general, we compare keys and move items (or exchange items) in a

sorting algorithm (which uses key comparisons).
➔ So, to analyze a sorting algorithm we should count the number of
key comparisons and the number of moves.
• Ignoring other operations does not affect our final result.

• In selectionSort function, the outer for loop executes n-1 times.

• We invoke swap function once at each iteration.
➔ Total Swaps: n-1
➔ Total Moves: 3*(n-1) (Each swap has three moves)
 Selection Sort – Analysis (cont.)
• The inner for loop executes the size of the unsorted part minus 1
(from 1 to n-1), and in each iteration we make one key
comparison.
➔ # of key comparisons = 1+2+...+n-1 = n*(n-1)/2
➔ So, Selection sort is O(n2)
• The best case, the worst case, and the average case of the
selection sort algorithm are same. ➔ all of them are O(n2)
• This means that the behavior of the selection sort algorithm does not depend on the
initial organization of data.
• Since O(n2) grows so rapidly, the selection sort algorithm is appropriate only for small n.
Comparison of N, logN and N2
N O(LogN) O(N2)
16 4 256
64 6 4K
256 8 64K
1,024 10 1M
16,384 14 256M
131,072 17 16G
262,144 18 6.87E+10
524,288 19 2.74E+11
1,048,576 20 1.09E+12
1,073,741,824 30 1.15E+18
 Insertion Sort

• Insertion sort is a simple sorting algorithm that is appropriate

for small inputs.
• Most common sorting technique used by card players.
• The list is divided into two parts: sorted and unsorted.
• In each pass, the first element of the unsorted part is picked up,
transferred to the sorted sublist, and inserted at the
appropriate place.
• A list of n elements will take at most n-1 passes to sort the
data.
 Insertion Sort

• The insertion sort, although still O(n2), works in a

slightly different way. It always maintains a sorted
sublist in the lower positions of the list. Each new item
is then “inserted” back into the previous sublist such
that the sorted sublist is one item larger.
Visualize the Insertion Sort:
https://visualgo.net/en/sorting

We begin by assuming
that a list with one item
(position 0) is already
sorted. On each pass, one
for each item 1
through n−1, the current
item is checked against
those in the already sorted
sublist. As we look back
into the already sorted
sublist, we shift those
items that are greater to
the right. When we reach
a smaller item or the end
of the sublist, the current
item can be inserted.
The figure shows the fifth
pass in detail. At this point in
the algorithm, a sorted
sublist of five items
consisting of 17, 26, 54, 77,
and 93 exists. We want to
insert 31 back into the
already sorted items. The
first comparison against 93
causes 93 to be shifted to
the right. 77 and 54 are also
shifted. When the item 26 is
encountered, the shifting
process stops and 31 is
placed in the open position.
Now we have a sorted
sublist of six items.
 Insertion Sort Algorithm
def insertionSort(alist):
for index in range(1,len(alist)):
currentvalue = alist[index]
position = index
while position>0 and alist[position-
1]>currentvalue:
alist[position]=alist[position-1]
position = position-1
alist[position]=currentvalue
alist = [54,26,93,17,77,31,44,55,20]
insertionSort(alist)
print(alist)
Press here to see the
run
Step by step
 Insertion Sort – Analysis
• Running time depends on not only the size of the array but
also the contents of the array.
• Best-case: ➔ O(n)
• Array is already sorted in ascending order.
• Inner loop will not be executed.
• The number of moves: 2*(n-1) ➔ O(n)
• The number of key comparisons: (n-1) ➔ O(n)
• Worst-case: ➔ O(n2)
• Array is in reverse order:
• Inner loop is executed i-1 times, for i = 2,3, …, n
• The number of moves: 2*(n-1)+(1+2+...+n-1)= 2*(n-1)+ n*(n-1)/2 ➔ O(n2)
• The number of key comparisons: (1+2+...+n-1)= n*(n-1)/2 ➔ O(n2)
• Average-case: ➔ O(n2)
• We have to look at all possible initial data organizations.
• So, Insertion Sort is O(n2)
 Analysis of sorting algorithms:
Best, worst or average?

• Which running time will be used to characterize this

algorithm?
• Best, worst or average?
• Worst:
• Longest running time (this is the upper limit for the algorithm)
• It is guaranteed that the algorithm will not be worse than this.
• Sometimes we are interested in average case. But there are
some problems with the average case.
• It is difficult to figure out the average case. i.e. what is average
input?
• Are we going to assume all possible inputs are equally likely?
• In fact for most algorithms average case is same as the worst case.
 Mergesort

• Mergesort algorithm is one of two important divide-and-conquer

sorting algorithms (the other one is quicksort).
• It is a recursive algorithm.
• Divides the list into halves,
• Sort each halve separately, and
• Then merge the sorted halves into one sorted array.
 Merge sort
We now turn our attention to using a divide and conquer strategy as a way to
improve the performance of sorting algorithms. The first algorithm we will study is
the merge sort. Merge sort is a recursive algorithm that continually splits a list in
half. If the list is empty or has one item, it is sorted by definition (the base case). If
the list has more than one item, we split the list and recursively invoke a merge sort
on both halves. Once the two halves are sorted, the fundamental operation, called
a merge, is performed. Merging is the process of taking two smaller sorted lists
and combining them together into a single, sorted, new list.
 the figure shows our
familiar example list as it
is being split by merge
Sort.

Visualize the Bubble Sort:

https://visualgo.net/en/sorting

the figure shows the

simple lists, now sorted,
as they are merged
back together.
The mergeSort function begin
s by asking the base case
question. If the length of the
list is less than or equal to
one, then we already have a
sorted list and no more
processing is necessary. If, on
the other hand, the length is
greater than one, then we
extract the left and right
halves. It is important to note
that the list may not have an
even number of items. That
does not matter, as the
lengths will differ by at most
one.
 Merge
Once the mergeSort function is
invoked on the left half and the
right half (lines 8–9), it is
assumed they are sorted. The
rest of the function (lines 11–31)
is responsible for merging the
two smaller sorted lists into a
larger sorted list. Notice that the
merge operation places the items
back into the original list (alist)
one at a time by repeatedly
taking the smallest item from the
sorted lists.

Press here to see

the run
Step by step
 Merge (cont.)
The mergeSort function has been
augmented with a print statement
(line 2) to show the contents of
the list being sorted at the start of
each invocation. There is also
a print statement (line 32) to
show the merging process. The
transcript shows the result of
executing the function on our
example list. Note that the list
with 44, 55, and 20 will not divide
evenly. The first split gives [44]
and the second gives [55,20]. It is
easy to see how the splitting
process eventually yields a list
that can be immediately merged
with other sorted lists.
Mergesort - Example
Mergesort – Example2
 Mergesort – Analysis of Merge
In order to analyze the mergeSort function, we need to consider the two distinct
processes that make up its implementation. First, the list is split into halves. We
already computed (in a binary search) that we can divide a list in half logn times
where n is the length of the list. The second process is the merge. Each item in the
list will eventually be processed and placed on the sorted list. So the merge
operation which results in a list of size n requires n operations. The result of this
analysis is that logn splits, each of which costs n for a total of n logn operations. A
merge sort is an O(n logn) algorithm.

Recall that the slicing operator is O(k) where k is the size of the slice. In order to
guarantee that mergeSort will be O(nlogn) we will need to remove the slice
operator. Again, this is possible if we simply pass the starting and ending indices
along with the list when we make the recursive call. We leave this as an exercise.
It is important to notice that the mergeSort function requires extra space to hold the
two halves as they are extracted with the slicing operations. This additional space
can be a critical factor if the list is large and can make this sort problematic when
working on large data sets.
 Quicksort
The quick sort uses divide and conquer to gain the same
advantages as the merge sort, while not using additional storage. As
a trade-off, however, it is possible that the list may not be divided in
half. When this happens, we will see that performance is diminished.
A quick sort first selects a value, which is called the pivot value.
Although there are many different ways to choose the pivot value, we
will simply use the first item in the list. The role of the pivot value is to
assist with splitting the list. The actual position where the pivot value
belongs in the final sorted list, commonly called the split point, will
be used to divide the list for subsequent calls to the quick sort.
 Quicksort
Visualize the Bubble Sort:
(How it works) https://visualgo.net/en/sorting

The following figure shows that 54 will serve as our first pivot value. Since we
have looked at this example a few times already, we know that 54 will
eventually end up in the position currently holding 31. The partition process
will happen next. It will find the split point and at the same time move other
items to the appropriate side of the list, either less than or greater than the
pivot value.
 Quicksort
(How it works)
Partitioning begins by locating
two position markers—let’s call
them leftmark and rightmark—at
the beginning and end of the
remaining items in the list
(positions 1 and 8 in the
following figure).

The goal of the partition process

is to move items that are on the
wrong side with respect to the
pivot value while also
converging on the split
point. The figure shows this
process as we locate the
position of 54.
 Quicksort
We begin by incrementing leftmark until we locate a value that is greater than the
pivot value. We then decrement rightmark until we find a value that is less than the
pivot value. At this point we have discovered two items that are out of place with
respect to the eventual split point. For our example, this occurs at 93 and 20. Now
we can exchange these two items and then repeat the process again.
At the point where rightmark becomes less than leftmark, we stop.
The position of rightmark is now the split point. The pivot value can be exchanged
with the contents of the split point and the pivot value is now in place (see the
following figure). In addition, all the items to the left of the split point are less than
the pivot value, and all the items to the right of the split point are greater than the
pivot value. The list can now be divided at the split point and the quick sort can be
invoked recursively on the two halves.
 Quicksort
The quickSort function invokes
a recursive
function, quickSortHelper.
quickSortHelper begins with the
same base case as the merge
sort. If the length of the list is
less than or equal to one, it is
already sorted. If it is greater,
then it can be partitioned and
recursively sorted.
The partition function
implements the process
described earlier.

Press here to see the

run
Step by step
 Quicksort – Analysis
Worst Case: (assume that we are selecting the first element as pivot)
• The pivot divides the list of size n into two sublists of sizes 0 and
n-1.
• The number of key comparisons
= n-1 + n-2 + ... + 1
= n2/2 – n/2 ➔ O(n2)
• The number of swaps =
= n-1 + n-1 + n-2 + ... + 1
swaps outside of the for loop swaps inside of the for loop
= n2/2 + n/2 - 1 ➔ O(n2)
• So, Quicksort is O(n2) in worst case
 Quicksort – Analysis
• Quicksort is O(n*log2n) in the best case and average
case.
• Quicksort is slow when the array is sorted and we
choose the first element as the pivot.
• Although the worst case behavior is not so good, its
average case behavior is much better than its worst
case.
• So, Quicksort is one of best sorting algorithms using key
comparisons.
 QuickSort-Analysis: summary
To analyze the quickSort function, note that for a list of length n, if
the partition always occurs in the middle of the list, there will again
be logn divisions. In order to find the split point, each of the n items
needs to be checked against the pivot value. The result is nlogn. In
addition, there is no need for additional memory as in the merge
sort process.
Unfortunately, in the worst case, the split points may not be in the
middle and can be very skewed to the left or the right, leaving a
very uneven division. In this case, sorting a list of n items divides
into sorting a list of 0 items and a list of n−1 items. Then sorting a
list of n−1 divides into a list of size 0 and a list of size n−2, and so
on. The result is an O(n2) sort with all of the overhead that recursion
requires.
Comparison of Sorting Algorithms
Thank You