Trng Cao ng Cng ngh

Th c

DATA STRUCTURES &

ALGORITHMS
Chapter 4: Sorting Algorithms
Teacher: Van Nguyen
E-mail: vannt@tdc.edu.vn
Phone: 0985537687

Goals
At the end of this chapter you should be able to:
Explain interchange sort and its analysis
Explain insertion sort and its analysis
Explain selection sort and its analysis
Explain bubble sort and its analysis
Explain heapsort and its analysis
Explain merge sort and its analysis
Explain quicksort and its analysis
Demo
Analysis and compare the algorithms

11/26/2014

Data structures and algorithms

Chapter Outline
Introduction to Sorting
Sorting Algorithms
Interchange sort
Insertion sort
Selection sort
Bubble sort
Heapsort
Merge sort
Quicksort
Lab

11/26/2014

Data structures and algorithms

Introduction to Sorting
The Sorting Problem?
Input:
A sequence of n numbers a1, a2, . . . , an
Output:
A permutation (reordering) a1, a2, . . . , an of the input
sequence such that a1 a2 an

11/26/2014

Data structures and algorithms

Introduction to Sorting
What is Sorting?
Sorting: an operation that segregates items into groups according
to specified criterion
EX:
A={3162134590}
A={0112334569}

11/26/2014

Data structures and algorithms

Introduction to Sorting
Why Study Sorting Algorithms?
There are a variety of situations that we can encounter

Do we have randomly ordered keys?

Are all keys distinct?
How large is the set of keys to be ordered?
Need guaranteed performance?

Various algorithms are better suited to some of these

situations

11/26/2014

Data structures and algorithms

Introduction to Sorting
Examples:

Sorting Books in Library (Dewey system)

Sorting Individuals by Height (Feet and
Inches)
Sorting Movies in Blockbuster
(Alphabetical)
Sorting Numbers (Sequential)

11/26/2014

Data structures and algorithms

Introduction to Sorting
Types of Sorting Algorithms

Interchange sort
Insertion sort
Selection sort
Bubble sort
Heap sort
Merge sort
Quick sort

11/26/2014

Data structures and algorithms

Interchange sort Idea

Exchange sorts attempt to improve the
ordering by comparing elements in pairs and
interchanging them if they are not in sorted
order.
This operation is repeated until the table is
sorted.

11/26/2014

Data structures and algorithms

Interchange sort - Algorithms

Step 1 : i = 1; // starting from the first row
Step 2 : j = i+1; // find the rear element i
Step 3 :
While j n do
If a[j]< a[i] Swap(a[i], a[j]);
j = j+1;
Step 4 : i = i+1;
o If i < n: Step 2
o Else if End

11/26/2014

Data structures and algorithms

10

Interchange sort Example

j
2

12
1

15

11/26/2014

Data structures and algorithms

11

Interchange sort Example

j
3

12
2

15

11/26/2014

Data structures and algorithms

12

Interchange sort Example

j
4

12
4

15

11/26/2014

Data structures and algorithms

13

Interchange sort Example

j
5

12
5

15

11/26/2014

Data structures and algorithms

14

Interchange sort Example

12

15

11/26/2014

Data structures and algorithms

15

Interchange sort - Code for Algorithms

template <class Item>
void interchangeSort (Item a[], int N )
{
int i, j;
for (i = 0 ; i < N-1; i++)
for (j = i + 1; j < N ; j++)
if (a[j ] < a[i])
swap (a[i], a[j]);
}

11/26/2014

Data structures and algorithms

16

Interchange sort Analysis

Running time depends on not only the size of the
array but also the contents of the array.
Best-case:
O(n2)
Array is already sorted in ascending order.
Swap will not be executed.
The number of swap: 0
O(1)
The number of key comparisons: n(n-1)/2
O(n2)

11/26/2014

Data structures and algorithms

17

Interchange sort Analysis (cont.)

Worst-case:
O(n2)
Array is in reverse order:
Swap is executed i-1 times, for i = 2,3, , n
The number of moves: n*(n-1)/2
O(n2)
The number of key comparisons: n*(n-1)/2
O(n2)
Average-case: O(n2)
We have to look at all possible initial data
organizations.
So, Interchange Sort is O(n2)

11/26/2014

Data structures and algorithms

18

Insertion sort Idea

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.
11/26/2014

Data structures and algorithms

19

Insertion sort - Algorithms

Step 1: Starting i = 1 // a[0] is ordered
Step 2: x = a[i]. Find the appropriate position pos in
the segment a[0] ... a [i-1] to insert x.
Step 3: Move the segment a[pos] ... a [i-1] to have a
place to put x on.
Step 4: a[pos] = x
Step 5: i = i + 1
o If i<n: go back to step 2.
o Else: STOP!

11/26/2014

Data structures and algorithms

20

Insertion sort - Example

12

15

11/26/2014

Data structures and algorithms

21

Insertion sort - Example

Insert a2 into (1, 2)
1

pos
2

12
2

15

x
11/26/2014

Data structures and algorithms

22

Insertion sort - Example

Insert a3 into (1, 3)
1

pos
3

12
8

15

x
11/26/2014

Data structures and algorithms

23

Insertion sort - Example

Insert a4 into (1, 4)
1

pos
4

58

12

15

x
11/26/2014

Data structures and algorithms

24

Insertion sort - Example

Insert a5 into (1, 5)
1

pos
5

2
1

12

15

x
11/26/2014

Data structures and algorithms

25

Insertion sort - Example

Insert a6 into (1, 6)
1

pos
6

8
6

12

15

x
11/26/2014

Data structures and algorithms

26

Insertion sort - Example

Insert a7 into (1, 7)
1

pos
7

5
4

12

8
15

x
11/26/2014

Data structures and algorithms

27

Insertion sort - Example

Insert a8 into (1, 8)
1

pos
8

12

15

x
11/26/2014

Data structures and algorithms

28

Insertion sort - Example

pos
5

11/26/2014

Data structures and algorithms

12

15

29

Insertion sort - Code for Algorithms

//increase
template <class Item>
void insertionSort(Item a[], int n)
{
int pos;
for (int i = 1; i < n; i++)
{
Item x = a[i];
for (pos=i; pos > 0 && x <= a[pos-1]; pos--)
a[pos] = a[pos-1];
a[pos] = x;
}
}

11/26/2014

Data structures and algorithms

30

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)

11/26/2014

Data structures and algorithms

31

Insertion sort Analysis (cont.)

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)
11/26/2014

Data structures and algorithms

32

Selection sort Idea

The list is divided into two sublists, sorted and unsorted, which
are divided by an imaginary wall.
We find the smallest element from the unsorted sublist and
swap it with the element at the beginning of the unsorted data.
After each selection and swapping, the imaginary wall between
the two sublists move one element ahead, increasing the
number of sorted elements and decreasing the number of
unsorted ones.
Each time we move one element from the unsorted sublist to
the sorted sublist, we say that we have completed a sort pass.
A list of n elements requires n-1 passes to completely rearrange
the data.

11/26/2014

Data structures and algorithms

33

Selection sort Algorithms

Step 1: Starting i = 1
Step 2: Find the smallest element a[min] in the
current range from a[i] to a[N]
Step 3: Swap a[min] and a[i]
Step 4: i = i + 1
o If i <= N-1: go back to step 2
o Else: STOP!

11/26/2014

Data structures and algorithms

34

Selection sort Example

Swap(ai, amin)

Find MinPos(1, 8)
min
1

12

15

11/26/2014

Data structures and algorithms

35

Selection sort Example

Swap(ai, amin)

Find MinPos(2, 8)
1

min
2

12

15

11/26/2014

Data structures and algorithms

36

Selection sort Example

Swap(ai, amin)

Find MinPos(3, 8)
1

min
3

12

15

11/26/2014

Data structures and algorithms

37

Selection sort Example

Swap(ai, amin)

Find MinPos(4, 8)
1

min
4

12

15

11/26/2014

Data structures and algorithms

38

Selection sort Example

Swap(ai, amin)

Find MinPos(5, 8)
1

min
5

12

15

11/26/2014

Data structures and algorithms

39

Selection sort Example

Find MinPos(6, 8)

Swap(ai, amin)
7

15

min
6

12

11/26/2014

Data structures and algorithms

40

Selection sort Example

Swap(ai, amin)

Find MinPos(7, 8)
1

min
7

12

8
15

11/26/2014

Data structures and algorithms

41

Selection sort - Code for Algorithms

template <class Item>
void selectionSort (Item a[], int n)
{
for (int i = 0; i < n-1; i++)
{
int min = i;
for (int j = i+1; j < n; j++)
if (a[j] < a[min]) min = j;
swap(a[i], a[min]);
}
}
template < class Object>
void swap (Object &lhs, Object &rhs)
{
Object tmp = lhs;
lhs = rhs;
rhs = tmp;
}
11/26/2014

Data structures and algorithms

42

Selection sort Analysis

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)

11/26/2014

Data structures and algorithms

43

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)

11/26/2014

Data structures and algorithms

44

Bubble sort Idea

The list is divided into two sublists: sorted and
unsorted.
The smallest element is bubbled from the unsorted
list and moved to the sorted sublist.
After that, the wall moves one element ahead,
increasing the number of sorted elements and
decreasing the number of unsorted ones.
Each time an element moves from the unsorted part
to the sorted part one sort pass is completed.
Given a list of n elements, bubble sort requires up to
n-1 passes to sort the data.
11/26/2014

Data structures and algorithms

45

Bubble sort Algorithms

Step 1: Starting i = 1
Step 2: j = N
While j> i do:
o If a[j] <a[j-1]: swap(a[j], a[j-1])
o j=j-1
Step 3: i = i + 1
o If i <= N-1: go back to step 2.
o Else: STOP!

11/26/2014

Data structures and algorithms

46

Bubble sort Example

j
8

12
1

15

11/26/2014

Data structures and algorithms

47

Bubble sort Example

j
8

12
2

15

11/26/2014

Data structures and algorithms

48

Bubble sort Example

j
8

12
4

15

11/26/2014

Data structures and algorithms

49

Bubble sort Example

j
8

12
5

15

11/26/2014

Data structures and algorithms

50

Bubble sort Example

j
8

12
6

15

11/26/2014

Data structures and algorithms

51

Bubble sort Example

j
8

12
8

15

11/26/2014

Data structures and algorithms

52

Bubble sort Example

j
8

12

15

11/26/2014

Data structures and algorithms

53

Bubble sort - Code for Algorithms

template <class Item>
void bubbleSort (Item a[], int n)
{
for (int i = 0; i < n-1; i++)
for (int j = n - 1; j > i; j--)
if (a[j-1] > a[j])
swap(a[j],a[j-1]);
}

11/26/2014

Data structures and algorithms

54

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)

11/26/2014

Data structures and algorithms

55

Bubble sort Analysis (cont.)

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)

11/26/2014

Data structures and algorithms

56

Heap sort Heap

What is a Heap?
A heap is also known as a priority queue and can be
represented by a binary tree with the following
properties:
Structure property: A heap is a completely filled
binary tree with the exception of the bottom row,
which is filled from left to right
Heap Order property: For every node x in the
heap, the parent of x greater than or equal to the
value of x. (known as a maxHeap).
11/26/2014

Data structures and algorithms

57

Heap sort Heap

53
44

25

15

11/26/2014

21

12

13

18

Data structures and algorithms

58

Heap sort Heap

53
44 25
15 21 13 18

12 5

53

44

25

15

21

13

18

12

10 11

For any node i, the following formulas apply:

The index of its parent = i / 2
Index of left child = 2 * i
Index of right child = 2 * i + 1
11/26/2014

Data structures and algorithms

59

Heap sort Algorithms

Step 1: Build Heap
Step 2: Swap the first element with the
end element, then reduce size of array to
n-1
Step 3: Continue step 1 and 2 until size of
array is 1

11/26/2014

Data structures and algorithms

60

Heap sort Example build heap

12

15

11/26/2014

Data structures and algorithms

61

Heap sort Example build heap

curr
4

12

joint
6

joint
8

15
5

left

11/26/2014

Data structures and algorithms

62

Heap sort Example build heap

curr
2

12

joint
4

joint
5

joint
8

15

left

11/26/2014

Data structures and algorithms

63

Heap sort Example build heap

curr
1

joint
2

joint
3

12

15

left

11/26/2014

Data structures and algorithms

64

Heap sort Example build heap

15

12

11/26/2014

Data structures and algorithms

65

Heap sort Example swap and shift

15

12

2
right

Swap(a1, aright)

11/26/2014

Data structures and algorithms

66

Heap sort Example swap and shift

curr
1

joint
2

joint
3

12

15

right

Shift(a, 1, right)

11/26/2014

Data structures and algorithms

67

Heap sort Example swap and shift

12

15

right
Swap(a1, aright)

11/26/2014

Data structures and algorithms

68

Heap sort Example swap and shift

curr
1

joint
2

joint
3

joint
6

12

15

right

Shift(a, 1, right)

11/26/2014

Data structures and algorithms

69

Heap sort Example swap and shift

12

15

right
Swap(a1, aright)

11/26/2014

Data structures and algorithms

70

Heap sort Example swap and shift

12

15

12

15

11/26/2014

Data structures and algorithms

71

Heap sort - Code for Algorithms

template <class Item>
void Shift (Item a[], int left, int right)
{
int x, curr, joint;
curr = left; joint = 2 * curr + 1
x = a[curr];
while (joint <= right)
{
if (joint < right)
if (a[joint] < a[joint+1])
joint = joint+1;
if (a[joint]<x) break;
a[curr] = a[joint];
curr = joint;
joint = 2 * curr + 1;
}
a[curr] = x;
}
11/26/2014

Data structures and algorithms

72

Heap sort - Code for Algorithms (cont.)

template <class Item>
void CreateHeap (Item a[], int N)
{
int left;
for (left = (N - 1) / 2; left >= 0; left--)
Shift(a, left, N-1);
}

11/26/2014

Data structures and algorithms

73

Heap sort - Code for Algorithms (cont.)

template <class Item>
void HeapSort (Item a[], int N)
{
int
right;
CreateHeap (a, N);
right = N - 1;
while (right > 0)
{
Swap (a[0],a[right]);
right--;
Shift (a,0,right);
}
}

11/26/2014

Data structures and algorithms

74

Heap sort Analysis

Step 1- Build heap, O(n) time complexity
Step 2 and 3 perform n swap and shift operations,
each with O(log(n)) time complexity
total time complexity = O(n log(n))
Pros: fast sorting algorithm, memory efficient,
especially for very large values of n.
Cons: slower of the O(n log(n)) sorting algorithms

11/26/2014

Data structures and algorithms

75

Merge sort Idea

Mergesort algorithm is one of two important divideand-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.

11/26/2014

Data structures and algorithms

76

Merge sort Algorithms

Step 1: Start with k = 1
Step 2: Distribution of array A = a1, a2, , an into
two arrays B, C following:
B= a1, ,ak, a2k+1, , a3k,
C=ak+1, , a2k, a3k+1, , a4k
Step 3: From 2 arrays B, C, we merge each pair
subarray and put into array A.
Step 4: k = k * 2
o If k <n: go back to step 2.
o Else: STOP!
11/26/2014

Data structures and algorithms

77

Merge sort Example

k = 1;
1

12

15

11/26/2014

Data structures and algorithms

78

Merge sort Example

k = 1;
1

12

15

11/26/2014

Data structures and algorithms

79

Merge sort Example

k = 1;
1

12

15

11/26/2014

Data structures and algorithms

80

Merge sort Example

k = 1;
1

12

15

11/26/2014

Data structures and algorithms

81

Merge sort Example

k = 2;
1

12

15

11/26/2014

Data structures and algorithms

82

Merge sort Example

k = 2;
1

12

15

11/26/2014

Data structures and algorithms

83

Merge sort Example

k = 2;
1

12

15

11/26/2014

Data structures and algorithms

84

Merge sort Example

k = 4;
1

12

15

11/26/2014

Data structures and algorithms

85

Merge sort Example

k = 4;
1

12

15

11/26/2014

Data structures and algorithms

86

Merge sort Example

k = 4;
1

12

15

11/26/2014

Data structures and algorithms

87

Merge sort Example

k = 8;
1

12

15

STOP
Only one subarray

11/26/2014

Data structures and algorithms

88

Merge sort Example

12

15

11/26/2014

Data structures and algorithms

89

Merge sort - Code for Algorithms

template <class Item>
int b[MAX], c[MAX], nb, nc;

int min(int a,int b)

{
if (a > b) return b;
else return a;
}
void MergeSort (Item a[], int N)
{
int k;
for (k = 1; k < N; k *= 2)
{
Distribute(a, N, nb, nc, k);
Merge(a, nb, nc, k);
}
}
Data structures and algorithms
11/26/2014

90

Merge sort - Code for Algorithms (cont.)

template <class Item>
void Distribute (Item a[], int
N,
int &nb, int &nc, int k)
{
int i, pa, pb, pc;
pa = pb = pc = 0;
while (pa < N)
{
for (i=0; (pa<N) && (i<k); i++, pa++, pb++)
b[pb] = a[pa];
for (i=0; (pa<N) && (i<k); i++, pa++, pc++)
c[pc] = a[pa];
}
nb = pb; nc = pc;
}
11/26/2014

Data structures and algorithms

91

Merge sort - Code for Algorithms (cont.)

template <class Item>
void Merge (Item a[], int nb, int nc, int k)
{
int pa, pb, pc;
pa = pb = pc = 0;
while ((pb < nb) && (pc < nc))
MergeSubarr (a, nb, nc, pa, pb, pc, k);
while (pb < nb)
a[pa ++] = b[pb++];
while (pc < nc)
a[pa++] = c[pc++];
}

11/26/2014

Data structures and algorithms

92

Merge sort - Code for Algorithms (cont.)

template <class Item>
void MergeSubarr (int a[], int nb, int nc,
int &pa, int &pb, int &pc, int k)
{
int rb, rc;
rb = min (nb, pb + k);
rc = min (nc, pb + k);
while ((pb < rb) && (pc < rc))
if (b[pb] < c[pc])
a[pa++] = b[pb++];
else a[pa++] = c[pc++];
while (pb < rb)
a[pa++] = b[pb++];
while (pc < rc)
a[pa++] = c[pc++];
}

11/26/2014

Data structures and algorithms

93

Merge sort Analysis

Merging two sorted arrays of size k
0

k-1

......

k-1

......

2k-1

......

Best-case:

All the elements in the first array are smaller (or larger) than all the
elements in the second array.
The number of moves: 2k + 2k
The number of key comparisons: k

Worst-case:
The number of moves: 2k + 2k
The number of key comparisons: 2k-1

11/26/2014

Data structures and algorithms

94

Merge sort Analysis (cont.)

2m

2m-1

level 0 : 1 merge (size 2m-1)

2m-1

level 1 : 2 merges (size 2m-2)

level 2 : 4 merges (size 2m-3)

2m-2 2m-2 2m-2 2m-2

.
.
.
.
.
.
level m-1 : 2m-1 merges (size 20)

20

11/26/2014

.................

20

level m

Data structures and algorithms

95

Merge sort Analysis (cont.)

Worst-case
The number of key comparisons:
= 20*(2*2m-1-1) + 21*(2*2m-2-1) + ... + 2m-1*(2*20-1)
= (2m - 1) + (2m - 2) + ... + (2m 2m-1)
( m terms )
= m*2m
= m*2m 2m 1
Using m = log n
= n * log2n n 1
O (n * log2n )
11/26/2014

Data structures and algorithms

96

Merge sort Analysis (cont.)

Mergesort is extremely efficient algorithm with
respect to time.
Both worst case and average cases are O (n * log2n )

But, mergesort requires an extra array whose size

equals to the size of the original array.
If we use a linked list, we do not need an extra array
But, we need space for the links
And, it will be difficult to divide the list into half ( O(n) )

11/26/2014

Data structures and algorithms

97

Quicksort Idea
Like mergesort, Quicksort is also based on
the divide-and-conquer paradigm.
But it uses this technique in a somewhat opposite
manner,
as all the hard work is done before the recursive
calls.
It works as follows:
1. First, it partitions an array into two parts,
2. Then, it sorts the parts independently,
3. Finally, it combines the sorted subsequences by
a simple concatenation.
11/26/2014

Data structures and algorithms

98

Quicksort Idea (cont.)

The quick-sort algorithm consists of the following three
steps:
1. Divide: Partition the list.
To partition the list, we first choose some element from the
list for which we hope about half the elements will come
before and half after. Call this element the pivot.
Then we partition the elements so that all those with values
less than the pivot come in one sublist and all those with
greater values come in another.

2. Recursion: Recursively sort the sublists separately.

3. Conquer: Put the sorted sublists together.
11/26/2014

Data structures and algorithms

99

Quicksort Algorithms
Step 1: If left>=right: STOP
Step 2: Choose any element a[k] is pivot (l k r):
x = a [k]; i = l; j = r;
Step 3: Detect and correct pair of elements a[i], a[j] is the
wrong position:
o Step 3a: while (a [i] <x) i ++;
o Step 3b: while (a [j]> x) j--;
o Step 3c: If i <j Swap(a [i], a [j]);

Step 4: If i <j: Repeat Step 3.

Else: Go to Step 4
Step 5: Quicksort for aleftaj
Step 6: Quicksort for aiaright
11/26/2014

Data structures and algorithms

100

Quicksort Example
Partition
X

i
1

j
8

12

15

right

left

11/26/2014

STOP

STOP

Not less than X

Not greater than X

Data structures and algorithms

101

Quicksort Example
Partition
X

i
2

j
6

12

15

right

left

11/26/2014

STOP

STOP

Not less than X

Not greater than X

Data structures and algorithms

102

Quicksort Example

j
3

i
5

12

15

right

left

11/26/2014

Data structures and algorithms

103

Quicksort Example
Partition
X
1

i
5

j
8

12

15

right

left

11/26/2014

STOP

STOP

Not less than X

Not greater than X

Data structures and algorithms

104

Quicksort Example

j
5

6
left

11/26/2014

Data structures and algorithms

i
6

12

15

right

105

Quicksort Example

12

15

11/26/2014

Data structures and algorithms

106

Quicksort - Code for Algorithms

template <class Item>
void QuickSort (Item a[], int left, int right)
{
int i, j, x;
if (left right) return;
x = a[(left+right) / 2];
i = left; j = right;
while (i < j)
{
while (a[i] < x) i++;
while (a[j] > x) j--;
if (i <= j)
{
Swap (a[i], a[j]);
i++ ; j--;
}
}
QuickSort (a, left, j);
QuickSort (a, i, right);
}
Data structures and algorithms
11/26/2014

107

Quicksort Analysis
Worst Case: (assume that we are selecting the mid 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

= n2/2 + n/2 - 1

swaps inside of the for loop

O(n2)

So, Quicksort is O(n2) in worst case

11/26/2014

Data structures and algorithms

108

Quicksort Analysis (cont.)

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.

11/26/2014

Data structures and algorithms

109

Question

11/26/2014

Data structures and algorithms

110

QUESTIONS AND EXERCISES

1. Write a method:
public static bool isSorted( int[] array, int n)
that returns true if array is sorted; otherwise it returns false.
2. Write a recursive bubble sort on a double array.
3. Write a recursive insertion sort on a double array.
4. Many operations can be performed faster on sorted than on
unsorted data. For which of the following operations is this the case?
(a) Finding an item with minimum value.
(b) Computing an average of values.
(c) Finding the middle value (the median).
(d) Finding the value that appears most frequently in the data.
(e) Finding the distinct elements of an array.
(f) Finding a value closest to a given value.
(g) Finding whether one word is an anagram(i.e., it contains the same
letters) as another word.
(example:plum and lump)
11/26/2014

Data structures and algorithms

111

QUESTIONS AND EXERCISES (cont.)

5. Class Student have 2 property name and
studentNo. Rewrite some of the sorting methods we
have studied such that each sorts an Object array of
Student objects by name or studentNo.
6. Show the contents of the following integer array:
43, 7, 10, 23, 18, 4, 19, 5, 66, 14
when the array is sorted in ascending order using:
(a) bubble sort, (b) selection sort, (c) insertion sort
(d) Interchange sort, (e) heap sort, (f) merge sort, (g)
quicksort

11/26/2014

Data structures and algorithms

112

QUESTIONS AND EXERCISES (cont.)

7. In our implementation of bubble sort, an array was
scanned bottom-up to bubble up the smallest element.
What modifications are needed to make it work topdown to bubble down the largest element?
8. A cocktail shaker sort is a modification of bubble sort
in which the direction of bubbling changes in each
iteration: In one iteration, the smallest element is
bubbled up; in the next, the largest is bubbled down; in
the next the second smallest is bubbled up; and so
forth. Implement this algorithm.
9. Explain why insertion sort works well on partially
sorted arrays.

11/26/2014

Data structures and algorithms

113

Thank you !

11/26/2014

Data structures and algorithms

114