Data structures and Algorithms

Course Code: CoSc-2083

Chapter 7: Advanced Sorting Algorithms

7.1. Shell Sort

Shell sort is an improvement of insertion sort. It is developed by Donald Shell in 1959. Insertion
sort works best when the array elements are sorted in a reasonable order. Thus, shell sort first
creates this reasonable order.
Algorithm:
1. Choose gap gk between elements to be partly ordered.
2. Generate a sequence (called increment sequence) gk, gk-1,…., g2, g1 where for each
sequence gi, A[j]<=A[j+gi] for 0<=j<=n-1-gi and k>=i>=1

It is advisable to choose gk =n/2 and gi-1 = gi/2 for k>=i>=1. After each sequence gk-1 is done and
the list is said to be gi-sorted. Shell sorting is done when the list is 1-sorted (which is sorted using
insertion sort) and A[j]<=A[j+1] for 0<=j<=n-2. Time complexity is O(n3/2).

Example: Sort the following list using shell sort algorithm.

5 8 2 4 1 3 9 7 6 0

Choose g3 =5 (n/2 where n is the number of elements =10)

Sort (5, 3) 3 8 2 4 1 5 9 7 6 0
Sort (8, 9) 3 8 2 4 1 5 9 7 6 0
Sort (2, 7) 3 8 2 4 1 5 9 7 6 0
Sort (4, 6) 3 8 2 4 1 5 9 7 6 0
Sort (1, 0) 3 8 2 4 0 5 9 7 6 1
 5- sorted list 3 8 2 4 0 5 9 7 6 1
Choose g2 =3
Sort (3, 4, 9, 1) 1 8 2 3 0 5 4 7 6 9
Sort (8, 0, 7) 1 0 2 3 7 5 4 8 6 9
Sort (2, 5, 6) 1 0 2 3 7 5 4 8 6 9
 3- sorted list 1 0 2 3 7 5 4 8 6 9

Choose g1 =1 (the same as insertion sort algorithm)

Sort (1, 0, 2, 3, 7, 5, 4, 8, 6, 9) 0 1 2 3 4 5 6 7 8 9
 1- sorted (shell sorted) list 0 1 2 3 4 5 6 7 8 9

Prepared by Department of Computer Science

Page 1
7.2. Quick Sort

Quick sort is the fastest known algorithm. It uses divide and conquer strategy and in the worst
case its complexity is O (n2). But its expected complexity is O(nlogn).
Algorithm:
1. Choose a pivot value (mostly the first element is taken as the pivot value)
2. Position the pivot element and partition the list so that:
 the left part has items less than or equal to the pivot value
 the right part has items greater than or equal to the pivot value
3. Recursively sort the left part
4. Recursively sort the right part

The following algorithm can be used to position a pivot value and create partition.

Left=0;
Right=n-1; // n is the total number of elements in the list
PivotPos=Left;
while(Left<Right)
{
if(PivotPos==Left)
{
if(Data[Left]>Data[Right])
{
swap(data[Left], Data[Right]);
PivotPos=Right;
Left++;
}
else
Right--;
}
else
{
if(Data[Left]>Data[Right])
{
swap(data[Left], Data[Right]);
PivotPos=Left;
Right--;
}
else
Left++;
}
}

Prepared by Department of Computer Science

Page 2
Example: Sort the following 0 3 2 4 1 5 9 7 6 8
list using quick sort
5 8 2 algorithm.
4 1 3 9 7 6 0 Left Right
Pivot
5 8 2 4 1 3 9 7 6 0 0 3 2 4 1 5 9 7 6 8

Left Right Left Right Left Right

Pivot Pivot Pivot
0 8 2 4 1 3 9 7 6 5 0 3 2 4 1 5 8 7 6 9

Left Right Left Right Left Right

Pivot Pivot Pivot
0 5 2 4 1 3 9 7 6 8 0 3 2 4 1 5 8 7 6 9

Left Right Left Right Left Right

Pivot Pivot Pivot
0 5 2 4 1 3 9 7 6 8 0 3 2 4 1 5 8 7 6 9

Left Right Left Right Left Right

Pivot Pivot Pivot
0 5 2 4 1 3 9 7 6 8 0 3 2 4 1 5 6 7 8 9

Left Right Left Right Left Right

Pivot Pivot Pivot
0 5 2 4 1 3 9 7 6 8 0 1 2 4 3 5 6 7 8 9

Left Right Left Right Left Right

Pivot Pivot Pivot
0 5 2 4 1 3 9 7 6 8 0 1 2 4 3 5 6 7 8 9

Left Right Left Right

Pivot Pivot
0 5 2 4 1 3 9 7 6 8 0 1 2 3 4 5 6 7 8 9

Left Right Left Right

Pivot Pivot
0 3 2 4 1 5 9 7 6 8 0 1 2 3 4 5 6 7 8 9

Left Right Left Right

Pivot
Pivot
0 3 2 4 1 5 9 7 6 8 0 1 2 3 4 5 6 7 8 9

Left Right
Pivot

Prepared by Department of Computer Science

Page 3
 7.3. Heap Sort

Heap sort operates by first converting the list in to a heap tree. Heap tree is a binary tree in which
each node has a value greater than both its children (if any). It uses a process called "adjust to
accomplish its task (building a heap tree) whenever a value is larger than its parent. The time
complexity of heap sort is O(nlogn).

Algorithm:
1. Construct a binary tree
 The root node corresponds to Data[0].
 If we consider the index associated with a particular node to be i, then the left child of
this node corresponds to the element with index 2*i+1 and the right child corresponds
to the element with index 2*i+2. If any or both of these elements do not exist in the
array, then the corresponding child node does not exist either.
2. Construct the heap tree from initial binary tree using "adjust" process.
3. Sort by swapping the root value with the lowest, right most value and deleting the lowest,
right most value and inserting the deleted value in the array in it proper position.

Example: Sort the following list using heap sort algorithm.

5 8 2 4 1 3 9 7 6 0

Construct the initial binary tree Construct the heap tree

RootNodePtr RootNodePtr
5 9

8 2 8 5

4 1 3 9 7 1 3 2

7 6 0 4 6 0

Swap the root node with the lowest, right most nodes and delete the lowest, right most value;
insert the deleted value in the array in its proper position; adjust the heap tree; and repeat this
process until the tree is empty.

RootNodePtr RootNodePtr
9 0
9
8 5 8 5

7 1 3 2 7 1 3 2

4 6 0 4 6

Prepared by Department of Computer Science

Page 4
 RootNodePtr RootNodePtr
8 0
8 9
7 5 7 5

6 1 6 1 3 2
3 2

4 4
0

RootNodePtr RootNodePtr
7 0
7 8 9
6 5 6 5

4 1 3 2 4 1 3 2

0
RootNodePtr
RootNodePtr
2
6 6 7 8 9
4 5
4 5

0 1 3
0 1 3 2

RootNodePtr RootNodePtr
5 2
5 6 7 8 9
4 3 4 3

0 1 2 0 1

RootNodePtr RootNodePtr
4 4 5 6 7 8 9 1

2 3 2 3

0 1 0
RootNodePtr RootNodePtr
3 0

2 1 2 1
Prepared by Department of Computer Science
Page 5
0
 3 4 5 6 7 8 9

RootNodePtr
RootNodePtr
2 2 3 4 5 6 7 8 9 1
0 1 0

RootNodePtr
RootNodePtr
1 1 2 3 4 5 6 7 8 9 0
0

RootNodePtr 0 1 2 3 4 5 6 7 8 9 RootNodePtr
0

Prepared by Department of Computer Science

Page 6
7.4. Merge Sort
Like quick sort, merge sort uses divide and conquer strategy and its time complexity is O(nlogn).

Algorithm:
1. Divide the array in to two halves.
2. Recursively sort the first n/2 items.
3. Recursively sort the last n/2 items.
4. Merge sorted items (using an auxiliary array).

Example: Sort the following list using merge sort algorithm.

5 8 2 4 1 3 9 7 6 0
5 8 2 4 1 3 9 7 6 0

5 8 2 4 1 3 9 7 6 0

Division phase
5 8 2 4 1 3 9 7 6 0

5 8 2 4 1 3 9 7 6 0

4 1 6 0

1 4 0 6

5 8 1 2 4 3 9 0 6 7
Sorting and merging phase

1 2 4 5 8 0 3 6 7 9

0 1 2 3 4 5 6 7 8 9

Prepared by Department of Computer Science

Page 7