Data Structures and Algorithms – BCA 3rd Semester

Unit-8: Sorting

Introduction:
Sorting is a process of ordering or placing a list of elements from a collection in
some kind of order. It is nothing but storage of data in sorted order. Sorting can be
done in ascending and descending order. It arranges the data in a sequence which
makes searching easier.

There are so many things in our real life that we need to search for, like a particular
record in database, roll numbers in merit list, a particular telephone number in
telephone directory, a particular page in a book etc. All this would have been a
mess if the data was kept unordered and unsorted, but fortunately the concept
of sorting came into existence, making it easier for everyone to arrange data in an
order, hence making it easier to search.

Sorting arranges data in a sequence which makes searching easier.

Following are some of the examples of sorting in real-life scenarios

 Telephone Directory: The telephone directory stores the telephone numbers

of people sorted by their names, so that the names can be searched easily.
 Dictionary: The dictionary stores words in an alphabetical order so that
searching of any word becomes easy.
 Result Ranking: The marks obtained by the student can sorted by
descending order i.e. higher marks in the top of the list.

Some terms are generally coined while discussing sorting techniques, here is a
brief introduction to them

Increasing Order
A sequence of values is said to be in increasing order, if the successive element is
greater than the previous one. For example, 1, 3, 4, 6, 8, 9 are in increasing order,
as every next element is greater than the previous element.

By Sr. Asst. Prof. Pratik Chand, LTU Page 1

 Data Structures and Algorithms – BCA 3rd Semester

Decreasing Order
A sequence of values is said to be in decreasing order, if the successive element is
less than the current one. For example, 9, 8, 6, 4, 3, 1 are in decreasing order, as
every next element is less than the previous element.

Non-Increasing Order
A sequence of values is said to be in non-increasing order, if the successive
element is less than or equal to its previous element in the sequence. This order
occurs when the sequence contains duplicate values. For example, 9, 8, 6, 3, 3, 1
are in non-increasing order, as every next element is less than or equal to (in case
of 3) but not greater than any previous element.

Non-Decreasing Order
A sequence of values is said to be in non-decreasing order, if the successive
element is greater than or equal to its previous element in the sequence. This order
occurs when the sequence contains duplicate values. For example, 1, 3, 3, 6, 8, 9
are in non-decreasing order, as every next element is greater than or equal to (in
case of 3) but not less than the previous one.

Sorting Categories:

The techniques of sorting can be divided into two categories. These are:

 Internal Sorting
 External Sorting

Internal sorting: If the input data is such that it can be adjusted in the main
memory at once, it is called internal sorting.

External sorting: If the input data is such that it cannot be adjusted in the memory
entirely at once, it needs to be stored in a hard disk, floppy disk, or any other
storage device. This is called external sorting.

By Sr. Asst. Prof. Pratik Chand, LTU Page 2

 Data Structures and Algorithms – BCA 3rd Semester

Complexity of Sorting algorithm:

The complexity of sorting algorithm calculates the running time of a function in
which 'n' number of items are to be sorted. The choice for which sorting method is
suitable for a problem depends on several dependency configurations for different
problems. The most noteworthy of these considerations are:

 The length of time spent by the programmer in programming a specific

sorting program
 Amount of machine time necessary for running the program
 The amount of memory necessary for running the program

The Efficiency of Sorting Techniques

To get the amount of time required to sort an array of 'n' elements by a particular
method, the normal approach is to analyze the method to find the number of
comparisons (or exchanges) required by it. Most of the sorting techniques are data
sensitive, and so the metrics for them depends on the order in which they appear in
an input array.

Various sorting techniques are analyzed in various cases and named these cases as
follows:

 Best case
 Worst case
 Average case

Hence, the result of these cases is often a formula giving the average time required
for a particular sort of size 'n.' Most of the sort methods have time requirements
that range from O(n log n) to O(n2)

Big “O” Notation:

Big O notation is a mathematical notation that describes the limiting behavior of a
function when the argument tends towards a particular value or infinity. It is a
member of a family of notations invented by Paul Bachmann, Edmund Landau,
and others, collectively called Bachmann–Landau notation or asymptotic notation.

We can express algorithmic complexity using the big-O notation. For a problem of
size N:
By Sr. Asst. Prof. Pratik Chand, LTU Page 3
 Data Structures and Algorithms – BCA 3rd Semester

 A constant-time function/method is “order 1” : O(1)

 A linear-time function/method is “order N” : O(N)
 A quadratic-time function/method is “order N squared” : O(N2)

Insertion Sort :
 Insertion sort is a simple sorting algorithm.
 This sorting method sorts the array by shifting elements one by one.
 It builds the final sorted array one item at a time.
 This sort is efficient for smaller data sets but it is insufficient for larger lists.
 It has less space complexity like bubble sort.
 It requires single additional memory space.
 Insertion sort does not change the relative order of elements with equal keys
because it is stable.
 Insertion sort works like the way we sort playing cards in our hands. It
always starts with the second element as key. The key is compared with the
elements ahead of it and is put it in the right place.

Time complexity: O(n2)

Algorithm for insertion sort

 Step 1: Start
 Step 2: First element is already sorted
 Step 3: Pick next element
 Step 4: Compare with all elements in the sorted sub-list
 Step 5: Shift all the elements right in the sorted sub-list that is greater than
the value to be sorted
 Step 6: Insert the value
 Step 7: Repeat until list is sorted
 Step 8: Stop

By Sr. Asst. Prof. Pratik Chand, LTU Page 4

 Data Structures and Algorithms – BCA 3rd Semester

Example: Sort the following element in ascending order using Insertion sort

14, 33, 27, 10, 35, 19, 42, 44

Solution:
Compare the first two elements.

It finds that both 14 and 33 are already in ascending order. For now, 14 is in sorted
sub-list.

Insertion sort moves ahead and compares 33 with 27.

And finds that 33 is not in the correct position.

It swaps 33 with 27. It also checks with all the elements of sorted sub-list. Here we
see that the sorted sub-list has only one element 14, and 27 is greater than 14.
Hence, the sorted sub-list remains sorted after swapping.

By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with 10.

These values are not in a sorted order.

So we swap them.

By Sr. Asst. Prof. Pratik Chand, LTU Page 5

 Data Structures and Algorithms – BCA 3rd Semester

However, swapping makes 27 and 10 unsorted.

Hence, we swap them too.

Again we find 14 and 10 in an unsorted order.

We swap them again. By the end of third iteration, we have a sorted sub-list of 4
items.

This process goes on until all the unsorted values are covered in a sorted sub-list.

The final result will be

Shell Sort:
Shell sort is a highly efficient sorting algorithm and is based on insertion sort
algorithm. This algorithm avoids large shifts as in case of insertion sort, if the
smaller value is to the far right and has to be moved to the far left.

This algorithm uses insertion sort on a widely spread elements, first to sort them
and then sorts the less widely spaced elements. This spacing is termed as interval.
This interval is calculated based on Knuth's formula as

By Sr. Asst. Prof. Pratik Chand, LTU Page 6

 Data Structures and Algorithms – BCA 3rd Semester

Interval or Gap Formula

Gap = n/2, n/4, n/8…… n/n (gap is floor value i.e. 9/2=4)

Time Complexity: O(n).

Algorithm for Shell Sort

Step 1: Start

Step 2: Initialize the value of gap

Step 3: Divide the list into smaller sub-list of equal gap

Step 4: Sort these sub-lists using insertion sort

Step 5: Repeat until complete list is sorted

Step 6: Stop

Example: Sort the following data using Shell Sort algorithm

23, 29, 15, 19, 31, 7, 9, 5, 2

Solution:

Here n = 9

New, find the gap

1st pass: gap = n/2, 9/2 = 4

Now the comparison will be at the gap of 4,

Now, compare 23 with 31 and arrange in ascending order by swapping both, here
both value are in ascending order already, so no swapping to be done.

By Sr. Asst. Prof. Pratik Chand, LTU Page 7

 Data Structures and Algorithms – BCA 3rd Semester

Now move the pointer one step forward and compare 29 with 7, here 29 is greater
than 7, so swap will be done

Likewise compare all the elements till last element is reached

Here, 2 will compare with 13, because it is also a gap of 4.

By Sr. Asst. Prof. Pratik Chand, LTU Page 8

 Data Structures and Algorithms – BCA 3rd Semester

Now the 1st pass is completed but data is not in proper sorted order, now we have
to do 2nd pass.

2nd Pass: gap = n/4 = 9/4 = 2

By Sr. Asst. Prof. Pratik Chand, LTU Page 9

 Data Structures and Algorithms – BCA 3rd Semester

3rd Pass: gap = n/n = 9/9 = 1 (it’s like insertion sort)

By Sr. Asst. Prof. Pratik Chand, LTU Page 10

 Data Structures and Algorithms – BCA 3rd Semester

By Sr. Asst. Prof. Pratik Chand, LTU Page 11

 Data Structures and Algorithms – BCA 3rd Semester

Now the final sorted data is

Selection Sort:
Selection sort is a simple sorting algorithm which finds the smallest element in the
array and exchanges it with the element in the first position. Then finds the second
smallest element and exchanges it with the element in the second position and
continues until the entire array is sorted.

Time Complexity: O(n2)

Algorithm for Selection Sort

Step 1: Start

Step 2: Set MIN to location 0

Step 3: Search the minimum element in the unsorted list

Step 4: Swap with value at location MIN

Step 5: Increment MIN to point to next element

Step 6: Repeat until list is sorted

Step 7: Stop

By Sr. Asst. Prof. Pratik Chand, LTU Page 12

 Data Structures and Algorithms – BCA 3rd Semester

Example: Sort the following unsorted element of array using selection sort

14, 33, 27, 10, 35, 19, 42, 44

Solution:

The first position where 14 is stored presently, we search the whole list and find
that 10 is the lowest value.

So we replace 14 with 10. After the one iteration, 10 which happens to be the
minimum value in the list, appears in the first position of the sorted list.

For the second position, where 33 is residing, we start scanning the rest of the list
in a linear manner.

We find that 14 is the second lowest value in the list and it should appear at the
second place. We swap these values.

After two iterations, two least values are positioned at the beginning in a sorted
manner.

The same process is applied to the rest of the items in the array.

Following is a pictorial depiction of the entire sorting process

By Sr. Asst. Prof. Pratik Chand, LTU Page 13

 Data Structures and Algorithms – BCA 3rd Semester

Bubble Sort
Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-
based algorithm in which each pair of adjacent elements is compared and the
elements are swapped if they are not in order. This algorithm is not suitable for
large data sets.

Time Complexity: Ο(n2)

By Sr. Asst. Prof. Pratik Chand, LTU Page 14

 Data Structures and Algorithms – BCA 3rd Semester

Algorithm for Bubble Sort

Step 1: Start

Step 2: Create a function as BubbleSort()

BubbleSort(list)

for all elements of list

if list[i] > list[i+1]

swap(list[i], list[i+1])

end if

end for

return list

end BubbleSort

Step 3: Stop

Example: Sort the following unsorted data using bubble sort

14, 33, 27, 35, 10

Solution:

Bubble sort starts with very first two elements, comparing them to check which
one is greater.

1st Pass:

In this case, value 33 is greater than 14, so it is already in sorted locations. Next,
we compare 33 with 27.

We find that 27 is smaller than 33 and these two values must be swapped.
By Sr. Asst. Prof. Pratik Chand, LTU Page 15
 Data Structures and Algorithms – BCA 3rd Semester

The new array should look like this

Next we compare 33 and 35. We find that both are in already sorted positions.

Then we move to the next two values, 35 and 10.

We know then that 10 is smaller 35. Hence they are not sorted.

We swap these values. We find that we have reached the end of the array. After
one iteration, the array should look like this

Repeat this process until all the data are sorted.

2nd Pass:
After the second iteration, it should look like this

3rd Pass:

By Sr. Asst. Prof. Pratik Chand, LTU Page 16

 Data Structures and Algorithms – BCA 3rd Semester

4th Pass:

And when there's no swap required, bubble sorts learns that an array is completely
sorted.

Exchange Sort:
The exchange sort is almost similar as the bubble sort. In fact some people refer to
the exchange sort as just a different bubble sort.

The exchange sort compares each element of an array and swaps those elements
that are not in their proper position, just like a bubble sort does. The only
difference between the two sorting algorithms is the manner in which they
compare the elements.

The exchange sort compares the first element with each element of the array,
making a swap where is necessary.

Time Complexity: Ο(n2)

Algorithm for Exchange sort

Step 1: Start

Step 2: Take first element and compare with all remaining element

Step 3: For ascending order

If the first element is greater then, swap with next element

For descending order

If the first element is smaller then, swap with next element

Step 4: Repeat step 3 until all the elements are sorted

Step 5: Stop

By Sr. Asst. Prof. Pratik Chand, LTU Page 17

 Data Structures and Algorithms – BCA 3rd Semester

Example: Sort the following data in ascending order using exchange sort

84, 69, 76, 86, 94, 91

Solution:

Compare first element with all other element,

First element > other, then swap, otherwise check for next.

1st pass:

Here, 84>69, swap

2nd Pass:

84>76, swap

3rd Pass:

4th Pass:

By Sr. Asst. Prof. Pratik Chand, LTU Page 18

 Data Structures and Algorithms – BCA 3rd Semester

5th Pass:

94>91, then swap

Now the data are in sorted order.

Quick Sort
 Quick sort is also known as Partition-exchange sort based on the rule
of Divide and Conquer.
 It is a highly efficient sorting algorithm.
 Quick sort is the quickest comparison-based sorting algorithm.
 It is very fast and requires less additional space, only O(n log n) space is
required.
 Quick sort picks an element as pivot and partitions the array around the
picked pivot.

Time Complexity: Ο(n log n)

There are different versions of quick sort which choose the pivot in different ways:

First element as pivot

Last element as pivot

Median as pivot

By Sr. Asst. Prof. Pratik Chand, LTU Page 19

 Data Structures and Algorithms – BCA 3rd Semester

Random element as pivot

Algorithm for Quick Sort (first index as pivot)

Step 1: Start

Step 2: If there is only one element in the list it is already sorted, return.

Step 3: Choose the first element as pivot.

Step 3: Take two pointers left and right of the list excluding pivot.

Step 4: Left pointer points to the first element

Step 5: Right pointer points to the last element

Step 6: Compare pivot element and left and right pointer element

If (element at left pointer <= pivot)

Move left pointer to next element towards right side
If (element at right pointer > pivot)
Move right index to next element toward left side.
Step 7: If both condition of step 6 does not match, swap left and right.

Step 8: If index of left pointer is greater than index of right pointer (left and right
pointer cross each other), then swap element of left pointer with pivot element.

Step 9: Stop

By Sr. Asst. Prof. Pratik Chand, LTU Page 20

 Data Structures and Algorithms – BCA 3rd Semester

By Sr. Asst. Prof. Pratik Chand, LTU Page 21

 Data Structures and Algorithms – BCA 3rd Semester

By Sr. Asst. Prof. Pratik Chand, LTU Page 22

 Data Structures and Algorithms – BCA 3rd Semester

Algorithm for Quick Sort for (last index as pivot)

Step 1: Start

Step 2: Choose the highest index value as pivot.

Step 3: Take two variables to point left and right of the list excluding pivot.

Step 4: Left points to the low index.

Step 5: Right points to the high index.

Step 6: While value at left < (Less than) pivot move right.

Step 7: While value at right > (Greater than) pivot move left.

Step 8: If both Step 5 and Step 6 does not match, swap left and right.

Step 9: if left index is greater than right, then swap left with pivot element.

Step 10: Stop

Example: Sort the following unsorted data using Quick sort

36, 34, 43, 11, 15, 20, 28, 45, 27, 32

Solution:
left < pivot move right, otherwise stop

right > pivot move left, otherwise stop

if both condition are not matched then, swap left and right.

Let’s take highest index element i.e. 32 as pivot element. Then, left element is 36
and right element is 27.

Here left and right both are not matched then swap. And move to next element and
check the condition.

By Sr. Asst. Prof. Pratik Chand, LTU Page 23

 Data Structures and Algorithms – BCA 3rd Semester

Here the index of left is greater than right, so, swap left with pivot element.

Now the pivot element is in sorted order. Perform the quick sort operation for data
in the left side of pivot element and right side of pivot element separately.

Now the data is sorted.

By Sr. Asst. Prof. Pratik Chand, LTU Page 24

 Data Structures and Algorithms – BCA 3rd Semester

Merge Sort:
Merge sort is a sorting technique based on divide and conquer technique. It is one
of the most respected algorithms. Merge sort first divides the array into equal
halves and then combines them in a sorted manner.

Merge sort keeps on dividing the list into equal halves until it can no more be
divided. By definition, if it is only one element in the list, it is sorted. Then, merge
sort combines the smaller sorted lists keeping the new list sorted too.

Time Complexity: Ο(n log n)

Algorithm for Merge Sort

Step 1: Start

Step 2: if it is only one element in the list it is already sorted, return.

Step 3: divide the list recursively into two halves until it can no more be divided.

Step 4: merge the smaller lists into new list in sorted order.

Step 5: Stop

Example: Sort the following unsorted array of item using Merge sort algorithm

14, 33, 27, 10, 35, 19, 42, 44

Solution:

We know that merge sort first divides the whole array iteratively into equal halves
unless the atomic values are achieved. We see here that an array of 8 items is
divided into two arrays of size 4.

This does not change the sequence of appearance of items in the original. Now we
divide these two arrays into halves.

By Sr. Asst. Prof. Pratik Chand, LTU Page 25

 Data Structures and Algorithms – BCA 3rd Semester

We further divide these arrays and we achieve atomic value which can no more be
divided.

Now, we combine them in exactly the same manner as they were broken down.
Please note the color codes given to these lists.

We first compare the element for each list and then combine them into another list
in a sorted manner. We see that 14 and 33 are in sorted positions. We compare 27
and 10 and in the target list of 2 values we put 10 first, followed by 27. We change
the order of 19 and 35 whereas 42 and 44 are placed sequentially.

In the next iteration of the combining phase, we compare lists of two data values,
and merge them into a list of found data values placing all in a sorted order.

After the final merging, the list should look like this

Radix Sort:
Radix sort is one of the sorting algorithms used to sort a list of integer numbers in
order. In radix sort algorithm, a list of integer numbers will be sorted based on the
digits of individual numbers. Sorting is performed from least significant digit to the
most significant digit.

Radix sort algorithm requires the number of passes which are equal to the number
of digits present in the largest number among the list of numbers. For example, if
the largest number is a 3 digit number then that list is sorted with 3 passes.

Time Complexity: O(n)

By Sr. Asst. Prof. Pratik Chand, LTU Page 26

 Data Structures and Algorithms – BCA 3rd Semester

Algorithm for Radix Sort

Step 1: Start

Step 2: Define 10 queues each representing a bucket for each digit from 0 to 9.

Step 3: Consider the least significant digit of each number in the list which is to be
sorted.

Step 4: Insert each number into their respective queue based on the least
significant digit.

Step 5: Group all the numbers from queue 0 to queue 9 in the order they have
inserted into their respective queues.

Step 6: Repeat from step 3 based on the next least significant digit.

Step 7: Repeat from step 2 until all the numbers are grouped based on the most
significant digit.

Step 8: Stop

Example: Sort the following list of data using Radix algorithm

82, 901, 100, 12, 150, 77, 55, 23

Solution:
Step 1: Define 10 queues each represents a bucket for digits from 0 to 9

Step 2: Insert all the number into the respective queue based on the least
significant digits (one place digits) of every number.

By Sr. Asst. Prof. Pratik Chand, LTU Page 27

 Data Structures and Algorithms – BCA 3rd Semester

Group all the number from queue 0 to queue 9 in order they have inserted and
consider the list for next step as input data.

Step 3: Insert all the number into the respective queue based on the next least
significant digits (Ten place digits) of every number.

Group all the number from queue 0 to queue 9 in order they have inserted and
consider the list for next step as input data.

Step 4: Insert all the number into the respective queue based on the next least
significant digits (Hundred place digits) of every number.

By Sr. Asst. Prof. Pratik Chand, LTU Page 28

 Data Structures and Algorithms – BCA 3rd Semester

Group all the number from queue 0 to queue 9 in order they have inserted and
consider the list for next step as input data.

Now list is in sorted order.

Binary Sort:
Binary sort is a comparison type sorting algorithm. It is a modification of
the insertion sort algorithm. In this algorithm, we also maintain one sorted and one
unsorted sub-array. The only difference is that we find the correct position of an
element using binary search instead of linear search. It helps to fasten the sorting
algorithm by reducing the number of comparisons required.

Time Complexity: O(n2)

Algorithm for Binary Sort:

Step 1: Start

Step 2: Mark the first element from the unsorted sub-array A[1] as the key.

Step 3: Use binary search to find the correct position p of A[1] inside the sorted
sub-array.

Step 4: Shift the elements from p 1 steps rightwards and insert A[1] in its correct
position.

Step 5: Repeat the above steps for all the elements in the unsorted sub-array.

Step 6: Stop

Note: During binary search we have to find left, mid, right point

Left Point = lower bound value

Right Point = upper bound value

Mid Point = left + (right - left)/2

By Sr. Asst. Prof. Pratik Chand, LTU Page 29

 Data Structures and Algorithms – BCA 3rd Semester

Example: Sort the following data using binary sort algorithm

3, 7, 1, 4, 6, 2, 5

Solution:

First item is always in sorted order. So, no searching is needed.

Move to the second item i.e. 7

Now the binary search to be done in sorted list. There is only one item so, left,
middle, and right pointer are at 3 only.

Now compare 7 with middle item, i.e 3 and place at left if item is less then middle
item and place at right if it is greater. Here 7 is greater than 3 so place at right.

Now move to third item i.e. 1

By Sr. Asst. Prof. Pratik Chand, LTU Page 30

 Data Structures and Algorithms – BCA 3rd Semester

Compare 1 with middle pointer which is greater than 1, so place 1 at left of 3.

Now move to 4th item i.e. 4

Now the 4 is greater than middle vale 3, move the pointer to right side.

Now there is only one item in the pointer, so compare with middle item 7, here, 4
is less than 7, so place at left of 7.

It goes for all items likewise.

By Sr. Asst. Prof. Pratik Chand, LTU Page 31

 Data Structures and Algorithms – BCA 3rd Semester

Here the 6 is greater than middle value 3, the pointer goes to right side. If goes so
on.

By Sr. Asst. Prof. Pratik Chand, LTU Page 32

 Data Structures and Algorithms – BCA 3rd Semester

Now all the data are in sorted array.

Heap Sort:
Heap is a tree based data structure. Here tree is complete or almost complete binary
tree. The insertion always takes place in leaf node and deletion always takes place
in root node in heap. After deleting the root node, last leaf node will goes up to
root node.

Time Complexity: O(n log n)

There are two types of heap

 Min heap
 Max heap

By Sr. Asst. Prof. Pratik Chand, LTU Page 33

 Data Structures and Algorithms – BCA 3rd Semester

Min heap: It contains parent value is less than its child value.

Max heap: It contains parent value is greater than its child value.

Heapify:
Heapify is the process of making min heap or max heap. In this process we
compare from the last leaf node. To make min heap take smallest value from child
to parent node. To make max heap take largest value from child to parent node.

Example: Create max heap from following complete binary tree using heapify
method.

By Sr. Asst. Prof. Pratik Chand, LTU Page 34

 Data Structures and Algorithms – BCA 3rd Semester

Solution:

Here we start to check the value from parent node of last leaf node. The last leaf
node is 12 and its parent is 6. Now check parent is greater than its largest child? If
yes, then leave it as it is and move to next node. If no, then swap parent with its
largest child.

Here largest child of node 6 is 12 and it is greater than its parent node. So, swap 6
with 12 and this process goes on until max heap is complete.

Heap sort processes the elements by creating the min heap or max heap using the
elements of the given array. Min heap or max heap represents the ordering of the
array in which root element represents the minimum or maximum element of the
array. At each step, the root element of the heap gets deleted and stored into the
sorted array and the heap will again be heapified.

By Sr. Asst. Prof. Pratik Chand, LTU Page 35

 Data Structures and Algorithms – BCA 3rd Semester

Max heap sort the data in ascending order and Min heap sort the data in descending
order.

The heap sort basically recursively performs two main operations.

 Build a heap H, using the elements of array.

 Repeatedly delete the root element of the heap formed in phase 1.

Algorithm for Heap Sort

Step 1: Start

Step 2: Construct a Binary Tree with given list of Elements.

Step 3: Transform the Binary Tree into Min or Max Heap.

Step 4: Delete the root element from Min or Max Heap using Heapify method.

Step 5: Put the deleted element into the Sorted list.

Step 6: Repeat the same until Min Heap becomes empty.

Step 7: Display the sorted list.

Step 8: Stop

By Sr. Asst. Prof. Pratik Chand, LTU Page 36

 Data Structures and Algorithms – BCA 3rd Semester

Example: Sort the following data using heap sort

82, 90, 10, 12, 15, 77, 55, 23

Solution:

Let’s sort the data using max heap.

Step 1: Create a heap with given data and use heapify method to make max heap.

Read number after heapify:

90, 82, 77, 23, 15, 10, 55, 12

Step 2: Delete root node i.e. 90 from the max heap and swap by last leaf node.
Again use heapify method to create max heap.

List of number after deleting 90 and swapping with last leaf node i.e. 12 is:

12, 82, 77, 23, 15, 10, 55, 90

Read number after heapify:

82, 23, 77, 12, 15, 10, 55, 90

By Sr. Asst. Prof. Pratik Chand, LTU Page 37
 Data Structures and Algorithms – BCA 3rd Semester

Step 3: Delete 82 and swap with last leaf node 55 and use heapify method

List of number after deleting 82 and swapping with last leaf node i.e. 55 is:

55, 23, 77, 12, 15, 10, 82, 90

Read number after heapify:

77, 23, 55, 12, 15, 10, 82, 90

Step 4: Delete 77 and swap with 10 and use heapify method

List of number after deleting 77 and swapping with last leaf node i.e. 10 is:

10, 23, 55, 12, 15, 77, 82, 90

Read number after heapify:

55, 23, 10, 12, 15, 77, 82, 90

By Sr. Asst. Prof. Pratik Chand, LTU Page 38

 Data Structures and Algorithms – BCA 3rd Semester

Step 5: Delete 55 and swap with 15 and use heapify method

List of number after deleting 55 and swapping with last leaf node i.e. 15 is:

15, 23, 10, 12, 55, 77, 82, 90

Read number after heapify:

23, 15, 10, 12, 55, 77, 82, 90

Step 6: Delete 23 and swap with 12 and use heapify method

List of number after deleting 23 and swapping with last leaf node i.e. 12 is:

12, 15, 10, 23, 55, 77, 82, 90

Read number after heapify:

15, 12, 10, 23, 55, 77, 82, 90

By Sr. Asst. Prof. Pratik Chand, LTU Page 39

 Data Structures and Algorithms – BCA 3rd Semester

Step 6: Delete 15 and swap with 10 and use heapify method

List of number after deleting 15, 12 and 10 from max heap is:

10, 12, 15, 23, 55, 77, 82, 90

Now the list of number is sorted in ascending order.

End of Unit - 8

By Sr. Asst. Prof. Pratik Chand, LTU Page 40