SORTING TECHNIQUES

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 O(n2) where n is the number of items.

Step by Step Process

Bubble Sort is an elementary sorting algorithm, which works by repeatedly exchanging

adjacent elements, if necessary. When no exchanges are required, the file is sorted.

Step 1 − Check if the first element in the input array is greater than the next element in the
array.

Step 2 − If it is greater, swap the two elements; otherwise move the pointer forward in the
array.

Step 3 − Repeat Step 2 until we reach the end of the array.

Step 4 − Check if the elements are sorted; if not, repeat the same process (Step 1 to Step 3)
from the last element of the array to the first.

Step 5 − The final output achieved is the sorted array.

Bubble Sort Logic

//Bubble sort logic

for(i=0; i<n-1; i++){

for(j=0; j<n-i-1; j++){
if(arr[i] > arr[j+1])
{
int temp=arr[j];
 arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}

Example

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.

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. 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 sort learns that an array is
completely sorted.

Implementation of Selection Sort Algorithm using C Programming

Language

#include<stdio.h>
#include<conio.h>

void bubble_sort(int arr[],int n)

int i,j;

for(i=0;i<n-1;i++)

for (j=0;j<n-i-1;j++)

if(arr[j]>arr[j+1])

int temp=arr[j];

arr[j]=arr[j+1];
 arr[j+1]=temp;

void printArr(int arr[],int n)

int i;

for(i=0;i<n;i++)

printf("%d \n",arr[i]);

int main()

int arr[]={64,34,25,12,22,11,90};

clrscr();

int n=sizeof(arr)/sizeof(arr[0]);

printf("Elements before sorting \n");

printArr(arr,n);

bubble_sort(arr,n);

printf("Elements after sorting \n");

printArr(arr,n);

getch();

return 0;

OUTPUT:
Elements before sorting

64 34 25 12 22 11 90

Elements after sorting

11 12 22 25 34 64 90

Bubble Sort
Advantages Disadvantages
The primary advantage of the bubble sort is that The main disadvantage of the bubble sort is the
it is popular and easy to implement. fact that it does not deal well with a list
containing a huge number of items.
In the bubble sort, elements are swapped in The bubble sort requires n-squared processing
place without using additional temporary steps for every n number of elements to be
storage. sorted.
The space requirement is at a minimum The bubble sort is mostly suitable for academic
teaching but not for real-life applications.

Selection Sort Algorithm

Selection Sort algorithm is used to arrange a list of elements in a particular order (Ascending or

Descending). In selection sort, the first element in the list is selected and it is compared repeatedly

with all the remaining elements in the list. If any element is smaller than the selected element (for

Ascending order), then both are swapped so that first position is filled with the smallest element in

the sorted order. Next, we select the element at a second position in the list and it is compared

with all the remaining elements in the list. If any element is smaller than the selected element, then

both are swapped. This procedure is repeated until the entire list is sorted.

Step by Step Process

The selection sort algorithm is performed using the following steps...

 Step 1 - Select the first element of the list (i.e., Element at first position in the list).

 Step 2: Compare the selected element with all the other elements in the list.

 Step 3: In every comparision, if any element is found smaller than the selected element

(for Ascending order), then both are swapped.

  Step 4: Repeat the same procedure with element in the next position in the list till the entire

list is sorted.

Following is the sample code for selection sort...

Selection Sort Logic

//Selection sort logic

for(i=0; i<size; i++){

for(j=i+1; j<size; j++){
if(list[i] > list[j])
{
temp=list[i];
list[i]=list[j];
list[j]=temp;
}
}
}

Example
Complexity of the Selection Sort Algorithm

To sort an unsorted list with 'n' number of elements, we need to make ((n-1)+(n-2)+(n-3)+......+1)

= (n (n-1))/2 number of comparisions in the worst case. If the list is already sorted then it

requires 'n' number of comparisions.

WorstCase: O(n2)

BestCase: Ω(n2)

Average Case : Θ(n2)

Implementation of Selection Sort Algorithm using C Programming

Language
#include<stdio.h>
#include<conio.h>

void main(){

int size,i,j,temp,list[100];
clrscr();

printf("Enter the size of the List: ");

scanf("%d",&size);
 printf("Enter %d integer values: ",size);
for(i=0; i<size; i++)
scanf("%d",&list[i]);

//Selection sort logic

for(i=0; i<size; i++){

for(j=i+1; j<size; j++){
if(list[i] > list[j])
{
temp=list[i];
list[i]=list[j];
list[j]=temp;
}
}
}

printf("List after sorting is: ");

for(i=0; i<size; i++)
printf(" %d",list[i]);

getch();
}

Output
Selection Sort
Advantages Disadvantages
The main advantage of the selection sort is that The primary disadvantage of the selection sort is
it performs well on a small list. its poor efficiency when dealing with a huge list
of items.
Because it is an in-place sorting algorithm, no The selection sort requires n-squared number of
additional temporary storage is required beyond steps for sorting n elements.
what is needed to hold the original list.
Its performance is easily influenced by the Quick Sort is much more efficient than
initial ordering of the items before the sorting selection sort
process.

Insertion Sort Algorithm

Sorting is the process of arranging a list of elements in a particular order (Ascending or Descending).

Insertion sort algorithm arranges a list of elements in a particular order. In insertion sort algorithm,
every iteration moves an element from unsorted portion to sorted portion until all the elements are
sorted in the list.

Step by Step Process

The insertion sort algorithm is performed using the following steps...

Step 1 - Assume that first element in the list is in sorted portion and all the remaining elements are
in unsorted portion.

Step 2: Take first element from the unsorted portion and insert that element into the sorted
portion in the order specified.

Step 3: Repeat the above process until all the elements from the unsorted portion are moved into
the sorted portion.

Following is the sample code for insertion sort...

Insertion Sort Logic

//Insertion sort logic
for i = 1 to size-1 {
temp = list[i];
j = i-1;
 while ((temp < list[j]) && (j > 0)) {
list[j] = list[j-1];
j = j - 1;
}
list[j] = temp;
}

Example
Complexity of the Insertion Sort Algorithm

To sort an unsorted list with 'n' number of elements, we need to make (1+2+3+......+n-1) = (n (n-

1))/2 number of comparisions in the worst case. If the list is already sorted then it

requires 'n' number of comparisions.

WorstCase: O(n2)

BestCase: Ω(n)

Average Case : Θ(n2)

Implementation of Insertion Sort Algorithm using C Programming

Language
#include<stdio.h>
#include<conio.h>

void main(){

int size, i, j, temp, list[100];

printf("Enter the size of the list: ");

scanf("%d", &size);

printf("Enter %d integer values: ", size);

for (i = 0; i < size; i++)
scanf("%d", &list[i]);

//Insertion sort logic

for (i = 1; i < size; i++) {
temp = list[i];
j = i - 1;
while ((temp < list[j]) && (j >= 0)) {
list[j + 1] = list[j];
j = j - 1;
}
list[j + 1] = temp;
}
 printf("List after Sorting is: ");
for (i = 0; i < size; i++)
printf(" %d", list[i]);

getch();
}

Output

Insertion Sort
Advantages Disadvantages

The main advantage of the insertion sort is its The disadvantage of the insertion sort is that it
simplicity. does not perform as well as other, better sorting
algorithms

It also exhibits a good performance when With n-squared steps required for every n
dealing with a small list. element to be sorted, the insertion sort does not
deal well with a huge list.

The insertion sort is an in-place sorting The insertion sort is particularly useful only
algorithm so the space requirement is minimal. when sorting a list of few items.
 Quick Sort Algorithm
Quick sort is a fast sorting algorithm used to sort a list of elements. Quick sort algorithm is invented
by C. A. R. Hoare.
The quick sort algorithm attempts to separate the list of elements into two parts and then sort each
part recursively. That means it use divide and conquer strategy. In quick sort, the partition of the list
is performed based on the element called pivot. Here pivot element is one of the elements in the
list.
The list is divided into two partitions such that "all elements to the left of pivot are smaller than the
pivot and all elements to the right of pivot are greater than or equal to the pivot".

Step by Step Process

In Quick sort algorithm, partitioning of the list is performed using following steps...

 Step 1 - Consider the first element of the list as pivot (i.e., Element at first position in the

list).

 Step 2 - Define two variables i and j. Set i and j to first and last elements of the list

respectively.

 Step 3 - Increment i until list[i] > pivot then stop.

 Step 4 - Decrement j until list[j] < pivot then stop.

 Step 5 - If i < j then exchange list[i] and list[j].

 Step 6 - Repeat steps 3,4 & 5 until i > j.

 Step 7 - Exchange the pivot element with list[j] element.

Following is the sample code for Quick sort...

Quick Sort Logic

//Quick Sort Logic
void quickSort(int list[10],int first,int last){
int pivot,i,j,temp;
 if(first < last){
pivot = first;
i = first;
j = last;

while(i < j){

while(list[i] <= list[pivot] && i < last)
i++;
while(list[j] && list[pivot])
j--;
if(i < j){
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}

temp = list[pivot];
list[pivot] = list[j];
list[j] = temp;
quickSort(list,first,j-1);
quickSort(list,j+1,last);
}
}

Example
Complexity of the Quick Sort Algorithm

To sort an unsorted list with 'n' number of elements, we need to make ((n-1)+(n-2)+(n-3)+......+1)

= (n (n-1))/2 number of comparisions in the worst case. If the list is already sorted, then it

requires 'n' number of comparisions.

WorstCase: O(n2)

BestCase: O(nlogn)

Average Case : O (n log n)

Implementation of Quick Sort Algorithm using C Programming

Language
#include<stdio.h>
#include<conio.h>

void quickSort(int [10],int,int);

void main(){
int list[20],size,i;

printf("Enter size of the list: ");

scanf("%d",&size);

printf("Enter %d integer values: ",size);

for(i = 0; i < size; i++)
scanf("%d",&list[i]);

quickSort(list,0,size-1);

printf("List after sorting is: ");

for(i = 0; i < size; i++)
printf(" %d",list[i]);

getch();
}
void quickSort(int list[10],int first,int last){
int pivot,i,j,temp;

if(first < last){

pivot = first;
i = first;
j = last;

while(i < j){

while(list[i] <= list[pivot] && i < last)
i++;
while(list[j] > list[pivot])
j--;
if(i <j){
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}

temp = list[pivot];
list[pivot] = list[j];
list[j] = temp;
quickSort(list,first,j-1);
quickSort(list,j+1,last);
}
}

Output
 Quick Sort
Advantages Disadvantages
The quick sort is regarded as the best sorting The slight disadvantage of quick sort is that its
algorithm. worst-case performance is similar to average
performances of the bubble, insertion or
selections sorts.
It is able to deal well with a huge list of items. If the list is already sorted than bubble
sort is much more efficient than quick
sort
Because it sorts in place, no additional storage If the sorting element is integers than
is required as well radix sort is more efficient than quick
sort.

Merge Sort Algorithm

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 used
and approached algorithms.

Merge sort first divides the array into equal halves and then combines them
in a sorted manner.

How Merge Sort Works?

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.

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 becomes sorted and is considered the final

solution.
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 considered
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, consider it already

sorted, so 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.

Example

In the following example, we have shown Merge-Sort algorithm step by step.

First, every iteration array is divided into two sub-arrays, until the sub-array
contains only one element. When these sub-arrays cannot be divided further,
then merge operations are performed.

Implementation of Merge Sort Algorithm using C Programming

Language
#include<stdio.h>
#include<conio.h>

void merge(int a[],int beg,int mid,int end)

{
int i,j,k;
int n1=mid-beg+1;
int n2=end-mid;
int leftArray[10],rightArray[10];
for(i=0;i<n1;i++)
{
leftArray[i]=a[beg+i];
}
for(j=0;j<n2;j++)
{
rightArray[j]=a[mid+1+j];
}

i=0;
j=0;
k=beg;
while(i<n1 && j<n2)
{
if(leftArray[i]<=rightArray[j])
{
a[k]=leftArray[i];
i++;
}
else
{
a[k]=rightArray[j];
j++;
}
k++;
}
while(i<n1)
{
a[k]=leftArray[i];
i++;
k++;
 }
while(j<n2)
{
a[k]=rightArray[i];
j++;
k++;
}
}

void mergeSort(int a[],int beg,int end)

{
if(beg<end)
{
int mid=beg+(end-beg)/2;
mergeSort(a,beg,mid);
mergeSort(a,mid+1,end);
merge(a,beg,mid,end);
}
}

void printArray(int a[],int n)

{
int i;
for(i=0;i<n;i++)
{
printf(“%d \n”,a[i]);
}
}
void main(){
int a[]={56,87,9,42,67,12,62};
int n=sizeof(a)/sizeof(a[0]);
clrscr();
printf(“Before sorting array elements are \n”);
printArray(a,n);
mergeSort(a,0,n-1);
printf(“After sorting array elements are \n”);
printArray(a,n);
return 0;
}

OUTPUT:
Before sorting array elements are
56
87
9
42
67
12
62
After sorting array elements are
9
12
42
56
62
67
87

Merge Sort

Advantages Disadvantages
It can be applied to files of any size. Requires extra space N
Reading of the input during the run-creation Merge Sort requires more space than other sort.
step is sequential ==> Not much seeking.
If heap sort is used for the in-memory part of Merge sort is less efficient than other sort
the merge, its operation can be overlapped with
I/O
 Comparison of Sorting Methods
The comparison of sorting methods is performed based on the Time complexity and Space

complexity of sorting methods. The following table provides the time and space complexities of

sorting methods. These Time and Space complexities are defined for 'n' number of elements.

Time Time Time

Sorting Complexity Complexity Complexity Space
Method Worst Case Average Case Best Case Complexity

Bubble n(n-1)/2 = O(n2) n(n-1)/2 = O(n2) n(n-1)/2 = O(n2) Constant

Sort

Insertion n(n-1)/2 = O(n2) n(n-1)/4 = O(n2) O(n) Constant

Sort

Selection n(n-1)/2 = O(n2) n(n-1)/2 = O(n2) n(n-1)/2 = O(n2) Constant

Sort

Quick Sort n(n+3)/2 = O(n2) O(n log n) O(n log n) Constant

Heap Sort O(n log n) O(n log n) O(n log n) Constant

Merge O(n log n) O(n log n) O(n log n) Depends

Sort