UNIT 4

4.SORTING
Sorting
Introduction to Sorting
 Sorting refers to arranging data in a particular format. Sorting algorithm
specifies the way to arrange data in a particular order. Most common orders
are in numerical or lexicographical order.
 The importance of sorting lies in the fact that data searching can be
optimized to a very high level, if data is stored in a sorted manner. Sorting is
also used to represent data in more readable formats. 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.
 Sorting
Sorting Efficiency
• There are many techniques for sorting. Implementation of particular sorting
technique depends upon situation. Sorting techniques mainly depends on
two parameters. First parameter is the execution time of program, which
means time taken for execution of program. Second is the space, which
means space taken by the program.
In-place Sorting and Not-in-place Sorting
• Sorting algorithms may require some extra space for comparison and
temporary storage of few data elements. These algorithms do not require any
extra space and sorting is said to happen in-place, or for example, within the
array itself. This is called in-place sorting. Bubble sort is an example of in-
place sorting.
• However, in some sorting algorithms, the program requires space which is
more than or equal to the elements being sorted. Sorting which uses equal or
more space is called not-in-place sorting. Merge-sort is an example of not-in-
place sorting.
 Sorting
Stable and Not Stable Sorting
 If a sorting algorithm, after sorting the contents, does not change the sequence of
similar content in which they appear, it is called stable sorting.

 If a sorting algorithm, after sorting the contents, changes the sequence of similar
content in which they appear, it is called unstable sorting.

 Stability of an algorithm matters when we wish to maintain the sequence of original

elements, like in a tuple for example.
Sorting
Adaptive and Non-Adaptive Sorting Algorithm
• A sorting algorithm is said to be adaptive, if it takes advantage of already
'sorted' elements in the list that is to be sorted. That is, while sorting if the
source list has some element already sorted, adaptive algorithms will take
this into account and will try not to re-order them.
• A non-adaptive algorithm is one which does not take into account the
elements which are already sorted. They try to force every single element to
be re-ordered to confirm their sortedness.
Important Terms
• 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.
Sorting
 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
Types of Sorting Techniques
Bubble Sort
Insertion Sort
Selection Sort
Merge Sort
Shell sort
Quick Sort
Heap Sort
Radix sort
BUBBLE -SORT
ALGORITHM
Bubble Sort Algorithm
• 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 as its average and worst case
complexity are of Ο(n2) where n is the number of items.
• How Bubble Sort Works?
• We take an unsorted array for our example. Bubble sort takes Ο(n 2) time so
we're keeping it short and precise.

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

• In this case, value 33 is greater than 14, so it is already in sorted locations.

Next, we compare 33 with 27.
 Bubble Sort Algorithm

We find that 27 is smaller than 33 and these two values must be swapped.

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.
 Bubble Sort Algorithm
• We swap these values. We find that we have reached the end of the array. After one
iteration, the array should look like this

To be precise, we are now showing how an array should look like after each iteration.
After the second iteration, it should look like this

Notice that after each iteration, at least one value moves at the end

And when there's no swap required, bubble sorts learns that an array is completely sorted.
Bubble Sort Algorithm
• Algorithm
• We assume list is an array of n elements. We further assume that swap function
swaps the values of the given array elements.
 begin 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 BubbleSortes

• We observe in algorithm that Bubble Sort compares each pair of array element
unless the whole array is completely sorted in an ascending order. This may cause
a few complexity issues like what if the array needs no more swapping as all the
elements are already ascending.

• To ease-out the issue, we use one flag variable swapped which will help us see if
any swap has happened or not. If no swap has occurred, i.e. the array requires no
more processing to be sorted, it will come out of the loop.
Insertion Sort
Algorithm
Insertion Sort
ALGORITHM

Step 1 − If it is the first element, it is already sorted.

return 1;
 Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-
list
Step 4 − Shift all the elements in the sorted sub-list
that is greater than the value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted
Insertion Sort
• This is an in-place comparison-based sorting algorithm. Here, a sub-list is
maintained which is always sorted. For example, the lower part of an array is
maintained to be sorted. An element which is to be 'insert'ed in this sorted
sub-list, has to find its appropriate place and then it has to be inserted there.
Hence the name, insertion sort.
• The array is searched sequentially and unsorted items are moved and inserted
into the sorted sub-list (in the same array). This algorithm is not suitable for
large data sets as its average and worst case complexity are of Ο(n2),
where n is the number of items.
How Insertion Sort Works?
• We take an unsorted array for our example.

• Insertion sort compares the first two elements

Insertion Sort
• 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.
Insertion Sort
• These values are not in a sorted order.

• So we swap them.

• However, swapping makes 27 and 10 unsorted.

• Hence, we swap them too.

• Again we find 14 and 10 in an unsorted order.

SELECTION SORT
ALGORITHM
Selection Sort
Algorithm
Step 1 − Set MIN to location 0

Step 2 − Search the minimum element in the list

Step 3 − Swap with value at location MIN

Step 4 − Increment MIN to point to next element

Step 5 − Repeat until list is sorted

Selection Sort
• Selection sort is a simple sorting algorithm. This sorting algorithm is an in-
place comparison-based algorithm in which the list is divided into two parts,
the sorted part at the left end and the unsorted part at the right end. Initially,
the sorted part is empty and the unsorted part is the entire list.
• The smallest element is selected from the unsorted array and swapped with
the leftmost element, and that element becomes a part of the sorted array.
This process continues moving unsorted array boundary by one element to the
right.
• This algorithm is not suitable for large data sets as its average and worst case
complexities are of Ο(n2), where n is the number of items.
• How Selection Sort Works?
• Consider the following depicted array as an example.

• For the first position in the sorted list, the whole list is scanned sequentially.
The first position where 14 is stored presently, we search the whole list and
find that 10 is the lowest value.
Selection Sort

So we replace 14 with 10. After 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.
Selection Sort
• The same process is applied to the rest of the items in the array.
• Following is a pictorial depiction of the entire sorting process
MERGE SORT
ALGORITHM
Merge Sort
Algorithm
• 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.
 Step 1 − if it is only one element in the list it is already sorted, return.
 Step 2 − divide the list recursively into two halves until it can no more be
divided.
 Step 3 − merge the smaller lists into new list in sorted order.

ӂ Merge sort is a sorting technique based on divide and conquer technique.

With worst-case time complexity being Ο(n log n), 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
How Merge Sort Works?
• To understand merge sort, we take an unsorted array as the following

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.

We further divide these arrays and we achieve atomic value which can no more be divided.
Merge Sort
• 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
SHELL SORT
ALGORITHM
Shell Sort
• Algorithm
Step 1 − Initialize the value of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 4 − Repeat until complete list is sorted
• 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
Knuth's Formula
h = h * 3 + 1
 where − h is interval with initial value 1
Shell Sort
• This algorithm is quite efficient for medium-sized data sets as its average and
worst case complexity are of Ο(n), where n is the number of items.
• How Shell Sort Works?
• Let us consider the following example to have an idea of how shell sort works.
We take the same array we have used in our previous examples. For our
example and ease of understanding, we take the interval of 4. Make a virtual
sub-list of all values located at the interval of 4 positions. Here these values
are {35, 14}, {33, 19}, {42, 27} and {10, 14}
Shell Sort
• We compare values in each sub-list and swap them (if necessary) in the
original array. After this step, the new array should look like this

• Then, we take interval of 2 and this gap generates two sub-lists - {14, 27, 35,
42}, {19, 10, 33, 44}

We compare and swap the values, if required, in the original array. After this step, the
array should look like this
 Shell Sort
• Finally, we sort the rest of the array using interval of value 1. Shell sort uses insertion
sort to sort the array.

We see that it required only four swaps to sort the rest of the array
QUICK SORT
ALGORITHM
QUICK SORT
 Quick Sort Algorithm

It Is Sorted Quickly The Position Of The Element Is Replaced Quickly From Last Element

1. Start

2. Find The Position Of An Pivot Element

3. Let Us Consider The First Element As A Pivot Value.

4. Initialize I To Low & J To High Index's.

5. Repeat The Steps Until I<j

I. Keep On Increment The I Value While A[i]<=pivot
II. Keep On Decrement The J Value While A[j]>pivot
III. If The Condition Is True [I,<j] Swap A[i],a[j]
IV. If The Condition Is False [I>j] Swap A[j], Pivot

6. Now J Is The Exact Position Of The Pivot.

7. Stop
 0 1 2 3 4 5
a[]=
30 20 10 50 60 40
i j
a[i] < a[j]
0 < 5

Find the I & J values

a[ I ] < = PIVOT &
i++

30 <= 30 20 <= 30 10 <= 30 50 <= 30

I value
TRUE TRUE TRUE FALSE

i = 3
a[ j ] > PIVOT &
J--

40 > 30 60 > 30 50 > 30 10 > 30

J value
TRUE TRUE TRUE FALSE

j = 2

 Now check the conditions

 if i<j swap a[i],a[j]- 3 < 2 False

OR
 if i>j swap a[j],PIVOT- 3 > 2 True
  Now swap the elements a[j] & PIVOT

 After Swapping the elements are

10 20 30 50 60 40

 If the partition is having only 2 elements we are unable to

sort the data

From The Second Part

a[i] < a[j]

50 60 40 0 < 2
I value TRUE
3 < 5
i j
 a[ I ] < = PIVOT &
i++
50 <= 50 60 <= 50
50 60 40
TRUE FALSE
i j
i = 1

a[ J ] > PIVOT &

J--

40 > 50 j = 2
J value
FALSE

 Now check the conditions

 if I <J swap a [ i ],a[j]- 1 < 2 True
or
 if I >J swap a[j],PIVOT- 1 > 2 False
 So swap a[I ], a[ J ] then

50 40 60

NOTE:-
Now the pivot value is not changed so
repeat the process until the pivot value swaps
HEAP SORT
ALGORITHM
HEAP SORT
ALGORITHM
 Step 1 − Create a new node at the end of heap.
 Step 2 − Assign new value to the node.
 Step 3 − Compare the value of this child node with its parent.
 Step 4 − If value of parent is less than child, then swap them.
 Step 5 − Repeat step 3 & 4 until Heap property holds.
Max Heap Deletion Algorithm
 Step 1 − Remove root node.
 Step 2 − Move the last element of last level to root.
 Step 3 − Compare the value of this child node with its parent.
 Step 4 − If value of parent is less than child, then swap them.
 Step 5 − Repeat step 3 & 4 until Heap property holds.
HEAP SORT
• Heap is a special case of balanced binary tree data structure where the root-
node key is compared with its children and arranged accordingly. If α has child
node β then
• As the value of parent is greater than that of child, this property
generates Max Heap. Based on this criteria, a heap can be of two types
• For Input → 35 33 42 10 14 19 27 44 26 31

Min-Heap
Max Heap
HEAP SORT
Max Heap Construction Algorithm
 We shall use the same example to demonstrate how a Max Heap is created.
The procedure to create Min Heap is similar but we go for min values instead
of max values.
 We are going to derive an algorithm for max heap by inserting one element at
a time. At any point of time, heap must maintain its property. While insertion,
we also assume that we are inserting a node in an already heapified tree.

• Note − In Min Heap construction algorithm, we expect the value of the parent
node to be less than that of the child node.

• Let's understand Max Heap construction by an animated illustration. We

consider the same input sample that we used earlier.
HEAP SORT
Max Heap Construction

Max Heap Deletion Algorithm

• Let us derive an algorithm to delete from max heap. Deletion in Max (or Min)
Heap always happens at the root to remove the Maximum (or minimum)
value.
HEAP SORT
 Max Heap Deletion Algorithm
 Step 1 − Remove root node.
 Step 2 − Move the last element of last level to root.
 Step 3 − Compare the value of this child node with its parent.
 Step 4 − If value of parent is less than child, then swap them.
 Step 5 − Repeat step 3 & 4 until Heap property holds.
Radix/Bucket Sort
1, c 3, a 3, b 7, d 7, g 7, e

B       

0 1 2 3 4 5 6 7 8 9
Radix Sort
• Radix sort is a linear sorting algorithm for integers that uses the concept of
sorting names in alphabetical order. When we have a list of sorted names,
the radix is 26 (or 26 buckets) because there are 26 letters of the alphabet.
• Observe that words are first sorted according to the first letter of the name.
That is, 26 classes are used to arrange the names, where the first class
stores the names that begins with ‘A’, the second class contains names with
‘B’, so on and so forth.
• During the second pass, names are grouped according to the second letter.
After the second pass, the names are sorted on the first two letters. This
process is continued till nth pass, where n is the length of the names with
maximum letters.
• After every pass, all the names are collected in order of buckets. That is,
first pick up the names in the first bucket that contains names beginning
with ‘A’. In the second pass collect the names from the second bucket, so
on and so forth.
Radix Sort
• When radix sort is used on integers, sorting is done on each of the digits in
the number. The sorting procedure proceeds by sorting the least significant
to most significant digit. When sorting numbers, we will have ten buckets,
each for one digit (0, 1, 2…, 9) and the number of passes will depend on the
length of the number having maximum digits.

• Example: Sort the numbers given below using radix sort.

345,654, 924, 123, 567, 472, 555, 808, 911

• In the first pass the numbers are sorted according to the digit at ones place.
The buckets are pictured upside down as shown below.
Radix Sort
Step 1: Find the largest number in ARR as LARGE
Step 2: [Initialize] SET NOP = Number of digits in LARGE
Step 3: SET PASS = 0
Step 4: Repeat Step 5 while PASS <= NOP-1
Step 5: SET I = 0 AND Initialize buckets
Step 6: Repeat Step 7 to Step 9 while I<N-1
Step 7:SET DIGIT = digit at PASS th place in A[I]
Step 8:Add A[I} to the bucket numbered DIGIT
Step 9:INCEREMENT bucket count for bucket numbered
DIGIT
Step 10:Collect the numbers in the bucket
Radix Sort
Numbe
0 1 2 3 4 5 6 7 8 9
r

345 345

654 654

924 924

123 123

567 567

472 472

555 555

808 808

911 911
Radix Sort
Number 0 1 2 3 4 5 6 7 8 9

911 911

472 472

123 123

654 654

924 924

345 345

555 555

567 567

808 808
Radix Sort
Number 0 1 2 3 4 5 6 7 8 9

808 808

911 911

123 123

924 924

345 345

654 654

555 555

567 567

472 472
After this pass, the numbers are collected bucket by bucket. The new list thus formed is
the final sorted result. After the third pass, the list can be given as, 123, 345, 472, 555,
567, 654, 808, 911, 924.