.PNG)
Program Statement :
Write a Menu driven C program to sort a list of elements stored in an array; using bubble sort, insertion sort, selection sort, quick sort, merge sort and heap sort techniques.
Theory :
Sorting means arranging a set of data in some order. There are different sorting methods that are used to sort the data in ascending or descending order. These methods can be divided into two categories. They are as follows :-
1. Internal sorting : If all the data is to be sorted, can be accommodated at a time in memory then internal sorting methods are used.
2. External sorting : When the data to be sorted is so large that some of data is present in the memory and some is kept in auxiliary memory (hard disk, floppy, tape,etc), then external sorting methods are used.
● Selection Sort : This is the simplest method of sorting. In this method (ascending order), the last element is compared with all other elements. If the last element is found to be less than the compared element then they are interchanged. So after 1st iteration the largest element is placed at the last position. The same procedure is repeated for the second last element and so on.
● Bubble Sort : In this method (ascending order), we begin by comparing the 0th element is compared with the 1st element. If it is found to be greater than 1st element then they are interchanged. In the same way all elements (excluding last) are compared with their next elements and are interchanged if required. In this way after 1st iteration largest element placed at last position and after 2nd iteration second largest element gets placed at the 2nd last position and so on. In this way we get a a sorted list.
● Insertion Sort : Insertion sort is implemented by inserting a particular element at the appropriate position. In this method the first iteration starts with comparison of 1st element with 0th element. In the second iteration 2nd element is compared with the 0th and 1st element. In general, in every iteration an element is compared with all elements before it. During comparison if it is found that the element in question can be inserted at a suitable position then space is created for it by shifting the other elements one position to the right and insert the element at the suitable position. This procedure is replaced for all the elements in the array.
● Heap Sort : In this method, a tree structure called heap is used. A heap is type of a binary tree. An ordered balanced binary tree is called a min heap where the value at the root of any sub-tree is less than or equal to the value of either of its children. An ordered balanced binary tree is called a max-heap, when the value at the root of any sub-tree is more than or equal to the value of either of its children.
Basically, there are two phases involved in sorting the elements using heap sort algorithm. They are as follows :-
1. Construct a heap by adjusting the array elements.
2. Repeatedly eliminate the root element of the heap by shifting it to the end of the array and then restore the heap structure with remaining elements.
The root element of a max heap is always the largest element. The sorting ends when all the root element of each successive heap has been moved to the end of the array. The resulting array now contains a sorted list.
● Quick Sort : Quick sort is a very popular sorting method. The name comes from the fact that in general, quick sort can sort a list of data elements significantly faster than any of the common sorting algorithm.
The basic strategy of quick sort is to “divide and conquer”. In this method from the given elements first we have to pick a splitting value known as pivot element. Then all the elements are spited into two piles (not necessarily containing the same number of elements). Then two piles are divided into 4 piles. The same approach is used to sort each smaller piles. This strategy based on recursion. Quick sort is also known as partition exchange sort.
●Merge sort: Merging means combining two sorted lists into one sorted list. For this the elements from both the sorted lists are compared. The smaller of both the elements is then sorted in the third array. The sorting is complete when all the elements from both the lists are placed in the third list.
Among the above six sorting techniques bubble sort, insertion sort, selection sort and heap sort are generally implemented non-recursively and quick sort and merge sort are generally implemented recursively. However, we can implement recursive algorithms for non-recursive versions and vice-versa.
In order to make bubble sort, insertion sort and selection sort recursive, the outer loops are eliminated from the non-recursive versions and the functions are called recursively decreasing upper bound of the array by 1.
We use stack data structure to implement non-recursive quick sort. And in non-recursive merge sort the array is sorted by a sequence of passes. During each pass, the array is divided into blocks. Every two adjacent blocks are merged (as in normal merge sort), and the next pass is made with a block size twice larger of the previous pass.
Algorithm :
Selection sort
/*non recursive selection sort*/
selection_sort(a[lb..ub])
{
for(i=ub;i>lb;i--)
{
/*find the maximum in a[lb]..a[i] */
max_index = i;
for(j=lb ; j<i ; j++)
if(a[j]>a[max_index])
max_index = j;
/*swap the maximum of a[lb]..a[i] with a[i] if they are different*/
if(i!=max_index)
swap(a[i],a[max_index]);
}
}
/*recursive selection sort*/
selection_sort_rec(a[lb..ub])
{
if(lb>=ub) End Algorithm;
max_index = ub;
for(j=0;j<ub;j++)
{
if(a[j]>a[max_index])
max_index = j;
}
if(ub!=max_index)
swap(a[ub],a[max_index]);
selection_sort_rec(a,lb,ub-1);
}
Bubble sort
/*non recursive bubble sort*/
bubble_sort(a[lb..ub])
{
for(i=lb+1 ; i<=ub ; i++)
{
/*compare side by side and move highest of unsorted part to start of sorted part*/
for(j= lb ; f=false ; j<=lb+ub-i ; j++)
if(a[j]>a[j+1])
{
swap(a[j],a[j+1]);
f = true;
}
/*stop unnecessary looping if the list already became sorted*/
if(f=false) exit;
}
}
/*recursive bubble sort*/
bubble_sort_rec(a[lb..ub])
{
if(lb>=ub)End Algorithm;
for(j=lb,f=0;j<=lb+ub-1;j++)
{
if(a[j]>a[j+1])
{
swap(a[j],a[j+1]);
f = 1;
}
}
if(f=1)
bubble_sort_rec(a,lb,ub-1);
}
Insertion sort
/*non recursive insertion sort*/
insertion_sort(a[lb..ub])
{
for(i= lb+1 ; i<=ub; i++)
{
/* insert a[i] into the sorted sequence a[lb]..a[i-1]*/
key=a[i];
for(j=i-1; j>=lb && a[j]>key ; j--)
a[j+1] = a[j];
a[j+1] = key;
}
}
/*recursive insertion sort*/
insertion_sort_rec(a[lb..ub])
{
if(lb>=ub) End Algorithm;
insertion_sort_rec(a,lb,ub-1);
key = a[ub];
for(j=ub-1;j>=lb && a[j]>key;j--)
a[j+1] = a[j];
a[j+1] = key;
}
Heap sort
/*non recursive heap sort*/
heap_sort(a[lb..ub])
{
for(i=lb+1; i<=ub; i++)
for(t=i ; t>lb && a[t]>a[p=parent_index(t)]; t=p)
swap( a[t], a[p]);
for(i=ub; i>lb; i--)
{
swap(a[lb], a[i]);
for(t=lb; (l=left_child_index(t))<i ;t=greater_child_index)
{
r = right_child_index(t);
greater_child_index=(r<i && a[l]<a[r])? r:1;
if(a[t]>a[greater_child_index]) break;
swap(a[t],a[greater_child_index]);
}
}
}
Quick sort
/* recursive quick sort*/
quick_sort(a[lb..ub])
{
/*check for empty or single element list*/
if(lb>=ub)
End algorithm; /*stop recursion*/
p = partition(a[lb..ub]); /*partition the list*/
quick_sort(a[lb..(p-1)]); /*continue recursion for left partition*/
quick_sort(a[(p+1)..ub]); /*continue recursion for right partition*/
}
/*non-recursive quick sort*/
quick_sort_non_rec(a[lb..ub])
{
push(lb);
push(ub);
while(stack is not empty)/*Iteration will be continued until stack is empty*/
{
ub = pop(stack);
lb = pop(stack);
/*Check for empty or single element list*/
if(lb>=ub)
continue;
p = partition(lb,ub,a); /*partition the list*/
push(lb);
push(p-1);
push(p+1);
push(ub);
}
}
/* This algorithm partitions the list into two parts with respect to a pivot element, so that the elements of left and right partition of pivot are less than and greater than or equal to the pivot element respectively*/
partition(a[lb..ub])
{
swap(a[lb],a[(lb+ub)/2]);
small_end = lb;
for(large_end=lb; large_end<ub; large_end++)
{
if(a[lb]>a[large_end+1])
{
small_end++;
swap(a[small_end],a[large_end+1]);
}
}
swap(a[lb], a[small_end]);
return small_end;
}
Merge sort
/*recursive merge sort*/
merge_sort(a[lb..ub])
{
if(lb>=ub) end_algorithm;
mid = floor((lb+ub)/2);
merge_sort(a[lb..mid]);
merge_sort(a[(mid+1)..ub]);
merge(a[lb..ub], mid);
}
/*non-recursive merge sort*/
mergesort_non_rec(a[lb..ub])
{
for(k=1;k<=(ub-lb+1);k=2k)
{
for(i=lb;i<=(ub-k);i+=2k)
{
merge(a,i,(i+k-1),min((i+2k-1),ub));
}
}
}
/* merge two sorted sub lists into one sorted list*/
merge(a[lb..ub], mid)
{
for(i=lb; j=mid+1; k=lb; i<=mid && j<=ub;k++)
temp[k] = (a[i]<a[j] ? a[i+1]:a[j+1]);
while(i<=mid)
temp[k+1] = a[i+1];
while(j<=ub)
temp[k++] = a[j++];
for(i=lb;i<=ub;i++)
a[i] = temp[i];
}
PROGRAM LISTING:
/*C program to sort a list of elements stored in an array data structure; using bubble sort, insertion sort, selection sort, quick sort, merge sort and heap sort techniques.*/
#include<stdio.h>
#include<math.h>
#define max 50
void swap(int*,int*);
void main()
{
int ch,i,j,lb,ub,n,midindex,a[max],c[max],c1;
char c2;
void bublsort_non_rec(int[],int);
void bubble_sort_rec(int[],int,int);
void inssort_non_rec(int[],int);
void insertion_sort_rec(int[],int,int);
void selsort_non_rec(int[],int);
void selection_sort_rec(int[],int,int);
void quick_sort_rec(int[],int,int);
void quick_sort_non_rec(int[],int,int);
void m_sort_rec(int[],int,int);
void mergesort_non_rec(int[],int,int);
void heapsort(int[],int,int);
while(1)
{
printf("Give number of data in the array : ");
scanf("%d",&n);
lb=0;
ub=n-1;
printf("Enter the elements of the array : ");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("n.....Menu.....");
printf("n1>Bubble sort.n2>Insertion sort.n3>Selection sortn4>Quicksort.n5>Mergesort.n6>HeapsortnEnter choice : ");
scanf("n%d",&ch);
switch(ch)
{
case 1:
{
printf("n1>Non-recursive.n2>RecursivenEnter choice : ");
scanf("%d",&c1);
if(c1==1)
bublsort_non_rec(a,n);
else if(c1==2)
bubble_sort_rec(a,lb,ub);
else
{
printf("Invalid choice givenn");
return;
}
break;
}
case 2:
{
printf("n1>Non-recursive.n2>RecursivenEnter choice : ");
scanf("%d",&c1);
if(c1==1)
inssort_non_rec(a,n);
else if(c1==2)
insertion_sort_rec(a,lb,ub);
else
{
printf("Invalid choice givenn");
return;
}
break;
}
case 3:
{
printf("n1>Non-recursive.n2>RecursivenEnter choice : ");
scanf("%d",&c1);
if(c1==1)
selsort_non_rec(a,n);
else if(c1==2)
selection_sort_rec(a,lb,ub);
else
{
printf("Invalid choice givenn");
return;
}
break;
}
case 4:
{
printf("n1>Non-recursive.n2>RecursivenEnter choice : ");
scanf("%d",&c1);
if(c1==1)
quick_sort_non_rec(a,lb,ub);
else if(c1==2)
quick_sort_rec(a,lb,ub);
else
{
printf("Invalid choice givenn");
return;
}
break;
}
case 5:
{
printf("n1>Non-recursiven2>RecursivenEnter choice : ");
scanf("%d",&c1);
if(c1==1)
mergesort_non_rec(a,lb,ub);
else if(c1==2)
m_sort_rec(a,lb,ub);
else
{
printf("Invalid choice givenn");
return;
}
break;
}
case 6:
{
heapsort(a,lb,ub);
break;
}
default:
{
printf("Invalid choice givenn");
return;
}
}
printf("nThe sorted array is : n");
for(i=0;i<n;i++)
printf("%dt",a[i]);
printf("n");
printf("Do you want to sort a new set of data(Y/N):");
scanf(" %c",&c2);
switch(c2)
{
case 'y':
case 'Y':break;
case 'n':
case 'N':printf("You have chosen to exit from the program.n");
return;
default: printf("nINVALID CHOICE!!!!n");
return;
}
printf(".....Enter a new set of data.....n");
}
}
/*Non recursive bubble sort*/
void bublsort_non_rec(int a[],int n)
{
int i,j,f;
void swap(int*,int*);
for(i=1,f=0;i<=n-1;i++)
{
/*compare elements side by side and move highest element of unsorted part to start of sorted part*/
for(j=0;j<=n-i-1;j++)
{
if(a[j]>a[j+1])
{
swap(&a[j],&a[j+1]);
f=1;
}
}
if(f=0)/*stop unnecessary looping if the list is already sorted*/
break;
}
}
/*This function swaps two elements passed as parameters*/
void swap(int*p,int*q)
{
int temp;
temp=*p;
*p=*q;
*q=temp;
}
/*Non recursive insertion sort*/
void inssort_non_rec(int a[],int n)
{
int i,j,key;
for(i=1;i<=n-1;i++)
{
/*insert a[i] into the sorted sequence a[lb]..a[i-1]*/
key=a[i];
for(j=i-1;j>=0&&a[j]>key;j--)
a[j+1]=a[j];
a[j+1]=key;
}
}
/*Non recursive selection sort*/
void selsort_non_rec(int a[],int n)
{
int i,j,max_index,temp;
for(i=n-1;i>0;i--)
{
/*find the maximum in a[lb]..a[i] */
max_index=i;
for(j=0;j<i;j++)
if(a[j]>a[max_index])
max_index=j;
if(i!=max_index)/*swap the maximum of a[lb]..a[i] with a[i] if they are different*/
swap(&a[i],&a[max_index]);
}
}
/* This algorithm partition the list into two parts with respect to a pivot element, so that the elements of left and right partition of pivot are less than and greater than or equal to the pivot element respectively*/
int partition(int lb,int ub,int a[])
{
int i,j;
for(i=lb,j=lb+1;j<=ub;j++)
if(a[lb]>a[j])
swap(&a[++i],&a[j]);
swap(&a[lb],&a[i]);
return i;
}
/*Recursive quick sort*/
void quick_sort_rec(int a[],int lb,int ub)
{
int p;
int partition(int,int,int[]);
/*check for empty or single element list*/
if(lb>=ub)
return;/*stop recursion*/
p=partition(lb,ub,a);/*partition the list*/
quick_sort_rec(a,lb,p-1);/*continue recursion for left partition*/
quick_sort_rec(a,p+1,ub);/*continue recursion for right partition*/
}
/*Recursive merge sort*/
void m_sort_rec(int a[],int lb,int ub)
{
int mid;
void merge(int[],int,int,int);
if(lb>=ub)
return;/*Stop recursion*/
mid=(lb+ub)/2;
m_sort_rec(a,lb,mid);/*Self-calling*/
m_sort_rec(a,mid+1,ub);/*Self-calling*/
merge(a,lb,mid,ub);
}
/*merge two sorted sub lists into one sorted list*/
void merge(int a[],int lb,int mid,int ub)
{
int i,j,k,tmp[50];
for(i=lb,j=mid+1,k=lb;i<=mid&&j<=ub;k++)
{
if(a[i]>=a[j])
{
tmp[k]=a[j];
j++;
}
else
{
tmp[k]=a[i];
i++;
}
}
while(j<=ub)
{
tmp[k]=a[j];
j++;
k++;
}
while(i<=mid)
{
tmp[k]=a[i];
i++;
k++;
}
for(k=lb;k<=ub;k++)
a[k]=tmp[k];
}
/*Non recursive heap sort*/
void heapsort(int a[],int lb,int ub)
{
int i;
void create_heap(int[],int,int,int,int);
void del_heap(int[],int,int,int);
for(i=lb;i<=ub;i++)
{
create_heap(a,i,a[i],lb,ub);/*Heap-creation with input elements*/
}
i=ub;
while(i>=lb)
{
del_heap(a,i+1,lb,ub);/*Deletion from heap is always in descending order*/
i--;
}
}
/*Function to create a heap with input elements*/
void create_heap(int a[],int heapsize,int data,int lb,int ub)
{
int i,p;
int parent(int);
i=lb+heapsize;
a[i]=data;
while(i>lb&&a[p=parent(i)]<a[i])
{
swap(&a[p],&a[i]);
i=p;
}
}
/*Function to delete elements from previously created heap*/
void del_heap(int a[],int heapsize,int lb,int ub)
{
int data,i,l,r,max_child;
int left(int);
int right(int);
swap(&a[lb],&a[heapsize-1]);
i=lb;
heapsize--;
while(1)
{
if((l=left(i))>=heapsize)
break;
if((r=right(i))>=heapsize)
max_child=l;
else
max_child=(a[l]>a[r])?l:r;
if(a[i]>=a[max_child])
break;
swap(&a[i],&a[max_child]);
i=max_child;
}
}
/*This function returns parent index of an element in the list*/
int parent(int i)
{
float p;
p=((float)i/2.0)-1.0;
return ceil(p);
}
/*This function returns left child index of an element in the list*/
int left(int i)
{
return 2*i+1;
}
/*This function returns right child index of an element in the list*/
int right(int i)
{
return 2*i+2;
}
/*Recursive bubble sort*/
void bubble_sort_rec(int a[],int lb,int ub)
{
int j,f;
if(lb>=ub)/*Check for terminating condition*/
return;
/*compare elements side by side and move highest element to the end*/
for(j=lb,f=0;j<=lb+ub-1;j++)
{
if(a[j]>a[j+1])
{
swap(&a[j],&a[j+1]);
f=1;
}
}
/*Continue recursion if the list is not yet sorted*/
if(f=1)
bubble_sort_rec(a,lb,ub-1);/*Self calling*/
}
/*Recursive insertion sort*/
void insertion_sort_rec(int a[],int lb,int ub)
{
int j,key;
if(lb>=ub)/*Check for terminating condition*/
return;
insertion_sort_rec(a,lb,ub-1);/*Self calling*/
/*Insert a[ub] into the sorted sequence a[lb]..a[ub-1]*/
key=a[ub];
for(j=ub-1;j>=lb && a[j]>key;j--)
a[j+1]=a[j];
a[j+1]=key;
}
/*Recursive selection sort*/
void selection_sort_rec(int a[],int lb,int ub)
{
int j,max_index;
if(lb>=ub)/*Check for terminating condition*/
return;
/*Find the maximum in a[lb]..a[ub]*/
max_index=ub;
for(j=0;j<ub;j++)
{
if(a[j]>a[max_index])
max_index=j;
}
/*Swap the maximum of a[lb]..a[ub] with a[ub] if they are different*/
if(ub!=max_index)
swap(&a[ub],&a[max_index]);
selection_sort_rec(a,lb,ub-1);/*Self calling*/
}
/*Non recursive merge sort*/
void mergesort_non_rec(int a[],int lb,int ub)
{
int k,i;
int min(int,int);
for(k=1;k<=(ub-lb+1);k*=2)
{
for(i=lb;i<=(ub-k);i+=2*k)
merge(a,i,(i+k-1),min((i+2*k-1),ub));/*Every two adjacent blocks are merged*/
}
}
/*This function returns minimum of two elements*/
int min(int a,int b)
{
if(a>b)
return b;
else
return a;
}
/*Non recursive quick sort*/
void quick_sort_non_rec(int a[],int lb,int ub)
{
int stack[max],p,top=0;
void push(int[],int,int*);
int pop(int[],int*);
int stack_empty(int*);
push(stack,lb,&top);
push(stack,ub,&top);
while(stack_empty(&top)==0)/*This loop will continue until stack is empty*/
{
/*Initialize the current sub list*/
ub=pop(stack,&top);
lb=pop(stack,&top);
/*check for empty or single element sub list*/
if(lb>=ub)
continue;
/*Partition the sub list*/
p=partition(lb,ub,a);
/*Set the left partition*/
push(stack,lb,&top);
push(stack,p-1,&top);
/*Set the right partition*/
push(stack,p+1,&top);
push(stack,ub,&top);
}
}
/*Function to insert elements into stack*/
void push(int stack[],int data,int* top)
{
if(*top>=max)
{
printf("Error overflow.n");
return;
}
stack[*top]=data;
(*top)++;
}
/*Function to delete elements from stack*/
int pop(int stack[],int *top)
{
int data;
(*top)--;
data=stack[*top];
return data;
}
/*This function returns 1 if stack is empty else returns 0*/
int stack_empty(int *top)
{
if(*top==0)
return 1;
else
return 0;
}
Output :
Give number of data in the array : 7
Enter the elements of the array : 15 21 8 51 22 2 45
.....Menu.....
1>Bubble sort.
2>Insertion sort.
3>Selection sort
4>Quicksort.
5>Mergesort.
6>Heapsort
Enter choice : 1
1>Non-recursive.
2>Recursive
Enter choice : 2
The sorted array is :
2 8 15 21 22 45 51
Do you want to sort a new set of data(Y/N):y
.....Enter a new set of data.....
Give number of data in the array : 5
Enter the elements of the array : 4 84 21 0 6
.....Menu.....
1>Bubble sort.
2>Insertion sort.
3>Selection sort
4>Quicksort.
5>Mergesort.
6>Heapsort
Enter choice : 2
1>Non-recursive.
2>Recursive
Enter choice : 2
The sorted array is :
0 4 6 21 84
Do you want to sort a new set of data(Y/N):y
.....Enter a new set of data.....
Give number of data in the array : 6
Enter the elements of the array : 51 15 20 7 -2 96
.....Menu.....
1>Bubble sort.
2>Insertion sort.
3>Selection sort
4>Quicksort.
5>Mergesort.
6>Heapsort
Enter choice : 3
1>Non-recursive.
2>Recursive
Enter choice : 2
The sorted array is :
-2 7 15 20 51 96
Do you want to sort a new set of data(Y/N):y
.....Enter a new set of data.....
Give number of data in the array : 6
Enter the elements of the array : 17 19 20 -5 0 4
.....Menu.....
1>Bubble sort.
2>Insertion sort.
3>Selection sort
4>Quicksort.
5>Mergesort.
6>Heapsort
Enter choice : 4
1>Non-recursive.
2>Recursive
Enter choice : 1
The sorted array is :
-5 0 4 17 19 20
Do you want to sort a new set of data(Y/N):y
.....Enter a new set of data.....
Give number of data in the array : 5
Enter the elements of the array : 26 -1 -5 9 96
.....Menu.....
1>Bubble sort.
2>Insertion sort.
3>Selection sort
4>Quicksort.
5>Mergesort.
6>Heapsort
Enter choice : 4
1>Non-recursive.
2>Recursive
Enter choice : 2
The sorted array is :
-5 -1 9 26 96
Do you want to sort a new set of data(Y/N):y
.....Enter a new set of data.....
Give number of data in the array : 5
Enter the elements of the array : 23 21 194 55 54
.....Menu.....
1>Bubble sort.
2>Insertion sort.
3>Selection sort
4>Quicksort.
5>Mergesort.
6>Heapsort
Enter choice : 5
1>Non-recursive
2>Recursive
Enter choice : 1
The sorted array is :
21 23 54 55 194
Do you want to sort a new set of data(Y/N):y
.....Enter a new set of data.....
Give number of data in the array : 6
Enter the elements of the array : 85 48 2 0 -9 66
.....Menu.....
1>Bubble sort.
2>Insertion sort.
3>Selection sort
4>Quicksort.
5>Mergesort.
6>Heapsort
Enter choice : 5
1>Non-recursive
2>Recursive
Enter choice : 2
The sorted array is :
-9 0 2 48 66 85
Do you want to sort a new set of data(Y/N):y
.....Enter a new set of data.....
Give number of data in the array : 6
Enter the elements of the array : 19 32 0 -5 7 45
.....Menu.....
1>Bubble sort.
2>Insertion sort.
3>Selection sort
4>Quicksort.
5>Mergesort.
6>Heapsort
Enter choice : 6
The sorted array is :
-5 0 7 19 32 45
Do you want to sort a new set of data(Y/N):n
You have chosen to exit from the program.
Discussions :
● In classical bubble sort worst case, average case, best case complexity is O(n2).
We can refine bubble sort by introducing a flag variable which is initially 0. If the list is previously sorted then after 1st pass this flag is not changed to 1 and the program is terminated. In this case, time complexity is O(n).
● In selection sort worst case, average case, best case complexity is O(n2).
● In insertion sort worst case and average case complexity is O(n2), and best case complexity is O(n).
● In heap sort worst case, average case, best case complexity in O(nlog n).
● The best case complexity of quick sort is O(log n). The average case complexity is O(nlog n). But the worst case situation arises when the file is sorted itself. So the worst case complexity of quick Sort is O(n2).
● The efficiency of the Quick Sort method can be improved by :
1. Choosing a better pivot element.
2. Using better algorithm for small sub list.
3. Eliminating recursion.
● In merge sort worst case, best case, average case complexity is O(nlog n).
● Non-recursive merge sort is also called bottom up sort.
● Recursive version of heap sort is not implemented in the above program.
Write a Menu driven C program to sort a list of elements stored in an array; using bubble sort, insertion sort, selection sort, quick sort, merge sort and heap sort techniques.
Theory :
Sorting means arranging a set of data in some order. There are different sorting methods that are used to sort the data in ascending or descending order. These methods can be divided into two categories. They are as follows :-
1. Internal sorting : If all the data is to be sorted, can be accommodated at a time in memory then internal sorting methods are used.
2. External sorting : When the data to be sorted is so large that some of data is present in the memory and some is kept in auxiliary memory (hard disk, floppy, tape,etc), then external sorting methods are used.
● Selection Sort : This is the simplest method of sorting. In this method (ascending order), the last element is compared with all other elements. If the last element is found to be less than the compared element then they are interchanged. So after 1st iteration the largest element is placed at the last position. The same procedure is repeated for the second last element and so on.
● Bubble Sort : In this method (ascending order), we begin by comparing the 0th element is compared with the 1st element. If it is found to be greater than 1st element then they are interchanged. In the same way all elements (excluding last) are compared with their next elements and are interchanged if required. In this way after 1st iteration largest element placed at last position and after 2nd iteration second largest element gets placed at the 2nd last position and so on. In this way we get a a sorted list.
● Insertion Sort : Insertion sort is implemented by inserting a particular element at the appropriate position. In this method the first iteration starts with comparison of 1st element with 0th element. In the second iteration 2nd element is compared with the 0th and 1st element. In general, in every iteration an element is compared with all elements before it. During comparison if it is found that the element in question can be inserted at a suitable position then space is created for it by shifting the other elements one position to the right and insert the element at the suitable position. This procedure is replaced for all the elements in the array.
● Heap Sort : In this method, a tree structure called heap is used. A heap is type of a binary tree. An ordered balanced binary tree is called a min heap where the value at the root of any sub-tree is less than or equal to the value of either of its children. An ordered balanced binary tree is called a max-heap, when the value at the root of any sub-tree is more than or equal to the value of either of its children.
Basically, there are two phases involved in sorting the elements using heap sort algorithm. They are as follows :-
1. Construct a heap by adjusting the array elements.
2. Repeatedly eliminate the root element of the heap by shifting it to the end of the array and then restore the heap structure with remaining elements.
The root element of a max heap is always the largest element. The sorting ends when all the root element of each successive heap has been moved to the end of the array. The resulting array now contains a sorted list.
● Quick Sort : Quick sort is a very popular sorting method. The name comes from the fact that in general, quick sort can sort a list of data elements significantly faster than any of the common sorting algorithm.
The basic strategy of quick sort is to “divide and conquer”. In this method from the given elements first we have to pick a splitting value known as pivot element. Then all the elements are spited into two piles (not necessarily containing the same number of elements). Then two piles are divided into 4 piles. The same approach is used to sort each smaller piles. This strategy based on recursion. Quick sort is also known as partition exchange sort.
●Merge sort: Merging means combining two sorted lists into one sorted list. For this the elements from both the sorted lists are compared. The smaller of both the elements is then sorted in the third array. The sorting is complete when all the elements from both the lists are placed in the third list.
Among the above six sorting techniques bubble sort, insertion sort, selection sort and heap sort are generally implemented non-recursively and quick sort and merge sort are generally implemented recursively. However, we can implement recursive algorithms for non-recursive versions and vice-versa.
In order to make bubble sort, insertion sort and selection sort recursive, the outer loops are eliminated from the non-recursive versions and the functions are called recursively decreasing upper bound of the array by 1.
We use stack data structure to implement non-recursive quick sort. And in non-recursive merge sort the array is sorted by a sequence of passes. During each pass, the array is divided into blocks. Every two adjacent blocks are merged (as in normal merge sort), and the next pass is made with a block size twice larger of the previous pass.
Algorithm :
Selection sort
/*non recursive selection sort*/
selection_sort(a[lb..ub])
{
for(i=ub;i>lb;i--)
{
/*find the maximum in a[lb]..a[i] */
max_index = i;
for(j=lb ; j<i ; j++)
if(a[j]>a[max_index])
max_index = j;
/*swap the maximum of a[lb]..a[i] with a[i] if they are different*/
if(i!=max_index)
swap(a[i],a[max_index]);
}
}
/*recursive selection sort*/
selection_sort_rec(a[lb..ub])
{
if(lb>=ub) End Algorithm;
max_index = ub;
for(j=0;j<ub;j++)
{
if(a[j]>a[max_index])
max_index = j;
}
if(ub!=max_index)
swap(a[ub],a[max_index]);
selection_sort_rec(a,lb,ub-1);
}
Bubble sort
/*non recursive bubble sort*/
bubble_sort(a[lb..ub])
{
for(i=lb+1 ; i<=ub ; i++)
{
/*compare side by side and move highest of unsorted part to start of sorted part*/
for(j= lb ; f=false ; j<=lb+ub-i ; j++)
if(a[j]>a[j+1])
{
swap(a[j],a[j+1]);
f = true;
}
/*stop unnecessary looping if the list already became sorted*/
if(f=false) exit;
}
}
/*recursive bubble sort*/
bubble_sort_rec(a[lb..ub])
{
if(lb>=ub)End Algorithm;
for(j=lb,f=0;j<=lb+ub-1;j++)
{
if(a[j]>a[j+1])
{
swap(a[j],a[j+1]);
f = 1;
}
}
if(f=1)
bubble_sort_rec(a,lb,ub-1);
}
Insertion sort
/*non recursive insertion sort*/
insertion_sort(a[lb..ub])
{
for(i= lb+1 ; i<=ub; i++)
{
/* insert a[i] into the sorted sequence a[lb]..a[i-1]*/
key=a[i];
for(j=i-1; j>=lb && a[j]>key ; j--)
a[j+1] = a[j];
a[j+1] = key;
}
}
/*recursive insertion sort*/
insertion_sort_rec(a[lb..ub])
{
if(lb>=ub) End Algorithm;
insertion_sort_rec(a,lb,ub-1);
key = a[ub];
for(j=ub-1;j>=lb && a[j]>key;j--)
a[j+1] = a[j];
a[j+1] = key;
}
Heap sort
/*non recursive heap sort*/
heap_sort(a[lb..ub])
{
for(i=lb+1; i<=ub; i++)
for(t=i ; t>lb && a[t]>a[p=parent_index(t)]; t=p)
swap( a[t], a[p]);
for(i=ub; i>lb; i--)
{
swap(a[lb], a[i]);
for(t=lb; (l=left_child_index(t))<i ;t=greater_child_index)
{
r = right_child_index(t);
greater_child_index=(r<i && a[l]<a[r])? r:1;
if(a[t]>a[greater_child_index]) break;
swap(a[t],a[greater_child_index]);
}
}
}
Quick sort
/* recursive quick sort*/
quick_sort(a[lb..ub])
{
/*check for empty or single element list*/
if(lb>=ub)
End algorithm; /*stop recursion*/
p = partition(a[lb..ub]); /*partition the list*/
quick_sort(a[lb..(p-1)]); /*continue recursion for left partition*/
quick_sort(a[(p+1)..ub]); /*continue recursion for right partition*/
}
/*non-recursive quick sort*/
quick_sort_non_rec(a[lb..ub])
{
push(lb);
push(ub);
while(stack is not empty)/*Iteration will be continued until stack is empty*/
{
ub = pop(stack);
lb = pop(stack);
/*Check for empty or single element list*/
if(lb>=ub)
continue;
p = partition(lb,ub,a); /*partition the list*/
push(lb);
push(p-1);
push(p+1);
push(ub);
}
}
/* This algorithm partitions the list into two parts with respect to a pivot element, so that the elements of left and right partition of pivot are less than and greater than or equal to the pivot element respectively*/
partition(a[lb..ub])
{
swap(a[lb],a[(lb+ub)/2]);
small_end = lb;
for(large_end=lb; large_end<ub; large_end++)
{
if(a[lb]>a[large_end+1])
{
small_end++;
swap(a[small_end],a[large_end+1]);
}
}
swap(a[lb], a[small_end]);
return small_end;
}
Merge sort
/*recursive merge sort*/
merge_sort(a[lb..ub])
{
if(lb>=ub) end_algorithm;
mid = floor((lb+ub)/2);
merge_sort(a[lb..mid]);
merge_sort(a[(mid+1)..ub]);
merge(a[lb..ub], mid);
}
/*non-recursive merge sort*/
mergesort_non_rec(a[lb..ub])
{
for(k=1;k<=(ub-lb+1);k=2k)
{
for(i=lb;i<=(ub-k);i+=2k)
{
merge(a,i,(i+k-1),min((i+2k-1),ub));
}
}
}
/* merge two sorted sub lists into one sorted list*/
merge(a[lb..ub], mid)
{
for(i=lb; j=mid+1; k=lb; i<=mid && j<=ub;k++)
temp[k] = (a[i]<a[j] ? a[i+1]:a[j+1]);
while(i<=mid)
temp[k+1] = a[i+1];
while(j<=ub)
temp[k++] = a[j++];
for(i=lb;i<=ub;i++)
a[i] = temp[i];
}
PROGRAM LISTING:
/*C program to sort a list of elements stored in an array data structure; using bubble sort, insertion sort, selection sort, quick sort, merge sort and heap sort techniques.*/
#include<stdio.h>
#include<math.h>
#define max 50
void swap(int*,int*);
void main()
{
int ch,i,j,lb,ub,n,midindex,a[max],c[max],c1;
char c2;
void bublsort_non_rec(int[],int);
void bubble_sort_rec(int[],int,int);
void inssort_non_rec(int[],int);
void insertion_sort_rec(int[],int,int);
void selsort_non_rec(int[],int);
void selection_sort_rec(int[],int,int);
void quick_sort_rec(int[],int,int);
void quick_sort_non_rec(int[],int,int);
void m_sort_rec(int[],int,int);
void mergesort_non_rec(int[],int,int);
void heapsort(int[],int,int);
while(1)
{
printf("Give number of data in the array : ");
scanf("%d",&n);
lb=0;
ub=n-1;
printf("Enter the elements of the array : ");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("n.....Menu.....");
printf("n1>Bubble sort.n2>Insertion sort.n3>Selection sortn4>Quicksort.n5>Mergesort.n6>HeapsortnEnter choice : ");
scanf("n%d",&ch);
switch(ch)
{
case 1:
{
printf("n1>Non-recursive.n2>RecursivenEnter choice : ");
scanf("%d",&c1);
if(c1==1)
bublsort_non_rec(a,n);
else if(c1==2)
bubble_sort_rec(a,lb,ub);
else
{
printf("Invalid choice givenn");
return;
}
break;
}
case 2:
{
printf("n1>Non-recursive.n2>RecursivenEnter choice : ");
scanf("%d",&c1);
if(c1==1)
inssort_non_rec(a,n);
else if(c1==2)
insertion_sort_rec(a,lb,ub);
else
{
printf("Invalid choice givenn");
return;
}
break;
}
case 3:
{
printf("n1>Non-recursive.n2>RecursivenEnter choice : ");
scanf("%d",&c1);
if(c1==1)
selsort_non_rec(a,n);
else if(c1==2)
selection_sort_rec(a,lb,ub);
else
{
printf("Invalid choice givenn");
return;
}
break;
}
case 4:
{
printf("n1>Non-recursive.n2>RecursivenEnter choice : ");
scanf("%d",&c1);
if(c1==1)
quick_sort_non_rec(a,lb,ub);
else if(c1==2)
quick_sort_rec(a,lb,ub);
else
{
printf("Invalid choice givenn");
return;
}
break;
}
case 5:
{
printf("n1>Non-recursiven2>RecursivenEnter choice : ");
scanf("%d",&c1);
if(c1==1)
mergesort_non_rec(a,lb,ub);
else if(c1==2)
m_sort_rec(a,lb,ub);
else
{
printf("Invalid choice givenn");
return;
}
break;
}
case 6:
{
heapsort(a,lb,ub);
break;
}
default:
{
printf("Invalid choice givenn");
return;
}
}
printf("nThe sorted array is : n");
for(i=0;i<n;i++)
printf("%dt",a[i]);
printf("n");
printf("Do you want to sort a new set of data(Y/N):");
scanf(" %c",&c2);
switch(c2)
{
case 'y':
case 'Y':break;
case 'n':
case 'N':printf("You have chosen to exit from the program.n");
return;
default: printf("nINVALID CHOICE!!!!n");
return;
}
printf(".....Enter a new set of data.....n");
}
}
/*Non recursive bubble sort*/
void bublsort_non_rec(int a[],int n)
{
int i,j,f;
void swap(int*,int*);
for(i=1,f=0;i<=n-1;i++)
{
/*compare elements side by side and move highest element of unsorted part to start of sorted part*/
for(j=0;j<=n-i-1;j++)
{
if(a[j]>a[j+1])
{
swap(&a[j],&a[j+1]);
f=1;
}
}
if(f=0)/*stop unnecessary looping if the list is already sorted*/
break;
}
}
/*This function swaps two elements passed as parameters*/
void swap(int*p,int*q)
{
int temp;
temp=*p;
*p=*q;
*q=temp;
}
/*Non recursive insertion sort*/
void inssort_non_rec(int a[],int n)
{
int i,j,key;
for(i=1;i<=n-1;i++)
{
/*insert a[i] into the sorted sequence a[lb]..a[i-1]*/
key=a[i];
for(j=i-1;j>=0&&a[j]>key;j--)
a[j+1]=a[j];
a[j+1]=key;
}
}
/*Non recursive selection sort*/
void selsort_non_rec(int a[],int n)
{
int i,j,max_index,temp;
for(i=n-1;i>0;i--)
{
/*find the maximum in a[lb]..a[i] */
max_index=i;
for(j=0;j<i;j++)
if(a[j]>a[max_index])
max_index=j;
if(i!=max_index)/*swap the maximum of a[lb]..a[i] with a[i] if they are different*/
swap(&a[i],&a[max_index]);
}
}
/* This algorithm partition the list into two parts with respect to a pivot element, so that the elements of left and right partition of pivot are less than and greater than or equal to the pivot element respectively*/
int partition(int lb,int ub,int a[])
{
int i,j;
for(i=lb,j=lb+1;j<=ub;j++)
if(a[lb]>a[j])
swap(&a[++i],&a[j]);
swap(&a[lb],&a[i]);
return i;
}
/*Recursive quick sort*/
void quick_sort_rec(int a[],int lb,int ub)
{
int p;
int partition(int,int,int[]);
/*check for empty or single element list*/
if(lb>=ub)
return;/*stop recursion*/
p=partition(lb,ub,a);/*partition the list*/
quick_sort_rec(a,lb,p-1);/*continue recursion for left partition*/
quick_sort_rec(a,p+1,ub);/*continue recursion for right partition*/
}
/*Recursive merge sort*/
void m_sort_rec(int a[],int lb,int ub)
{
int mid;
void merge(int[],int,int,int);
if(lb>=ub)
return;/*Stop recursion*/
mid=(lb+ub)/2;
m_sort_rec(a,lb,mid);/*Self-calling*/
m_sort_rec(a,mid+1,ub);/*Self-calling*/
merge(a,lb,mid,ub);
}
/*merge two sorted sub lists into one sorted list*/
void merge(int a[],int lb,int mid,int ub)
{
int i,j,k,tmp[50];
for(i=lb,j=mid+1,k=lb;i<=mid&&j<=ub;k++)
{
if(a[i]>=a[j])
{
tmp[k]=a[j];
j++;
}
else
{
tmp[k]=a[i];
i++;
}
}
while(j<=ub)
{
tmp[k]=a[j];
j++;
k++;
}
while(i<=mid)
{
tmp[k]=a[i];
i++;
k++;
}
for(k=lb;k<=ub;k++)
a[k]=tmp[k];
}
/*Non recursive heap sort*/
void heapsort(int a[],int lb,int ub)
{
int i;
void create_heap(int[],int,int,int,int);
void del_heap(int[],int,int,int);
for(i=lb;i<=ub;i++)
{
create_heap(a,i,a[i],lb,ub);/*Heap-creation with input elements*/
}
i=ub;
while(i>=lb)
{
del_heap(a,i+1,lb,ub);/*Deletion from heap is always in descending order*/
i--;
}
}
/*Function to create a heap with input elements*/
void create_heap(int a[],int heapsize,int data,int lb,int ub)
{
int i,p;
int parent(int);
i=lb+heapsize;
a[i]=data;
while(i>lb&&a[p=parent(i)]<a[i])
{
swap(&a[p],&a[i]);
i=p;
}
}
/*Function to delete elements from previously created heap*/
void del_heap(int a[],int heapsize,int lb,int ub)
{
int data,i,l,r,max_child;
int left(int);
int right(int);
swap(&a[lb],&a[heapsize-1]);
i=lb;
heapsize--;
while(1)
{
if((l=left(i))>=heapsize)
break;
if((r=right(i))>=heapsize)
max_child=l;
else
max_child=(a[l]>a[r])?l:r;
if(a[i]>=a[max_child])
break;
swap(&a[i],&a[max_child]);
i=max_child;
}
}
/*This function returns parent index of an element in the list*/
int parent(int i)
{
float p;
p=((float)i/2.0)-1.0;
return ceil(p);
}
/*This function returns left child index of an element in the list*/
int left(int i)
{
return 2*i+1;
}
/*This function returns right child index of an element in the list*/
int right(int i)
{
return 2*i+2;
}
/*Recursive bubble sort*/
void bubble_sort_rec(int a[],int lb,int ub)
{
int j,f;
if(lb>=ub)/*Check for terminating condition*/
return;
/*compare elements side by side and move highest element to the end*/
for(j=lb,f=0;j<=lb+ub-1;j++)
{
if(a[j]>a[j+1])
{
swap(&a[j],&a[j+1]);
f=1;
}
}
/*Continue recursion if the list is not yet sorted*/
if(f=1)
bubble_sort_rec(a,lb,ub-1);/*Self calling*/
}
/*Recursive insertion sort*/
void insertion_sort_rec(int a[],int lb,int ub)
{
int j,key;
if(lb>=ub)/*Check for terminating condition*/
return;
insertion_sort_rec(a,lb,ub-1);/*Self calling*/
/*Insert a[ub] into the sorted sequence a[lb]..a[ub-1]*/
key=a[ub];
for(j=ub-1;j>=lb && a[j]>key;j--)
a[j+1]=a[j];
a[j+1]=key;
}
/*Recursive selection sort*/
void selection_sort_rec(int a[],int lb,int ub)
{
int j,max_index;
if(lb>=ub)/*Check for terminating condition*/
return;
/*Find the maximum in a[lb]..a[ub]*/
max_index=ub;
for(j=0;j<ub;j++)
{
if(a[j]>a[max_index])
max_index=j;
}
/*Swap the maximum of a[lb]..a[ub] with a[ub] if they are different*/
if(ub!=max_index)
swap(&a[ub],&a[max_index]);
selection_sort_rec(a,lb,ub-1);/*Self calling*/
}
/*Non recursive merge sort*/
void mergesort_non_rec(int a[],int lb,int ub)
{
int k,i;
int min(int,int);
for(k=1;k<=(ub-lb+1);k*=2)
{
for(i=lb;i<=(ub-k);i+=2*k)
merge(a,i,(i+k-1),min((i+2*k-1),ub));/*Every two adjacent blocks are merged*/
}
}
/*This function returns minimum of two elements*/
int min(int a,int b)
{
if(a>b)
return b;
else
return a;
}
/*Non recursive quick sort*/
void quick_sort_non_rec(int a[],int lb,int ub)
{
int stack[max],p,top=0;
void push(int[],int,int*);
int pop(int[],int*);
int stack_empty(int*);
push(stack,lb,&top);
push(stack,ub,&top);
while(stack_empty(&top)==0)/*This loop will continue until stack is empty*/
{
/*Initialize the current sub list*/
ub=pop(stack,&top);
lb=pop(stack,&top);
/*check for empty or single element sub list*/
if(lb>=ub)
continue;
/*Partition the sub list*/
p=partition(lb,ub,a);
/*Set the left partition*/
push(stack,lb,&top);
push(stack,p-1,&top);
/*Set the right partition*/
push(stack,p+1,&top);
push(stack,ub,&top);
}
}
/*Function to insert elements into stack*/
void push(int stack[],int data,int* top)
{
if(*top>=max)
{
printf("Error overflow.n");
return;
}
stack[*top]=data;
(*top)++;
}
/*Function to delete elements from stack*/
int pop(int stack[],int *top)
{
int data;
(*top)--;
data=stack[*top];
return data;
}
/*This function returns 1 if stack is empty else returns 0*/
int stack_empty(int *top)
{
if(*top==0)
return 1;
else
return 0;
}
Output :
Give number of data in the array : 7
Enter the elements of the array : 15 21 8 51 22 2 45
.....Menu.....
1>Bubble sort.
2>Insertion sort.
3>Selection sort
4>Quicksort.
5>Mergesort.
6>Heapsort
Enter choice : 1
1>Non-recursive.
2>Recursive
Enter choice : 2
The sorted array is :
2 8 15 21 22 45 51
Do you want to sort a new set of data(Y/N):y
.....Enter a new set of data.....
Give number of data in the array : 5
Enter the elements of the array : 4 84 21 0 6
.....Menu.....
1>Bubble sort.
2>Insertion sort.
3>Selection sort
4>Quicksort.
5>Mergesort.
6>Heapsort
Enter choice : 2
1>Non-recursive.
2>Recursive
Enter choice : 2
The sorted array is :
0 4 6 21 84
Do you want to sort a new set of data(Y/N):y
.....Enter a new set of data.....
Give number of data in the array : 6
Enter the elements of the array : 51 15 20 7 -2 96
.....Menu.....
1>Bubble sort.
2>Insertion sort.
3>Selection sort
4>Quicksort.
5>Mergesort.
6>Heapsort
Enter choice : 3
1>Non-recursive.
2>Recursive
Enter choice : 2
The sorted array is :
-2 7 15 20 51 96
Do you want to sort a new set of data(Y/N):y
.....Enter a new set of data.....
Give number of data in the array : 6
Enter the elements of the array : 17 19 20 -5 0 4
.....Menu.....
1>Bubble sort.
2>Insertion sort.
3>Selection sort
4>Quicksort.
5>Mergesort.
6>Heapsort
Enter choice : 4
1>Non-recursive.
2>Recursive
Enter choice : 1
The sorted array is :
-5 0 4 17 19 20
Do you want to sort a new set of data(Y/N):y
.....Enter a new set of data.....
Give number of data in the array : 5
Enter the elements of the array : 26 -1 -5 9 96
.....Menu.....
1>Bubble sort.
2>Insertion sort.
3>Selection sort
4>Quicksort.
5>Mergesort.
6>Heapsort
Enter choice : 4
1>Non-recursive.
2>Recursive
Enter choice : 2
The sorted array is :
-5 -1 9 26 96
Do you want to sort a new set of data(Y/N):y
.....Enter a new set of data.....
Give number of data in the array : 5
Enter the elements of the array : 23 21 194 55 54
.....Menu.....
1>Bubble sort.
2>Insertion sort.
3>Selection sort
4>Quicksort.
5>Mergesort.
6>Heapsort
Enter choice : 5
1>Non-recursive
2>Recursive
Enter choice : 1
The sorted array is :
21 23 54 55 194
Do you want to sort a new set of data(Y/N):y
.....Enter a new set of data.....
Give number of data in the array : 6
Enter the elements of the array : 85 48 2 0 -9 66
.....Menu.....
1>Bubble sort.
2>Insertion sort.
3>Selection sort
4>Quicksort.
5>Mergesort.
6>Heapsort
Enter choice : 5
1>Non-recursive
2>Recursive
Enter choice : 2
The sorted array is :
-9 0 2 48 66 85
Do you want to sort a new set of data(Y/N):y
.....Enter a new set of data.....
Give number of data in the array : 6
Enter the elements of the array : 19 32 0 -5 7 45
.....Menu.....
1>Bubble sort.
2>Insertion sort.
3>Selection sort
4>Quicksort.
5>Mergesort.
6>Heapsort
Enter choice : 6
The sorted array is :
-5 0 7 19 32 45
Do you want to sort a new set of data(Y/N):n
You have chosen to exit from the program.
Discussions :
● In classical bubble sort worst case, average case, best case complexity is O(n2).
We can refine bubble sort by introducing a flag variable which is initially 0. If the list is previously sorted then after 1st pass this flag is not changed to 1 and the program is terminated. In this case, time complexity is O(n).
● In selection sort worst case, average case, best case complexity is O(n2).
● In insertion sort worst case and average case complexity is O(n2), and best case complexity is O(n).
● In heap sort worst case, average case, best case complexity in O(nlog n).
● The best case complexity of quick sort is O(log n). The average case complexity is O(nlog n). But the worst case situation arises when the file is sorted itself. So the worst case complexity of quick Sort is O(n2).
● The efficiency of the Quick Sort method can be improved by :
1. Choosing a better pivot element.
2. Using better algorithm for small sub list.
3. Eliminating recursion.
● In merge sort worst case, best case, average case complexity is O(nlog n).
● Non-recursive merge sort is also called bottom up sort.
● Recursive version of heap sort is not implemented in the above program.
