SORTING IN DATA STRUCTURE
Sorting refers to rearrangement of a given array or list of elements
according to a comparison operator on the elements. The
comparison operator is used to decide the new order of elements in
the respective data structure.
When we have a large amount of data, it can be difficult to deal with
it, especially when it is arranged randomly. When this happens,
sorting that data becomes crucial. It is necessary to sort data in
order to make searching easier.
There are various sorting algorithms are used in data structures. The
following two types of sorting algorithms can be broadly classified:
1. Comparison-based: We compare the elements in a comparison-
based sorting algorithm)
2. Non-comparison-based: We do not compare the elements in a
non-comparison-based sorting algorithm)
Bubble sort
Bubble Sort is the simplest sorting algorithm that works by
repeatedly swapping the adjacent elements if they are in the wrong
order. This algorithm is not suitable for large data sets as its average
and worst-case time complexity is quite high.
Working of Bubble Sort algorithm:
Lets consider the following array as an example: arr[] = {5, 1, 4, 2,
8}
First Pass:
Bubble sort starts with very first two elements, comparing them to
check which one is greater.
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two
elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already
in order (8 > 5), algorithm does not swap them.
Second Pass:
Now, during second iteration it should look like this:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Third Pass:
Now, the array is already sorted, but our algorithm does not know if it
is completed.
The algorithm needs one whole pass without any swap to know it is
sorted.
( 1 2 4 5 8 ) –> (12458)
( 1 2 4 5 8 ) –> (12458)
( 1 2 4 5 8 ) –> (12458)
( 1 2 4 5 8 ) –> (12458)
Illustration:
Insertion Sort
Insertion sort is a simple sorting algorithm that works similarly to the
way you sort playing cards in your hands. The array is virtually split
into a sorted and an unsorted part. Values from the unsorted part are
picked and placed at the correct position in the sorted part.
Working of Insertion Sort algorithm:
Consider an example: arr[]: {12, 11, 13, 5, 6}
12 11 13 5 6
First Pass:
Initially, the first two elements of the array are compared in
insertion sort.
12 11 13 5 6
Here, 12 is greater than 11 hence they are not in the ascending
order and 12 is not at its correct position. Thus, swap 11 and 12.
So, for now 11 is stored in a sorted sub-array.
11 12 13 5 6
Second Pass:
Now, move to the next two elements and compare them
11 12 13 5 6
Here, 13 is greater than 12, thus both elements seems to be in
ascending order, hence, no swapping will occur. 12 also stored in
a sorted sub-array along with 11
Third Pass:
Now, two elements are present in the sorted sub-array which
are 11 and 12
Moving forward to the next two elements which are 13 and 5
11 12 13 5 6
Both 5 and 13 are not present at their correct place so swap them
11 12 5 13 6
After swapping, elements 12 and 5 are not sorted, thus swap
again
11 5 12 13 6
Here, again 11 and 5 are not sorted, hence swap again
5 11 12 13 6
here, it is at its correct position
Fourth Pass:
Now, the elements which are present in the sorted sub-array
are 5, 11 and 12
Moving to the next two elements 13 and 6
5 11 12 13 6
Clearly, they are not sorted, thus perform swap between both
5 11 12 6 13
Now, 6 is smaller than 12, hence, swap again
5 11 6 12 13
Here, also swapping makes 11 and 6 unsorted hence, swap
again
5 6 11 12 13
Finally, the array is completely sorted.
Illustrations:
Merge Sort
The Merge Sort algorithm is a sorting algorithm that is based on
the Divide and Conquers paradigm. In this algorithm, the array is
initially divided into two equal halves and then they are combined in
a sorted manner.
Let’s see how Merge Sort uses Divide and Conquer:
The merge sort algorithm is an implementation of the divide and
conquers technique. Thus, it gets completed in three steps:
1. Divide: In this step, the array/list divides itself recursively into
sub-arrays until the base case is reached.
2. Conquer: Here, the sub-arrays are sorted using recursion.
3. Combine: This step makes use of the merge( ) function to
combine the sub-arrays into the final sorted array.
Working of Merge Sort algorithm:
To know the functioning of merge sort, lets consider an array arr[] =
{38, 27, 43, 3, 9, 82, 10}
At first, check if the left index of array is less than the right index, if
yes then calculate its mid point
Now, as we already know that merge sort first divides the whole
array iteratively into equal halves, unless the atomic values are
achieved.
Here, we see that an array of 7 items is divided into two arrays of
size 4 and 3 respectively.
Now, again find that is left index is less than the right index for both
arrays, if found yes, then again calculate mid points for both the
arrays.
Now, further divide these two arrays into further halves, until the
atomic units of the array is reached and further division is not
possible.
After dividing the array into smallest units, start merging the
elements again based on comparison of size of elements
Firstly, compare the element for each list and then combine them
into another list in a sorted manner.
After the final merging, the list looks like this:
Quick sort
Quick sort is a sorting algorithm based on the divide and conquer
approach where an array is divided into subarrays by selecting a
pivot element (element selected from the array).
1. While dividing the array, the pivot element should be positioned in
such a way that elements less than the pivot are kept on the left
side, and elements greater than the pivot is on the right side of
the pivot.
2. The left and right subarrays are also divided using the same
approach. This process continues until each subarray contains a
single element.
3. At this point, elements are already sorted. Finally, elements are
combined to form a sorted array.
Working of Quick Sort algorithm:
To know the functioning of Quick sort, let’s consider an array arr[] =
{10, 80, 30, 90, 40, 50, 70}
Indexes: 0 1 2 3 4 5 6
low = 0, high = 6, pivot = arr[h] = 70
Initialize index of smaller element, i = -1
Step1
Traverse elements from j = low to high-1
j = 0: Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i=0
arr[] = {10, 80, 30, 90, 40, 50, 70} // No change as i and j are
same
j = 1: Since arr[j] > pivot, do nothing
Step2
j = 2 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i=1
arr[] = {10, 30, 80, 90, 40, 50, 70} // We swap 80 and 30
Step3
j = 3 : Since arr[j] > pivot, do nothing // No change in i and arr[]
j = 4 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i=2
arr[] = {10, 30, 40, 90, 80, 50, 70} // 80 and 40 Swapped
Step 4
j = 5 : Since arr[j] <= pivot, do i++ and swap arr[i] with arr[j]
i=3
arr[] = {10, 30, 40, 50, 80, 90, 70} // 90 and 50 Swapped
Step 5
We come out of loop because j is now equal to high-1.
Finally we place pivot at correct position by swapping arr[i+1] and
arr[high] (or pivot)
arr[] = {10, 30, 40, 50, 70, 90, 80} // 80 and 70 Swapped
Step 6
Now 70 is at its correct place. All elements smaller than 70 are
before it and all elements greater than 70 are after it.
Since quick sort is a recursive function, we call the partition function
again at left and right partitions
Step 7
Again call function at right part and swap 80 and 90
Step 8
