+
Sorting Algorithms
Sorting is a process in which records are arranged
in ascending or descending order.
The process of sorting is essential for database
applications.
Real life example Of sort :
In telephone directory the names of the subscribers
and their phone numbers are written in alphabetical
order. The records of the list of these telephone
holders are to be sorted by their names.
Dictionary
Page 1
+
Types Of Sorting Algorithm
Bubble Sort
Selection Sort
Insertion Sort
Etc.
Page 2
+
Bubble Sort
Compare each element (except the last one) with its neighbor to the
right
If they are out of order, swap them
This puts the largest element at the very end
The last element is now in the correct and final place
Compare each element (except the last two) with its neighbor to the
right
If they are out of order, swap them
This puts the second largest element next to last
The last two elements are now in the correct and final place
Compare each element (except the last three) with its neighbor to the
right
If they are out of order, swap them
This puts the third largest element next to second largest
The last three elements are now in their correct and final places
Continue as above until you have no unsorted elements on the left
Page 3
+
Example of bubble sort
7 2 8 5 4 2 7 5 4 8 2 5 4 7 8 2 4 5 7 8
2 7 8 5 4 2 7 5 4 8 2 5 4 7 8 2 4 5 7 8
2 7 8 5 4 2 5 7 4 8 2 4 5 7 8 (done)
2 7 5 8 4 2 5 4 7 8
2 7 5 4 8
Page 4 4
+
Bubble Sort Code
#include<stdio.h>
void bubble_sort(int [],int);
void main()
{
int a[30],n,i;
printf("Enter no of elements :");
scanf("%d",&n);
printf("Enter array elements :");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
bubble_sort(a,n);
}
Page 5
+ Bubble Sort Code Cont….
void bubble_sort(int a[],int n)
{ int i,j,k,temp;
printf("Unsorted Data:");
for(k=0;k<n;k++)
printf("%5d",a[k]);
printf("\n");
for(i=0;i< n -1;i++)
{
for(j=0;j< n -i-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
printf("After pass %d : ",i);
for(k=0;k< n;k++)
printf("%5d",a[k]);
printf("\n");
} Page 6
}
+
Bubble Sort Code Cont….
Output :
Enter no of elements :5
Enter array elements :10 4 55 21 6
Unsorted Data: 10 4 55 21 6
After pass 1 : 4 10 21 6 55
After pass 2 : 4 10 6 21 55
After pass 3 : 4 6 10 21 55
After pass 4 : 4 6 10 21 55
Worst case Complexity O(n2)
Page 7
+
Page 8
+
Selection Sort
Given an array of length n,
Search elements 0 through n-1 and select the smallest
Swap it with the element in location 0
Search elements 1 through n-1 and select the smallest
Swap it with the element in location 1
Search elements 2 through n-1 and select the smallest
Swap it with the element in location 2
Search elements 3 through n-1 and select the smallest
Swap it with the element in location 3
Continue in this fashion until there’s nothing left to search.
Page 9
+
Example of selection sort
7 2 8 5 4
2 7 8 5 4
2 4 8 5 7
2 4 5 8 7
2 4 5 7 8
Page 10
+ Selection sort Code
#include <stdio.h>
void main( )
{
int arr[5] = {7, 2, 8, 5, 4} ;
int i, j, temp ;
for ( i = 0 ; i <= 3 ; i++ )
{
for ( j = i + 1 ; j <= 4 ; j++ )
{
if ( arr[i] > arr[j] )
{
temp = arr[i] ;
arr[i] = arr[j] ;
arr[j] = temp ;
}
}
}
printf("Array after sorting:\n");
for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i]); Page 11
}
+
Page 12
+
Page 13
+ Insertion sort Demo
Page 14
+ Insertion sort Demo Cont….
Page 15
+ Insertion sort Demo Cont….
Page 16
+ Insertion sort Code
#include<stdio.h>
void main()
{
int A[20], N, Temp, i, j;
printf("\nENTER THE NUMBER OF TERMS...: ");
scanf("%d", &N);
printf("\nENTER THE ELEMENTS OF THE ARRAY...:");
for(i=0; i<N; i++)
{
scanf("\n%d", &A[i]);
}
Page 17
+ Insertion sort Code Cont….
for(i=1; i<N; i++)
{
Temp = A[i];
j = i-1;
while(Temp<A[j] && j>=0)
{
A[j+1] = A[j];
j = j-1;
}
A[j+1] = Temp;
}
printf("\nTHE ASCENDING ORDER LIST IS...:\n");
for(i=0; i<N; i++)
printf("\n%d", A[i]);
}
Worst case Complexity O(n2)
Page 18
