QEEE DSA05
DATA STRUCTURES AND
ALGORITHMS
G VENKATESH AND MADHAVAN MUKUND
LECTURE 3, 8 AUGUST 2014
Sorting
Sorting
Searching for a value
Sorting
Searching for a value
Unsorted array linear scan, O(n)
Sorting
Searching for a value
Unsorted array linear scan, O(n)
Sorted array binary search, O(log n)
Sorting
Searching for a value
Unsorted array linear scan, O(n)
Sorted array binary search, O(log n)
Other advantages of sorting
Sorting
Searching for a value
Unsorted array linear scan, O(n)
Sorted array binary search, O(log n)
Other advantages of sorting
Finding median value: midpoint of sorted list
Sorting
Searching for a value
Unsorted array linear scan, O(n)
Sorted array binary search, O(log n)
Other advantages of sorting
Finding median value: midpoint of sorted list
Checking for duplicates
Sorting
Searching for a value
Unsorted array linear scan, O(n)
Sorted array binary search, O(log n)
Other advantages of sorting
Finding median value: midpoint of sorted list
Checking for duplicates
Building a frequency table of values
How to sort?
You are a Teaching Assistant for a course
The instructor gives you a stack of exam answer
papers with marks, ordered randomly
Your task is to arrange them in descending order
Strategy 1
Strategy 1
Scan the entire stack and find the paper with
minimum marks
Move this paper to a new stack
Strategy 1
Scan the entire stack and find the paper with
minimum marks
Move this paper to a new stack
Repeat with remaining papers
Each time, add next minimum mark paper on
top of new stack
Strategy 1
Scan the entire stack and find the paper with
minimum marks
Move this paper to a new stack
Repeat with remaining papers
Each time, add next minimum mark paper on
top of new stack
Eventually, new stack is sorted in descending
order
Strategy 1
74
32
89
55
21
64
Strategy 1
74
21
32
89
55
21
64
Strategy 1
74
32
21
32
89
55
21
64
Strategy 1
74
32
89
21
32
55
55
21
64
Strategy 1
74
32
89
55
21
32
55
64
21
64
Strategy 1
74
32
89
55
21
21
32
55
64
74
64
Strategy 1
74
32
89
55
21
64
21
32
55
64
74
89
Strategy 1
Selection Sort
Select the next element in sorted order
Move it into its correct place in the final sorted list
Strategy 2
Strategy 2
First paper: put in a new stack
Strategy 2
First paper: put in a new stack
Second paper:
Strategy 2
First paper: put in a new stack
Second paper:
Lower marks than first? Place below first paper
Higher marks than first? Place above first paper
Strategy 2
First paper: put in a new stack
Second paper:
Lower marks than first? Place below first paper
Higher marks than first? Place above first paper
Third paper
Strategy 2
First paper: put in a new stack
Second paper:
Lower marks than first? Place below first paper
Higher marks than first? Place above first paper
Third paper
Insert into the correct position with respect to first
two papers
Strategy 2
First paper: put in a new stack
Second paper:
Lower marks than first? Place below first paper
Higher marks than first? Place above first paper
Third paper
Insert into the correct position with respect to first
two papers
Do this for each subsequent paper:
insert into correct position in new sorted stack
Strategy 2
74
32
89
55
21
64
Strategy 2
74
74
32
89
55
21
64
Strategy 2
74
32
32
74
89
55
21
64
Strategy 2
74
32
32
74
89
89
55
21
64
Strategy 2
74
32
89
55
32
55
74
89
21
64
Strategy 2
74
21
32
32
89
55
55
74
21
89
64
Strategy 2
74
32
89
55
21
64
21
32
55
64
74
89
Strategy 2
Insertion Sort
Start building a sorted sequence with one element
Pick up next unsorted element and insert it into its
correct place in the already sorted sequence
Selection Sort
In an array, move each element to its final location
without using a second list
Move minimum element to first position
Move second minimum element to second
position
Selection Sort
SelectionSort(A,n)
// Sort A of size n
for (startpos = 0; startpos < n; startpos++)
// Scan segments A[0]..A[n-1], A[1]..A[n-1],
minpos = startpos;
for (i = minpos+1; i < n; i++)
if (A[i] < A[minpos])
minpos = i;
// Move minimum element to start of current segment
swap(A,startpos,minpos)
// Locate position of minimum element in current segment
Selection Sort
74
32
89
55
21
64
Selection Sort
74
32
89
55
21
64
Selection Sort
21
32
89
55
74
64
Selection Sort
21
32
89
55
74
64
Selection Sort
21
32
89
55
74
64
Selection Sort
21
32
89
55
74
64
Selection Sort
21
32
55
89
74
64
Selection Sort
21
32
55
89
74
64
Selection Sort
21
32
55
64
74
89
Selection Sort
21
32
55
64
74
89
Selection Sort
21
32
55
64
74
89
Selection Sort
21
32
55
64
74
89
Analysis of Selection Sort
Analysis of Selection Sort
Finding minimum in unsorted segment of length k
requires one scan, k steps
Analysis of Selection Sort
Finding minimum in unsorted segment of length k
requires one scan, k steps
In each iteration, segment to be scanned reduces
by 1
Analysis of Selection Sort
Finding minimum in unsorted segment of length k
requires one scan, k steps
In each iteration, segment to be scanned reduces
by 1
t(n) = n + (n-1) + (n-2) + + 1 = n(n+1)/2 = O(n2)
Alternative calculation
Alternative calculation
t(n), time to run selection sort on length n
Alternative calculation
t(n), time to run selection sort on length n
n steps to find minimum and move to position 0
Alternative calculation
t(n), time to run selection sort on length n
n steps to find minimum and move to position 0
t(n-1) time to run selection sort on A[1] to A[n-1]
Alternative calculation
t(n), time to run selection sort on length n
n steps to find minimum and move to position 0
t(n-1) time to run selection sort on A[1] to A[n-1]
Recurrence
Alternative calculation
t(n), time to run selection sort on length n
n steps to find minimum and move to position 0
t(n-1) time to run selection sort on A[1] to A[n-1]
Recurrence
t(n) = n + t(n-1)
t(1) = 1
Alternative calculation
t(n), time to run selection sort on length n
n steps to find minimum and move to position 0
t(n-1) time to run selection sort on A[1] to A[n-1]
Recurrence
t(n) = n + t(n-1)
t(1) = 1
t(n) = n + t(n-1) = n + ((n-1) + t(n-2)) = =
n + (n-1) + (n-2) + + 1 = n(n+1)/2 = O(n2)
Insertion Sort
InsertionSort(A,n)
// Sort A of size n
for (pos = 1; pos < n; pos++)
// Build longer and longer sorted
segments
// In each iteration A[0]..A[pos-1] is already sorted
// Move first element after sorted segment left
// till it is in the correct place
nextpos = pos
while (nextpos > 0 &&
A[nextpos] < A[nextpos-1])
swap(A,nextpos,nextpos-1)
nextpos = nextpos-1
Insertion Sort
74
32
89
55
21
64
Insertion Sort
74
32
89
55
21
64
Insertion Sort
32
74
89
55
21
64
Insertion Sort
32
74
89
55
21
64
Insertion Sort
32
74
55
89
21
64
Insertion Sort
32
55
74
89
21
64
Insertion Sort
32
55
74
21
89
64
Insertion Sort
32
55
21
74
89
64
Insertion Sort
32
21
55
74
89
64
Insertion Sort
21
32
55
74
89
64
Insertion Sort
21
32
55
74
64
89
Insertion Sort
21
32
55
64
74
89
Analysis of Insertion Sort
Analysis of Insertion Sort
Inserting a new value in sorted segment of length
k requires upto k steps in the worst case
Analysis of Insertion Sort
Inserting a new value in sorted segment of length
k requires upto k steps in the worst case
In each iteration, sorted segment in which to insert
increased by 1
Analysis of Insertion Sort
Inserting a new value in sorted segment of length
k requires upto k steps in the worst case
In each iteration, sorted segment in which to insert
increased by 1
t(n) = 1 + 2 + + n-1 = n(n-1)/2 = O(n2)
Recurrence
Recurrence
t(n), time to run insertion sort on length n
Recurrence
t(n), time to run insertion sort on length n
Time t(n-1) to sort segment A[0] to A[n-2]
Recurrence
t(n), time to run insertion sort on length n
Time t(n-1) to sort segment A[0] to A[n-2]
n-1 steps to insert A[n-1] in sorted segment
Recurrence
t(n), time to run insertion sort on length n
Time t(n-1) to sort segment A[0] to A[n-2]
n-1 steps to insert A[n-1] in sorted segment
Recurrence
Recurrence
t(n), time to run insertion sort on length n
Time t(n-1) to sort segment A[0] to A[n-2]
n-1 steps to insert A[n-1] in sorted segment
Recurrence
t(n) = n-1 + t(n-1)
t(1) = 1
Recurrence
t(n), time to run insertion sort on length n
Time t(n-1) to sort segment A[0] to A[n-2]
n-1 steps to insert A[n-1] in sorted segment
Recurrence
t(n) = n-1 + t(n-1)
t(1) = 1
t(n) = n-1 + t(n-1) = n-1 + ((n-2) + t(n-2)) = =
(n-1) + (n-2) + + 1 = n(n-1)/2 = O(n2)
2
O(n )
sorting algorithms
Selection sort and insertion sort are both O(n2)
So is bubble sort, which we will not discuss here
O(n2) sorting is infeasible for n over 100000
Among O(n2) sorts, insertion sort is usually better
than selection sort and both are better than
bubble sort
What happens when we apply insertion sort to
an already sorted list?
A different strategy?
Divide array in two equal parts
Separately sort left and right half
Combine the two sorted halves to get the full array
sorted
Combining sorted lists
Combining sorted lists
Given two sorted lists A and B, combine into a
sorted list C
Compare first element of A and B
Move it into C
Repeat until all elements in A and B are over
Combining sorted lists
Given two sorted lists A and B, combine into a
sorted list C
Compare first element of A and B
Move it into C
Repeat until all elements in A and B are over
Merging A and B
Merging two sorted lists
32
74
89
21
55
64
Merging two sorted lists
32
74
89
21
55
64
21
Merging two sorted lists
32
74
89
21
55
64
21
32
Merging two sorted lists
32
74
89
21
55
64
21
32
55
Merging two sorted lists
32
74
89
21
55
64
21
32
55
64
Merging two sorted lists
32
74
89
21
55
64
21
32
55
64
74
Merging two sorted lists
32
74
89
21
55
64
21
32
55
64
74
89
Merge Sort
Sort A[0] to A[n/2-1]
Sort A[n/2] to A[n-1]
Merge sorted halves into B[0..n-1]
How do we sort the halves?
Recursively, using the same strategy!
Merge Sort
43
32
22
78
63
57
91
13
Merge Sort
43
43
32
32
22
22
78
78
63
57
91
13
Merge Sort
43
43
32
32
22
22
78
78
63
57
63
91
57
13
91
13
Merge Sort
43
43
43
32
32
32
22
22
22
78
78
78
63
57
63
91
57
13
91
13
Merge Sort
43
43
43
32
32
32
22
22
22
78
78
78
63
57
63
63
91
57
57
13
91
91
13
13
Merge Sort
43
43
43
43
32
32
32
32
22
22
22
78
78
78
63
57
63
63
91
57
57
13
91
91
13
13
Merge Sort
43
43
43
43
32
32
32
32
22
22
22
22
78
78
63
57
63
78
78
63
91
57
57
13
91
91
13
13
Merge Sort
43
43
43
43
32
32
32
32
22
22
22
22
78
78
63
57
63
78
78
63
63
91
57
57
57
13
91
91
13
13
Merge Sort
43
43
43
43
32
32
32
32
22
22
22
22
78
78
63
57
63
78
78
63
63
91
57
57
57
13
91
91
91
13
13
13
Merge Sort
43
43
32
43
32
32
43
32
22
22
22
22
78
78
63
57
63
78
78
63
63
91
57
57
57
13
91
91
91
13
13
13
Merge Sort
43
43
32
43
32
32
43
32
22
22
22
22
78
78
63
57
63
78
78
63
63
91
57
57
57
13
91
91
91
13
13
13
Merge Sort
43
43
32
43
32
32
43
32
22
22
22
22
78
78
63
57
63
78
78
57
63
91
57
63
57
13
91
91
91
13
13
13
Merge Sort
43
43
32
43
32
32
43
32
22
22
22
22
78
78
63
57
63
78
78
57
63
91
57
63
57
13
91
13
91
13
91
13
Merge Sort
43
22
32
43
32
32
43
32
22
43
22
22
78
63
57
63
78
78
78
57
63
91
57
63
57
13
91
13
91
13
91
13
Merge Sort
43
22
32
43
32
32
43
32
22
43
22
22
78
63
57
13
78
78
78
57
63
91
57
63
57
13
63
13
91
91
91
13
Merge Sort
13
22
32
43
22
32
43
32
32
43
22
22
43
57
63
13
78
78
78
57
63
78
57
63
57
91
63
13
91
91
91
13
Divide and conquer
Break up problem into disjoint parts
Solve each part separately
Combine the solutions eciently
Merge Sort code, analysis
Next class
Summary
Selection Sort and Insertion Sort are two methods
that we often use in practical situations
Both are O(n2)
Merge Sort uses a divide and conquer strategy for
sorting
More details of Merge Sort in the next class
