sorting
sorting
• Sorting means arranging the elements of an array so that
they are arranged either in ascending or descending order.
• For example
• A[] = {21, 34, 11, 9, 1, 0, 22};
• After sorting
• A[] = {0, 1, 9, 11, 21, 22, 34};
Bubble Sort 2
Bubble Sort
• Bubble sort is a very simple method that sorts the array elements by repeatedly
moving the largest element to the highest index position of the array segment.
Bubble Sort 3
Example – Pass 1
49 36 12 97 58 63 8
36 49 12 97 58 63 8
36 12 49 97 58 63 8
36 12 49 97 58 63 8
36 12 49 58 97 63 8
36 12 49 58 63 97 8
36 12 49 58 63 8 97
Bubble Sort 4
Example – Pass 2
36 12 49 58 63 8 97
12 36 49 58 63 8 97
12 36 49 58 63 8 97
12 36 49 58 63 8 97
12 36 49 58 63 8 97
12 36 49 58 8 63 97
Bubble Sort 5
Example – Pass 3
12 36 49 58 8 63 97
12 36 49 58 8 63 97
12 36 49 58 8 63 97
12 36 49 58 8 63 97
12 36 49 8 58 63 97
Bubble Sort 6
Example – Pass 4
12 36 49 8 58 63 97
12 36 49 8 58 63 97
12 36 49 8 58 63 97
12 36 8 49 58 63 97
Bubble Sort 7
Example – Pass 5
12 36 8 49 58 63 97
12 36 8 49 58 63 97
12 8 36 49 58 63 97
Bubble Sort 8
Example – Pass 6
12 8 36 49 58 63 97
8 12 36 49 58 63 97
Bubble Sort 9
relation
• If there is n elements in array n-1 passes required
• In Pass number i, n-i comparisons
Bubble Sort 10
Bubble sorting
#include<stdio.h>
void main()
{
int i,a[10],n,j,t;
printf("Enter number of elements in array : ");
scanf("%d",&n);
printf("Enter elements in array : ");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("Array Before Sorting : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
11
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])
{
t=a[j+1];
a[j+1]=a[j];
a[j]=t;
}
}
}
printf("\nArray After Sorting : ");
for(i=0;i<n;i++)
printf("%d ",a[i]);
} 12
sorting of strings
• Sorting the names of students in the alphabetical order.
Bubble Sort 13
Bubble sorting for strings
#include<stdio.h>
#include<string.h>
void main()
{
int i,n,j;
char a[10][10],t[10];
printf("Enter number of names in array : ");
scanf("%d",&n);
printf("Enter names in array : ");
for(i=0;i<n;i++)
{
scanf("%s",a[i]);
}
printf("Array Before Sorting :");
for(i=0;i<n;i++)
{
printf("%s ",a[i]);
}
14
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
{
if(strcmp(a[j],a[j+1])>0)
{
strcpy(t,a[j+1]);
strcpy(a[j+1],a[j]);
strcpy(a[j],t);
}
}
}
printf("\nArray After Sorting : ");
for(i=0;i<n;i++)
{
printf("%s ",a[i]);
}
}
15
16
Exchange sort
#include<stdio.h>
void main()
{
int a[10], i, j, t,n;
printf("Enter the number of elements : ");
scanf("%d",&n);
printf("Enter elements in array : ");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("Array Before Sorting : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
} 17
}
for(i = 0; i < n -1; i++)
{
for (j=i + 1; j < n; j++)
{
if (a[i] > a[j])
{
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
printf("Sorted array is : ");
for (i = 0; i < n; i++)
{ printf(" %d ",a[i]);
}
}
18