Subject Code : KCS-301 Programme: [Link].

Subject Name : Data Structure Branch: CSE

Semester: III

Name: Sanjiv Kumar Singh

Designation: Assistant. Professor
Department: Computer Science & Engineering
[Link]/glbgoi [Link]
[Link]
Sorting
 Sorting is a process in which records are arranged in
ascending or descending order

1 2 3 4 5 6

77 42 35 12 101 5

1 2 3 4 5 6

5 12 35 42 77 101
Sorting
Classification

Sorting

Internal External

insertion selection Exchange

Types of Sorting
 Selection Sort
 Insertion Sort
 Bubble Sort
 Merge Sort
 Quick Sort
 Heap Sort
 Shell Sort
 Radix Sort
 Bucket Sort
 Counting Sort
Selection Sort
Selection sort is a sorting algorithm which works as
follows:

 Based upon the extension of the min/max

technique
 Find the minimum value in the list
 Swap it with the value in the first position
 Repeat the steps above for remainder of the list
(starting at the second position)
 It is an in-place comparison sort technique
 Inefficient for large lists
Example: Selection Sort
 26 33 43 100 46 88 52 17 53 77
 17 | 33 43 100 46 88 52 26 53 77
 17 26 | 43 100 46 88 52 33 53 77
 17 26 33 | 100 46 88 52 43 53 77
 17 26 33 43 | 46 88 52 100 53 77
 17 26 33 43 46 | 88 52 100 53 77
 17 26 33 43 46 52 | 88 100 53 77
 17 26 33 43 46 52 53 | 100 88 77
 17 26 33 43 46 52 53 77 | 88 100
 17 26 33 43 46 52 53 77 88 | 100
Selection Sort
Selection_Sort(A,n)
{
for (i=1 to n-1)
{
min= A[i]
loc= i
for (j= i+1 to n)
{
if A[j]< min
{
min= A[j]
loc= j
} //end of if condition
} //end of inner for loop
temp= A[i]
A[i]= min
A[loc]= temp
} //end of outer for loop
} //end of Selection_Sort function
Insertion Sort
Insertion Sort
 In insertion sort, each successive element in the
array to be sorted is inserted into its proper place in
already sorted part.

 We divide our array in a sorted and an unsorted array.

 Initially the sorted portion contains only one

element: the first element in the array.

 We take the second element in the array, and put it

into its correct place.
Insertion Sort
 It is efficient for small list or for mostly sorted list.

 It is expensive requiring shifting all the elements

one by one.

 Shall sort is another variant of insertion sort that

is more efficient for larger list.
Insertion Sort
 That is, array[1] and array[2] are in order with
respect to each other.
 Then the value in array[3] is put into its proper
place, so array [1]…. array[3] is sorted and so on.

36 36 24 10 6 6
24 24 36 24 10 10
10 10 10 36 24 12
6 6 6 6 36 24
12 12 12 12 12 36
Insertion Sort (Steps)
 Our strategy is to search for insertion point from the
beginning of the array and shift the element down to
make room for new element

 We compare the item at array[current] to one before

it, and swap if it is less.

 We then compare array[current-1] to one before it

and swap if necessary.
 Working of the Insertion sort
 It uses two sets of arrays where one stores the sorted data
and other on unsorted data.
 The sorting algorithm works until there are elements in
the unsorted set.
 Let’s assume there are ‘n’ number elements in the array.
Initially, the element with index 1 (LB = 1) exists in the
sorted set. Remaining elements are in the unsorted
partition of the list.
 The first element of the unsorted portion has array index 2
(If LB = 1).
 After each iteration, it chooses the first element of the
unsorted partition and inserts it into the proper place in
the sorted set.
Example: Insertion Sort
 99 | 55 4 66 28 31 36 52 38 72
 55 99 | 4 66 28 31 36 52 38 72
 4 55 99 | 66 28 31 36 52 38 72
 4 55 66 99 | 28 31 36 52 38 72
 4 28 55 66 99 | 31 36 52 38 72
 4 28 31 55 66 99 | 36 52 38 72
 4 28 31 36 55 66 99 | 52 38 72
 4 28 31 36 52 55 66 99 | 38 72
 4 28 31 36 38 52 55 66 99 | 72
 4 28 31 36 38 52 55 66 72 99 |
 Insertion Sort Algorithm
Insertion_Sort(A,n)
{
for( j= 2 to n )
{
i= j-1
key= A[j]
while (i>0 && A[i]> key)
{
A[i+1]= A[i]
i= i-1
} //end of while loop
A[i+1]= key
} //end of forloop
} //end of Insertion_Sort function
Bubble Sort
• Bubble sort is similar to selection sort in the sense that it
repeatedly finds the largest/smallest value in the
unprocessed portion of the array and puts it back.
• However, finding the largest value is not done by selection
this time.
• We "bubble" up the largest value instead.
• Compares adjacent items and exchanges them if they are
out of order.
• Comprises of several passes.
• In one pass, the largest value has been “bubbled” to its
proper position.
• In second pass, the last value does not need to be
compared.
Bubble Sort
 Traverse a collection of elements
 Move from the front to the end
 “Bubble” the largest value to the end using pair-wise
comparisons and swapping

1 2 3 4 5 6

77 42 35 12 101 5
Bubble Sort
 Traverse a collection of elements
 Move from the front to the end
 “Bubble” the largest value to the end using pair-wise
comparisons and swapping

1 2 3 4 5 6

7742 Swap 4277 35 12 101 5

Bubble Sort
 Traverse a collection of elements
 Move from the front to the end
 “Bubble” the largest value to the end using pair-wise
comparisons and swapping

1 2 3 4 5 6

42 77 35 Swap 3577 12 101 5

Bubble Sort
 Traverse a collection of elements
 Move from the front to the end
 “Bubble” the largest value to the end using pair-wise
comparisons and swapping

1 2 3 4 5 6

42 35 7712 Swap 1277 101 5

Bubble Sort
 Traverse a collection of elements
 Move from the front to the end
 “Bubble” the largest value to the end using pair-wise
comparisons and swapping

1 2 3 4 5 6

42 35 12 77 101 5

No need to swap
Bubble Sort
 Traverse a collection of elements
 Move from the front to the end
 “Bubble” the largest value to the end using pair-wise
comparisons and swapping

1 2 3 4 5 6

42 35 12 77 101 Swap 5
5 101
Bubble Sort
 Traverse a collection of elements
 Move from the front to the end
 “Bubble” the largest value to the end using pair-wise
comparisons and swapping

1 2 3 4 5 6

42 35 12 77 5 101

Largest value correctly placed

Items of Interest
 Notice that only the largest value is correctly
placed
 All other values are still out of order
 So we need to repeat this process

1 2 3 4 5 6

42 35 12 77 5 101

Largest value correctly placed

“Bubbling” All the Elements
1 2 3 4 5 6

42 35 12 77 5 101

1 2 3 4 5 6

35 12 42 5 77 101

1 2 3 4 5 6
N-1

12 35 5 42 77 101

1 2 3 4 5 6

12 5 35 42 77 101

1 2 3 4 5 6

5 12 35 42 77 101
Bubble Sort Algorithm
Bubble_Sort(A,n)
{
for(i=1 to n-1)
{
for(j=1 to n-i)
{
if(A[j]>A[j+1)
{
temp= A[j]
A[j]= A[j+1]
A[j+1]= temp
} //end of if condition
} //end of inner for loop
} //end of outer for loop
 Insertion Sort

Selection Sort

Bubble Sort
Summary
 The insertion sort is a good middle-of-the-road
choice for sorting lists of a few thousand items or less.

 The insertion sort is over twice as fast as the bubble

sort and almost 40% faster than the selection sort.

 The insertion sort shouldn't be used for sorting lists

larger than a couple thousand items or repetitive
sorting of lists larger than a couple hundred items.
Divide and Conquer
 Divide and Conquer cuts the problem in half
each time, but uses the result of both halves:
 cut the problem in half until the problem is trivial
 solve for both halves
 combine the solutions
Mergesort
 A divide-and-conquer algorithm:
 Divide the unsorted array into 2 halves until the
sub-arrays only contain one element
 Merge the sub-problem solutions together:
 Compare the sub-array’s first elements
 Remove the smallest element and put it into the
result array
 Continue the process until all elements have
been put into the result array

37 23 6 89 15 12 2 19
 Merge Sort
Mid = (0+6)/2 = 3

Mid = (0+3)/2 = 1 Mid = (4+6)/2 = 5

Mid = (0+1)/2 = 0
Mid = (4+5)/2 = 4
Mid = (2+3)/2 = 2
98 23 45 14 6 67 33 42
 98 23 45 14 6 67 33 42 Mid = (0+7)/2 = 3

Mid = 1 98 23 45 14 6 67 33 42
Mid = 5
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Mid = 1 Mid = 5

98 23 45 14
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23
Mid = 0
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23

23

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23

23 98

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23 45 14

23 98
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23 45 14

23 98

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23 45 14

23 98 14

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23 45 14

23 98 14 45

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23 45 14

23 98 14 45

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23 45 14

23 98 14 45

14

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23 45 14

23 98 14 45

14 23

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23 45 14

23 98 14 45

14 23 45

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23 45 14

23 98 14 45

14 23 45 98

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42 Mid = 5

98 23 45 14 6 67 33 42

98 23 45 14

23 98 14 45

14 23 45 98
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67
Mid = 4

Mid = 6
23 98 14 45

14 23 45 98
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67

23 98 14 45

14 23 45 98 Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67

23 98 14 45 6

14 23 45 98 Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67

23 98 14 45 6 67

14 23 45 98 Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67

14 23 45 98
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67

14 23 45 98 Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33

14 23 45 98 Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

6 14

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

6 14 23

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

6 14 23 33

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

6 14 23 33 42

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

6 14 23 33 42 45

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

6 14 23 33 42 45 67

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

6 14 23 33 42 45 67 98

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

6 14 23 33 42 45 67 98
98 23 45 14 6 67 33 42

6 14 23 33 42 45 67 98
Merge Sort Algorithm
Merge_Sort(A,first,last)
{
d= last-first+1
if(d<= 1)
exit;
if(first<last)
{
mid= (first+last)/2
Merge_Sort(A,first,mid)
Merge_Sort(A,mid+1,last)
Merge(A,first,mid,last)
} // end of if
} // end of Merge_Sort function
Merge(A,first,mid,last)
{
i=first, j=mid+1, k=first
while(i<= mid && j<= last)
{
if(A[i]< A[j])
{
temp[k]= A[i]
i++
} //end of if
else
{
temp[k]= A[j]
j++
} //end of else
k++
} // end of while loop
 while(i<= mid)
{
temp[k]= A[i]
i++
k++
} //end of while loop
while(j<= last)
{
temp[k]= A[j]
j++
k++
} //end of while loop
for (i= first to last)
{
A[i]= temp[i]
} //end of for loop
} // end of Merge function
Quicksort
▪ Quick sort is a divide and conquer algorithm.
▪ Quick sort first divides a large list into two smaller
sub list.
▪ Quick sort can then recursively sort the sub-lists.

partition_1 pivot partition_2

values<pivot values>pivot
Quicksort / partition-exchange sort

The steps are:

1. Pick an element, called a pivot, from the list.

2. Reorder the list so that all elements with values less than
the pivot come before the pivot, while all elements with
values greater than the pivot come after it (equal values can
go either way). After this partitioning, the pivot is in its
final position. This is called the partition operation.

3. Recursively apply the above steps to the sub-list of

elements with smaller values and separately the sub-list of
elements with greater values.
Tot
al %age
11
4 36. 36

1 9. 09

6 54. 55

4 36. 36

4 36. 36

1 9. 09

4 36. 36

7 63. 64

5 45. 45

0 0. 00

3 27. 27

0 0. 00

0 0. 00

4 36. 36

3 27. 27

5 45. 45

6 54. 55

1 1 1 00.
0 0

2 1 8. 1 8

0 0. 00

1 0 90. 91

1 9. 09

3 27. 27

8 72. 73

4 36. 36

5 45. 45

5 45. 45

0 0. 00

0 0. 00

9 81 . 82

0 0. 00

8 72. 73

2 1 8. 1 8

5 45. 45

9 81 . 82

1 1 1 00.
0
0

0 0. 00

1 9. 09

9 81 . 82

4 36. 36

3 27. 27

2 1 8. 1 8

6 54. 55

0 0. 00

8 72. 73

2 1 8. 1 8

1 9. 09

0 0. 00

0 0. 00

2 1 8. 1 8

1 9. 09

1 9. 09

0 0. 00

0 0. 00

1 9. 09

4 36. 36

1 9. 09

7 63. 64

2 1 8. 1 8

3 27. 27

0 0. 00

0 0. 00

4 36. 36

2 1 8. 1 8

1 1 1 00.
0 0

0 0. 00

0 0. 00

0 0. 00

2 1 8. 1 8

4 36. 36

2 1 8. 1 8

4 36. 36

7 63. 64

0 0. 00

3 27. 27

0 0. 00

6 54. 55

3 27. 27

5 45. 45

1 1 1 00.
0
0

0 0. 00

0 0. 00

5 45. 45

8 72. 73

1 1 1 00.
0
0

9 81 . 82

0 0. 00

0 0
 Example
Index 1 2 3 4 5 6 7 8 9
Ele 55 44 99 77 11 88 33 22 66
Key low high

Ele 55 44 99 77 11 88 33 22 66
Key low Exchange high

Ele 55 44 22 77 11 88 33 99 66
Key Low Exchange high

Ele 55 44 22 33 11 88 77 99 66
Key Low high
Index 1 2 3 4 5 6 7 8 9
Ele 55 44 22 33 11 88 77 99 66
Key high Low
Partition Exchange

Ele 11 44 22 33 55 88 77 66 99
Key high Low

Ele 11 44 22 33 55 66 77 88 99
11 33 22 44 55 66 77 88 99
11 22 33 44 55 66 77 88 99
Quick Sort Algorithm
Heap Sort
A sorting algorithm that works by first organizing
the data to be sorted into a special type of binary tree
called a heap

Procedures on Heap
 Heapify
 Build Heap
 Heap Sort
 Heapify: Heapify picks the largest child key and compare it to the
parent key. If parent key is larger than heapify quits, otherwise it swaps the
parent key with the largest child key. So that the parent is now becomes
larger than its children.

 Build Heap: We can use the procedure 'Heapify' in a bottom-up

fashion to convert an array A[1 . . n] into a heap. Since the elements in the
sub array A[n/2 +1 . . n] are all leaves, the procedure BUILD_HEAP goes
through the remaining nodes of the tree and runs 'Heapify' on each one.
The bottom-up order of processing node guarantees that the sub tree
rooted at children are heap before 'Heapify' is run at their parent.
 Heap Sort: The heap sort algorithm starts by using procedure
BUILD-HEAP to build a heap on the input array A[1 . . n]. Since the
maximum value element of the array stored at the root A[1], it can be put
into its correct final position by exchanging it with A[n] (the last element in
A). If we now discard node n from the heap than the remaining elements
can be made into heap. Note that the new element at the root may violate
the heap property. All that is needed to restore the heap property.
Array Representation of Heaps
 A heap can be stored as an
array A.
 Root of tree is A[1]
 Left child of A[i] = A[2i]
 Right child of A[i] = A[2i + 1]
 Parent of A[i] = A[ i/2 ]
 Heapsize[A] ≤ length[A]

 The elements in the subarray

A[(n/2+1) .. n] are leaves
Heap Sort
 The heapsort algorithm consists of two phases:
- build a heap from an arbitrary array
- use the heap to sort the data

 To sort the elements in the decreasing order, use a min heap

 To sort the elements in the increasing order, use a max heap

19

12 16

1 4 7
Heap Sort Algorithm
Heap_Sort(A,n)
{
BuildHeap(A,n);
for (i=n; i>=2; i--)
{
t= A[i];
A[i]= A[1];
A[1]= t;
Heapify(A,1,i-1);
}

BuildHeap(A,n)
{
for (i=n/2; i>=1; i--)
Heapify(A,i,n);
}
Heapify(A,i,n)
{
j= 2*i;
item= A[i];
while(j<=n)
{
if (j<n && A[j]< A[j+1])
j++;
if(item>= A[j])
break;
A[j/2]= A[j];
j= j*2;
}
A[j/2]= item;
}
Example: Convert the following array to a heap

16 4 7 1 12 19

Picture the array as a complete binary tree:

16

4 7

1 12 19
 16 16

4 7 4 19

swap

12 19 1 12 7
1

16 19
swap

12 19 12 16

swap

4 7 1 4 7
1
Example of Heap Sort
Take out biggest
19

12 16
Move the last element
to the root

1 4 7

Sorted:
Array A

12 16 1 4 7 19
 7
swap
HEAPIFY()

12 16

1 4

Sorted:
Array A

7 12 16 1 4 19
 16

12 7

1 4

Sorted:
Array A

16 12 7 1 4 19
 Take out biggest
16

Move the last element

to the root

12 7

1 4

Sorted:
Array A

12 7 1 4 16 19
 4

12 7

Sorted:
Array A

4 12 7 1 16 19
 4
swap

HEAPIFY()

12 7

Sorted:
Array A

4 12 7 1 16 19
 12

4 7

Sorted:
Array A

12 4 7 1 16 19
 Take out biggest
12
Move the last
element to the
root
4 7

Sorted:
Array A

4 7 1 12 16 19
 1
swap

4 7

Sorted:
Array A

1 4 7 12 16 19
 7

4 1

Sorted:
Array A

7 4 1 12 16 19
 Take out biggest
7
Move the last
element to the
root
4 1

Sorted:
Array A

1 4 7 12 16 19
 1
swap

HEAPIFY()

Sorted:
Array A

4 1 7 12 16 19
 Take out biggest
Move the last 4
element to the
root

Sorted:
Array A

1 4 7 12 16 19
 Take out biggest
1

Sorted:
Array A

1 4 7 12 16 19
Time Analysis
 Build Heap function will run in O(n) time
 Heapify function will run in O(log n) time
 There are n-1 calls to Heapify each call requires O(log n)
time
 Heap sort program combine Build Heap program and
Heapify, therefore it has the running time of O(n log n)
time
 Total time complexity: O(n log n)
Comparison with Quick Sort and Merge Sort
 Quick sort is typically somewhat faster, due to better cache
behavior and other factors, but the worst-case running time
for quick sort is O (n2), which is unacceptable for large data
sets and can be deliberately triggered given enough knowledge
of the implementation, creating a security risk.

 The quick sort algorithm also requires Ω (log n) extra storage

space, making it not a strictly in-place algorithm. This typically
does not pose a problem except on the smallest embedded
systems, or on systems where memory allocation is highly
restricted. Constant space (in-place) variants of quick sort are
possible to construct, but are rarely used in practice due to
their extra complexity.
Comparison with Quick Sort and Merge Sort (cont)
 Thus, because of the O(n log n) upper bound on heap sort’s
running time and constant upper bound on its auxiliary
storage, embedded systems with real-time constraints or
systems concerned with security often use heap sort.

 Heap sort also competes with merge sort, which has the same
time bounds, but requires Ω(n) auxiliary space, whereas heap
sort requires only a constant amount. Heap sort also typically
runs more quickly in practice. However, merge sort is simpler
to understand than heap sort, is a stable sort, parallelizes
better, and can be easily adapted to operate on linked lists and
very large lists stored on slow-to-access media such as disk
storage or network attached storage. Heap sort shares none of
these benefits; in particular, it relies strongly on random access.
Possible Application
 When we want to know the task that carry the highest
priority given a large number of things to do

 Interval scheduling, when we have a lists of certain task

with start and finish times and we want to do as many
tasks as possible

 Sorting a list of elements that needs and efficient sorting

algorithm
Conclusion
 The primary advantage of the heap sort is its efficiency.
The execution time efficiency of the heap sort is O(n log
n). The memory efficiency of the heap sort, unlike the
other n log n sorts, is constant, O(1), because the heap
sort algorithm is not recursive.
 The heap sort algorithm has two major steps. The first
major step involves transforming the complete tree into a
heap. The second major step is to perform the actual sort
by extracting the largest element from the root and
transforming the remaining tree into a heap.
Linear Sorts
 We will study algorithms that do not depend only
on comparing whole keys to be sorted.

 Counting sort
 Bucket sort
 Radix sort

Linear Sorts 111

 Radix sort
 Radix sort is a sorting technique that sorts the elements by first
grouping the individual digits of the same place value. Then,
sort the elements according to their increasing/decreasing
order.
502 1 5 10 50 == 10 50 1 502 5 == 1 5 502 10 50
== 1 5 10 50 502

 The idea of Radix Sort is to do digit by digit sort starting from

least significant digit to most significant digit.

 The Radix Sort Algorithm

1. Do following for each digit i where i varies from least significant

digit to the most significant digit.
2. Sort input array using according to the i’th digit.
Radix sort
Radix sort time complexity is (d  (n +b ))

where b is the range of a "digit“[base].

n is the total number to perform sorting
& d is the maximum digit in a number.

Linear Sorts 113

 Radix sort- with decimal digits
1 178 910 910 139
2 139 321 321 178
3 326 572 326 294
4 572 294 139 321
5
6
294
321
 326
178
 368
572
 326
368
7 910 368 178 572
8 368 139 294 910
Input list

Sorted list

Linear Sorts 114