Sorting
Sorting is the process of arranging the data in some logical order.This order may be ascending or descending in case of numeric values or dictionary order in case of alpha numeric values.
There are two type of sorting:-
- Internal Sorting
- External Sorting
BUBBLE SORT :-
Bubble sort is very simple and easy to implement sorting technique.Untile unless explicitly stated sorting means ascending order.
Lets take an example , we have a list of number stored in an array.
BUBBLE_SORT(A,N):A is array of values and N is the number of elements
1. Repeat for round = 1,2,3,.....N-1
2. Repeat for i=0,1,2,.....N-1 round
3. If A[i]>A[i+1] them swap A[i] and A[i+1]
4. Return
PROGRAM:-
#include <stdio.h>
int main()
{
int array[100], n, c, d, swap;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
for (c = 0 ; c < ( n - 1 ); c++)
{
for (d = 0 ; d < n - c - 1; d++)
{
if (array[d] > array[d+1]) /* For decreasing order use < */
{
swap = array[d];
array[d] = array[d+1];
array[d+1] = swap;
}
}
}
printf("Sorted list in ascending order:\n");
for ( c = 0 ; c < n ; c++ )
printf("%d\n", array[c]);
return 0;
}
SELECTION SORT:-
Select the smallest value in the list,swap smallest value with the first value of the list.Again select the smallest value in the list (exclude first value) swap this value with the second element of the list.keep doing n-1 times to place all n values in the sorted order.
In Selection Sort we will use a procedure MIN (A,K,N),A is Array , N is number of elements and K is index to begin with.
PROCEDURE MIN:-
Procedure MIN (A,K,N): An array A is in memory.This procedure finds the location LOC of the smallest element among A[K] , A[K+1],.........A[N-1].
1. [Initializes Pointers]
Set MIN=A[K] and LOC = K
2.Repeat for j=K+1 , K+2,......N-1:
if MIN>A[j] , then : Set MIN = A[j] and LOC = j.
[End of Step 1 loop]
3. Return LOC.
ALGORITHM:-
Algorithm SELECTION (A , N): This algorithm sorts the array A with N elements.
1.[loop]
Repeat Steps 2 and 3 for K=0,1,2,.......N-2:
2. Call LOC =MIN(A , K , N)
3. [Interchange A[K] and A[LOC].]
Set TEMP = A[K] , A[K]=A[LOC] and
A[LOC]=TEMP.
[End of step 1 loop]
4. Exit.
Example:-
PROGRAM:-
#include <stdio.h>
int main()
{
int array[100], n, c, d, position, swap;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for ( c = 0 ; c < n ; c++ )
scanf("%d", &array[c]);
for ( c = 0 ; c < ( n - 1 ) ; c++ )
{
position = c;
for ( d = c + 1 ; d < n ; d++ )
{
if ( array[position] > array[d] )
position = d;
}
if ( position != c )
{
swap = array[c];
array[c] = array[position];
array[position] = swap;
}
}
printf("Sorted list in ascending order:\n");
for ( c = 0 ; c < n ; c++ )
printf("%d\n", array[c]);
return 0;
}
Complexity :-
1.Best Case = o(n2)
2.Average Case = o(n2)
3.Worst Case = o(n2)
INSERTION SORT:-
A sublist (or sorted Array ) is maintained which is always sorted.It is not suitable for large data sets and Average and Worst case complexity = o(n2).
(n-1)pass are required to sort (n) elements.In each pass , we insert current element at appropriate place so that the elements in current range are in order.
ALGORITHM :-
int i , key , j;
for (i=1;i<n;i++)
{
key = arr[i];
j = i-1;
while(j> = 0&2 arr[j]>key)
{
arr[J+1] = arr[j];
j = j-1;
}
arr[j+1]=key;
}
}
Example:-
PROGRAM:-
#include <stdio.h>
int main()
{
int n, array[1000], c, d, t;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (c = 0; c < n; c++) {
scanf("%d", &array[c]);
}
for (c = 1 ; c <= n - 1; c++) {
d = c;
while ( d > 0 && array[d] < array[d-1]) {
t = array[d];
array[d] = array[d-1];
array[d-1] = t;
d--;
}
}
printf("Sorted list in ascending order:\n");
for (c = 0; c <= n - 1; c++) {
printf("%d\n", array[c]);
}
return 0;
}
QUICK SORT:-
Quick sort is based on partitioning of array of data into smaller arrays. It uses the concept of divide and conquer and finds an element called "pivot" (Point of division of array)
Pivot
- Left half
- Right half
The efficient for large sized data sets.
Average and worst case complexity = o(n log n)
Recursive Steps :-
i) Find Pivot that divides the array in two halves.
ii) Quick sort left half
iii) Quick sort right half
ALGORITHM:- This algorithm sorts an array A with N elements
1. Top = -1
2. if N>0 , then Top = Top + 1 , LOWER[Top] = 0 , UPPER[Top] = N-1
3. Repeat step 4 to 7 while Top not equal -1
4. POP sublist from stack set BEG = LOWER[Top] , END=UPPER[Top] , Top =Top-1
5. Call QUICK (A , N , BEG , END , LOC)
6. Push left sublist onto the stack
if (BEG < LOC -1) , then:Top = Top+1
LOWER[Top]=BEG, UPPER[Top] = LOC - 1
7. Push right sublist onto stacks
if(LOC+1<END),then:Top = Top + 1, LOWER[Top] = LOC + 1,
UPPER[Top]=END
8. Exit
Example:-
PROGRAM:-
#include <stdio.h>
void quick_sort(int[],int,int);
int partition(int[],int,int);
int main()
{
int a[50],n,i;
printf("How many elements?");
scanf("%d",&n);
printf("\nEnter array elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
quick_sort(a,0,n-1);
printf("\nArray after sorting:");
for(i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}
void quick_sort(int a[],int l,int u)
{
int j;
if(l<u)
{
j=partition(a,l,u);
quick_sort(a,l,j-1);
quick_sort(a,j+1,u);
}
}
int partition(int a[],int l,int u)
{
int v,i,j,temp;
v=a[l];
i=l;
j=u+1;
do
{
do
i++;
while(a[i]<v&&i<=u);
do
j--;
while(v<a[j]);
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
while(i<j);
while(i<j);
a[l]=a[j];
a[j]=v;
return(j);
}
MERGE SORT:-
It is based on divide and conquer technique.
Worst case time complexity = o(n log n)
It is divides the array into equal halves and then combines them in a
sorted manner.
Use the following for division of array:-
beg=start of array
end =end of array
if(beg<end) then Mid=(beg + end)/2
No comments