Department of Computer Sci.

& Business Systems, SVPCET, Nagpur

Introduction : Bubble Sort

Bubble sorting is a simple sorting technique in which we arrange the elements of the list by forming pairs of adjacent
elements. That means we form the pair of the ith and (i+1)th element. If the order is ascending, we interchange the
elements of the pair if the first element of the pair is greater than the second element. That means for every pair
(list[i],list[i+1]) for i :=1 to (n−1) if list[i] > list[i+1], we need to interchange list[i] and list[i+1]. Carrying this out once will
move the element with the highest value to the last or nth position. Therefore, we repeat this process the next time with
the elements from the first to (n−1)th positions. This will bring the highest value from among the remaining (n−1) values
to the (n−1)th position. We repeat the process with the remaining (n−2) values and so on. Finally, we arrange the
elements in ascending order. This requires to perform (n−1) passes. In the first pass we have (n−1) pairs, in the second
pass we have (n−2) pairs, and in the last (or (n−1)th) pass, we have only one pair. Therefore, the number of probes or
comparisons that are required to be carried out is
(n-1)+ (n-2)+ (n-3)+ (n-4)+…….+1
=n(n-1)/2
and the order of the algorithm is O(n2).
Bubble Sort Program Snapshot
#include<stdio.h>
#include<conio.h>
#define MAX 5
void bubblesort(int *p,int size);
void main()
{
int i;
int arr[MAX];
clrscr();
printf("\n enter %d elements",MAX);
for(i=0;i<MAX;i++)
{ scanf("%d",&arr[i]); }
printf("\n array before sorting");
for(i=0;i<MAX;i++)
{ printf("\t %d",arr[i]); }
bubblesort(arr,MAX);
printf("\n array after sorting \n");
for(i=0;i<MAX;i++)
{ printf("\t %d",arr[i]); }
getch();
}
void bubblesort(int *p,int size)
{
int i,j,temp;
for(i=0;i<size-1;i++)
{
for(j=0;j<size-i-1;j++)
{
if(p[j]>p[j+1])
{
temp=p[j];
p[j]=p[j+1];
p[j+1]=temp;
}
}
}
}

Prof.Praveen Sen (+91 9823017805) Page 1

Department of Computer Sci. & Business Systems, SVPCET, Nagpur

Introduction : Selection Sort

Selection sort is not difficult to analyze compared to other sorting algorithms since none of the loops depend on the data
in the array. Selecting the lowest element requires scanning all n elements (this takes n − 1 comparisons) and then
swapping it into the first position. Finding the next lowest element requires scanning the remaining n − 1 elements and
so on, for (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n2) comparisons. Each of these scans requires one swap
for n − 1 elements (the final element is already in place).
Selection Sort Program Snap shot
#include<stdio.h>
#include<conio.h>
#define MAX 5
void sel_sort(int *p,int size);
void main()
{
int i;
int arr[MAX];
clrscr();
printf("\n enter %d elements",MAX);
for(i=0;i<MAX;i++)
{
scanf("%d",&arr[i]);
}
printf("\n array before sorting");
for(i=0;i<MAX;i++)
{
printf("\t %d",arr[i]);
}
sel_sort(arr,MAX);
printf("\n array after sorting \n");
for(i=0;i<MAX;i++)
{
printf("\t %d",arr[i]);
}
getch();
}
void sel_sort(int *p,int size)
{
int i,j,temp;
for(i=0;i<size-1;i++)
{
for(j=i+1;j<size;j++)
{
if(p[i]>p[j])
{
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
}
}
}

Prof.Praveen Sen (+91 9823017805) Page 2

Department of Computer Sci. & Business Systems, SVPCET, Nagpur

Introduction: QUICK SORT

In the quick sort method, an array a[1],…..,a[n] is sorted by selecting some value in the array as a key element. We then
swap the first element of the list with the key element so that the key will be in the first position. We then determine the
key's proper place in the list. The proper place for the key is one in which all elements to the left of the key are smaller
than the key, and all elements to the right are larger.
To obtain the key's proper position, we traverse the list in both directions using the indices i and j, respectively. We
initialize i to that index that is one more than the index of the key element. That is, if the list to be sorted has the indices
running from m to n, the key element is at index m, hence we initialize i to (m+1). The index i is incremented until we get
an element at the ith position that is greater than the key value. Similarly, we initialize j to n and go on decrementing j
until we get an element with a value less than the key's value.
We then check to see whether the values of i and j have crossed each other. If not, we interchange the elements at the
key (mth)position with the elements at the jth position. This brings the key element to the jth position, and we find that the
elements to its left are less than it, and the elements to its right are greater than it. Therefore we can split the list into two
sublists. The first sublist is composed of elements from the mth position to the (j–1)th position, and the second sublist
consists of elements from the (j+1)th position to the nth position. We then repeat the same procedure on each of the
sublists separately.
Quick Sort Program Snap Shot
void quicksort(int a[],int lower,int upper)
{
int i;
if(upper>lower)
{
i=split(a,lower,upper);
quicksort(a,lower,i-1);
quicksort(a,i+1,upper);
}
}

int split(int a[],int lower,int upper)

{
int i,p,q,t;
p=lower+1;
q=upper;
i=a[lower];
while(q>=p)
{
while(a[p]<i)
p++;
while(a[q]>i)
q--;
if(q>p)
{
t=a[p];
a[p]=a[q];
a[q]=t;
}
}
t=a[lower];
a[lower]=a[q];
a[q]=t;
return(q);
}

Prof.Praveen Sen (+91 9823017805) Page 3

Department of Computer Sci. & Business Systems, SVPCET, Nagpur

Introduction : Insertion Sort

Insertion sort is a sorting algorithm with an O(n2) running time. Although the worst case run time is the same as bubble
sort, but it is alot more applicable for smaller data sets. To understand this algorithm, it is very similar to how some
people sort their hand of cards.
Here is how it works:
 Assume the left of the array of the current item is already sorted, and the right side is not yet sorted.
 Start a loop starting with the 2nd item in the array (since an array of 1 item is sorted.)
 For each item, start a 2nd loop starting from the current item going backwards in the array.
 If current item is smaller than the item on the left, we compare to the next item on the left.
 Repeat the step above until the item is greater than the one before it and insert it.
 Do this for each item in the array.
Insertion Sort Snap Shot
#include<stdio.h>
#include<conio.h>
void insertion(int *a,int n);
void main()
{
int a[10];
int i;
clrscr();
printf("\n Enter any 10 numbers");
for(i=0;i<10;i++)
scanf("%d",&a[i]);
printf("\n Array before sorting\n");
for(i=0;i<10;i++)
printf(" %d",a[i]);
insertion(a,10);
printf("\n Array after sorting\n");
for(i=0;i<10;i++)
printf("\t%d",a[i]);
getch();
}
void insertion (int *p,int n)
{
int i,j,k,index,t;
for(i=1;i<n;i++)
{
index=p[i];
j=i;
while((j>0) && (p[j-1]>index))
{
t=p[j];
p[j]=p[j-1];
p[j-1]=t;
j--;

}
printf("\n");
for( k=0;k<n;k++)
printf(" %d",p[k]);
printf("\n");
}
}

Prof.Praveen Sen (+91 9823017805) Page 4

Department of Computer Sci. & Business Systems, SVPCET, Nagpur

Introduction : MERGE SORT

This is another sorting technique having the same average-case and worst-case time complexities, but requiring an
additional list of size n.
The technique that we use is the merging of the two sorted lists of size m and n to form a single sorted list of size (m +
n). Given a list of size n to be sorted, instead of viewing it to be one single list of size n, we start by viewing it to be n
lists each of size 1, and merge the first list with the second list to form a single sorted list of size 2.
Similarly, we merge the third and the fourth lists to form a second single sorted list of size 2, and so on. This completes
one pass. We then consider the first sorted list of size 2 and the second sorted list of size 2, and merge them to form a
single sorted list of size 4.
Similarly, we merge the third and the fourth sorted lists, each of size 2, to form the second single sorted list of size 4,
and so on. This completes the second pass.
In the third pass, we merge these adjacent sorted lists, each of size 4, to form sorted lists of size 8. We continue this
process until we finally obtain a single sorted list of size n
Merge Sort Program Snap Shot
mergesort(int a[], int low, int high) {
int mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high,mid);
}
return(0);
}
merge(int a[], int low, int high, int mid) {
int i, j, k, c[50];
i=low;
j=mid+1;
k=low;
while((i<=mid)&&(j<=high)) {
if(a[i]<a[j]) {
c[k]=a[i];
k++; i++;
}
else {
c[k]=a[j];
k++;
j++;
}
}
while(i<=mid){
c[k]=a[i];
k++; i++;
}
while(j<=high){
c[k]=a[j];
k++; j++;
}
for(i=low;i<k;i++) {
a[i]=c[i];
}
}

Prof.Praveen Sen (+91 9823017805) Page 5