Complexity and Sorting

Input Algorithm Output

1
Introduction
Sorting data to improve the efficiency with
which it is handled is a common need
◼ Linear search vs Binary search
Efficiency criteria for comparing algorithms in
a quantitative fashion need to be chosen
Common measures are the number of
comparisons that occur and the number of
data movements that take place

3
Introduction
When these values are difficult to determine
exactly, approximations can be used
◼ Experiment to confirm results
These can then be represented using big-O
notation to indicate orders of magnitude
The number of comparisons and number of data
movements don’t apparently coincide
An algorithm may be very efficient in one case,
and perform poorly on the other
So practical considerations have to be taken into
account in choosing the algorithm to use

4
Introduction
While all of our examples involve sorting
elements into increasing (or non-decreasing
with repeats) order for consistency, the
desired order will depend on the application.

5
Insertion Sort
Insertion sort is a simple algorithm that builds the
final sorted list one item at a time
In each iteration the first remaining entry of the input is
removed and inserted into the result at the correct
position
template<class T>
void insertionSort(T data[], int n) {
for (int i = 1, j; i < n; i++) {
T tmp = data[i];
for (j = i; j > 0 && tmp < data[j – 1]; j--){
data[j] = data[j – 1];
data[j] = tmp;
}
}
}
6
Insertion Sort
Recursive solution
template<class T>
void insertionSort(T data[], int n) {
if (n<=1) { return; }
insertionSort(data, n-1);
T tmp = data[n-1];
for (j = n-1; j > 0 && tmp < data[j – 1]; j--){
data[j] = data[j – 1];
}
data[j]=tmp;
}
7
Insertion Sort
Insertion Sort
One important characteristic of the insertion
sort is that it only sorts when necessary
◼ For instance if the array is already sorted, only the
temporary variable is initialized, and that value is
moved back to its original location
Animation for this and other algorithms
◼ https://www.cs.usfca.edu/~galles/visualization/Co
mparisonSort.html

8
Selection Sort
Selection Sort
◼ Selection sort is an in-place comparison sort that
tries to localize the exchange of array elements by
finding an unsorted item and putting it in its final
location
◼ It works by locating the minimum element in the
list and swapping it with the item in the first
location, its correct final position
◼ Then it advances one position and repeats the
process, finding the next smallest element and
moving it to its correct position until it reaches the
end of the list

9
Bubble Sort
Bubble sort is a simple sorting algorithm that
works by repeatedly stepping through the list to
be sorted
On each pass through the list it compares pairs
of adjacent items and swaps them if they are in
the wrong order
The passes through the list are repeated until no
swaps are needed, which indicates that the list is
sorted
The algorithm gets its name from the way
smaller elements "bubble" to the top of the list

10
Bubble Sort
The main disadvantage to bubble sort is the
very process that gives it its name
Each item must be carefully “bubbled” step
by step to the appropriate end of the list
Because it looks at adjacent array elements
to determine if a swap is necessary, if an item
is moved from one end of the list to the
other, it has to be exchanged with every
element of the list

11
Divide-and-Conquer
Divide-and conquer is a Merge-sort is a sorting
general algorithm design algorithm based on the
paradigm: divide-and-conquer
◼ Divide: divide the input data paradigm
S in two (or more) disjoint
subsets S1 and S2
◼ Recur: solve the
subproblems associated
with S1 and S2
◼ Conquer: combine the
solutions for S1 and S2 into a
solution for S
The base case for the
recursion are subproblems of
size 0 or 1

12
Merge-Sort
Merge-sort on an input Algorithm mergeSort(S, C)
sequence S with n Input sequence S with n
elements consists of elements, comparator C
three steps: Output sequence S sorted
◼ Divide: partition S into according to C
two sequences S1 and S2 if S.size() > 1
of about n2 elements (S1, S2)  partition(S, n/2)
each mergeSort(S1, C)
◼ Recur: recursively sort S1 mergeSort(S2, C)
and S2 S  merge(S1, S2)
◼ Conquer: merge S1 and
S2 into a unique sorted
sequence

13
Merging Two Sorted Sequences
The conquer step of merge-sort consists of
merging two sorted sequences A and B into
a sorted sequence S containing the union of
the elements of A and B
Merging two sorted sequences, each with n2
elements takes O(n) time

14
Merge-Sort Tree
An execution of merge-sort is depicted by a binary tree
◼ each node represents a recursive call of merge-sort and stores
 unsorted sequence before the execution and its partition
 sorted sequence at the end of the execution
◼ the root is the initial call
◼ the leaves are calls on subsequences of size 0 or 1

7 29 4 → 2 4 7 9

7  2 → 2 7 9  4 → 4 9

7→7 2→2 9→9 4→4

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 2 9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6

7 2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

16
Execution Example (cont.)
Recursive call, partition

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9 3 8 6 1 → 1 3 8 6

7 2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

17
Execution Example (cont.)
Recursive call, partition

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9 3 8 6 1 → 1 3 8 6

72→2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

18
Execution Example (cont.)
Recursive call, base case

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9 3 8 6 1 → 1 3 8 6

72→2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

19
Execution Example (cont.)
Recursive call, base case

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9 3 8 6 1 → 1 3 8 6

72→2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

20
Execution Example (cont.)
Merge

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9 3 8 6 1 → 1 3 8 6

72→2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

21
Execution Example (cont.)
Recursive call, …, base case, merge

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9 3 8 6 1 → 1 3 8 6

72→2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

22
Execution Example (cont.)
Merge

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9 3 8 6 1 → 1 3 8 6

72→2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

23
Execution Example (cont.)
Recursive call, …, merge, merge

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9 3 8 6 1 → 1 3 6 8

72→2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

24
Execution Example (cont.)
Merge

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9 3 8 6 1 → 1 3 6 8

72→2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

25
Mergesort
The merge process requires a temporary
(working) array to do the merge

26
Quick-Sort
Quick-sort is a randomized
sorting algorithm based x
on the divide-and-conquer
paradigm:
◼ Divide: pick a random
element x (called pivot) and
x
partition S into
 L elements less than x
 E elements equal x L E G
 G elements greater than x
◼ Recur: sort L and G
◼ Conquer: join L, E and G x

27
Quick-Sort Tree
An execution of quick-sort is depicted by a binary tree
◼ Each node represents a recursive call of quick-sort and stores
 Unsorted sequence before the execution and its pivot
 Sorted sequence at the end of the execution
◼ The root is the initial call
◼ The leaves are calls on subsequences of size 0 or 1

7 4 9 6 2 → 2 4 6 7 9

4 2 → 2 4 7 9 → 7 9

2→2 9→9
28
Execution Example
Pivot selection

7 2 9 43 7 6 1 → 1 2 3 4 6 7 8 9

7 2 9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6

2→2 9 4 → 4 9 3→3 8→8

9→9 4→4

29
Execution Example (cont.)
Partition, recursive call, pivot selection

7 2 9 4 3 7 6 1→ 1 2 3 4 6 7 8 9

2 4 3 1→ 2 4 7 9 3 8 6 1 → 1 3 8 6

2→2 9 4 → 4 9 3→3 8→8

9→9 4→4

30
Execution Example (cont.)
Partition, recursive call, base case

7 2 9 43 7 6 1→→ 1 2 3 4 6 7 8 9

2 4 3 1 →→ 2 4 7 3 8 6 1 → 1 3 8 6

1→1 9 4 → 4 9 3→3 8→8

9→9 4→4

31
Execution Example (cont.)
Recursive call, …, base case, join

7 2 9 43 7 6 1→ 1 2 3 4 6 7 8 9

2 4 3 1 → 1 2 3 4 3 8 6 1 → 1 3 8 6

1→1 4 3 → 3 4 3→3 8→8

9→9 4→4

32
Execution Example (cont.)
Recursive call, pivot selection

7 2 9 43 7 6 1→ 1 2 3 4 6 7 8 9

2 4 3 1 → 1 2 3 4 7 9 7 1 → 1 3 8 6

1→1 4 3 → 3 4 8→8 9→9

9→9 4→4

33
Execution Example (cont.)
Partition, …, recursive call, base case

7 2 9 43 7 6 1→ 1 2 3 4 6 7 8 9

2 4 3 1 → 1 2 3 4 7 9 7 1 → 1 3 8 6

1→1 4 3 → 3 4 8→8 9→9

9→9 4→4

34
Execution Example (cont.)
Join, join

7 2 9 4 3 7 6 1 →1 2 3 4 6 7 7 9

2 4 3 1 → 1 2 3 4 7 9 7 → 17 7 9

1→1 4 3 → 3 4 8→8 9→9

9→9 4→4

35
Quicksort
The efficiency depends heavily on choosing a
good pivot value
Often chosen randomly, or just take
first/last/middle element
One simple strategy is to take three elements
and choose the middle value as the pivot

41
References
Goodrich , Michael T. (2011). Data
Structures & Algorithms in C++ 2nd ed. (2nd
ed.). New York: John Wiley & Sons.
Adam Drozdek (2012). Data Structures and
Algorithms in C++ 4th ed. Cengage Learning.