Data Structures UNIT - III
Sorting
Sorting: Bubble sort, Insertion Sort, Selection
sort, Heap Sort, Merge Sort, Quick Sort.
Learning Material
Sorting
means arranging the elements of an array so that they are placed in some
relevant order which may be either ascending or descending. That is, if A is an
array, then the elements of A are arranged in a sorted order (ascending order)
in such a way that A[0] < A[1] < A[2] < ...... < A[N].For example,
if we have an array that is declared and initialized as
int
A[] = {21, 34, 11, 9, 1, 0, 22};
Then the sorted
array (ascending order) can be given as:
A[]
= {0, 1, 9, 11, 21, 22, 34;
1.
Internal
Sorting.
2.
External
Sorting.
1. Internal
Sorting: For sorting a set of elements, if we use only primary
memory (Main memory), then that sorting process is known as internal
sorting. i.e. internal sorting deals with data stored in computer memory.
2. External
Sorting: For sorting a set of elements, if we use both primary
memory (Main memory) and secondary memory, then that sorting process is
known as external sorting. i.e. external sorting deals with data stored in
files.
Different types of
sorting techniques.
- Bubble sort
- Insertion sort
- Selection sort
- Merge sort
- Quick sort
1. 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 (in case of arranging elements in
ascending order). In bubble sorting, consecutive adjacent pairs of elements in
the array are compared with each other. If the element at the lower index is
greater than the element at the higher index, the two elements are interchanged
so that the element is placed before the bigger one. This process will continue
till the list of unsorted elements exhausts.
·
In
bubble sort, in each iteration we compare adjacent elements i.e. ith index element will be compared with (i+1)th
index element, if they are not in ascending order, then swap them.
·
After first iteration the biggest element
is moved to the last position.
·
After second iteration the next biggest element
is moved to next last but one position.
·
In bubble sort for sorting n elements, we
require (n-1) passes (or) iterations
Technique: The basic methodology of the
working of bubble sort is given as follows:
a) In Pass 1, A[0] and A[1] are compared, then A[1] is compared with A[2], A[2] is compared with A[3], and so on. Finally, A[N–2] is compared with A[N–1]. Pass 1 involves n–1 comparisons and places the biggest element at the highest index of the array.
b) In Pass 2, A[0] and A[1] are compared, then A[1] is compared with A[2], A[2] is compared with A[3], and so on. Finally, A[N–3] is compared with A[N–2]. Pass 2
involves n–2 comparisons and places the
second biggest element at the second highest index of the array.
c) In Pass 3, A[0] and A[1] are compared, then A[1] is compared with A[2], A[2] is compared with A[3], and so on. Finally, A[N–4] is compared with A[N–3]. Pass 3 involves n–3 comparisons and places the third biggest element at the third highest index of the array.
d) In Pass n–1, A[0] and A[1] are compared so that A[0]< A[1], After this step, all the elements of the array are arranged in ascending order.
Example: To discuss bubble sort in detail, let us consider an array A[] that has the following
elements:
Write a C program to implement Bubble sort.
Source code:-
Bubble sort:-
#include <stdio.h>
int main()
{
int a[10], n, i, d, swap;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
for (i = 0 ; i < n - 1; i++)
{
for (d = 0 ; d < n- i - 1; d++)
{
if (a[d] > a[d+1])
{
swap = a[d];
a[d] = a[d+1];
a[d+1] = swap;
}
}
}
printf("Sorted list in ascending order:\n");
for (i = 0; i < n; i++)
printf("%d\n", a[i]);
return 0;
}
Output:-
Enter number of elements
5
Enter 5 integers
76
12
4
23
9
Sorted list in ascending order:
4
9
12
23
76
int main()
{
int
n, a[10], i, d, t, flag = 0;
printf("Enter
number of elements\n");
scanf("%d", &n);
printf("Enter
%d integers\n", n);
for (i= 0; i < n;
i++)
{
scanf("%d", &a[i]);
}
for (i = 1 ; i <= n
- 1; i++)
{
t = a[i];
for (d = i - 1 ; d
>= 0; d--)
{
if (a[d]
> t)
{
a[d+1]
= a[d];
flag
= 1;
}
else
{
break;
}
}
if (flag==1)
{
a[d+1] = t;
}
}
printf("Sorted
list in ascending order:\n");
for (i = 0; i <= n - 1; i++)
{
printf("%d\n", a[i]);
}
return 0;
}
Output:-
Enter number of elements
6
Enter 6 integers
17
34
51
29
7
32
Sorted list in ascending order:
7
17
29
32
34
51
3. Insertion Sort:
#include<stdio.h>
#include<conio.h>
void selection_sort(int[ ],int);
void main()
{
int n,a[10],i;
clrscr();
printf("\n Enter size of the
array");
scanf("%d",&n);
printf("\n Enter elements of the
array");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
selection_sort(a,n);
printf("\n After sorting the
elements of the array are");
for(i=0;i<n;i++)
printf("%d
\t",a[i]);
getch();
}
void selection_sort(int a[],int n)
{
int i,j,temp,min;
for(i=0;i<n;i++)
{
min=i;
for(j=i+1;j<n;j++)
{
if(a[j]<a[min])
min=j;
}
temp=a[i];
a[i]=a[min];
a[min]=temp;
}
}
Merge Sort:
#include<stdio.h>
#include<conio.h>
void merge_sort(int,int);
void merge(int,int,int);
int a[10];
void main()
{
int n,i;
clrscr();
printf("\n Enter
size of the array");
scanf("%d",&n);
printf("\n Enter
elements of the array");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
merge_sort(1,n);
printf("\n After
sorting the elements of the array are");
for(i=1;i<=n;i++)
printf("%d
\t",a[i]);
getch();
}
void merge_sort(int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(low,mid);
merge_sort(mid+1,high);
merge(low,mid,high);
}
}
void merge(int low,int mid,int high)
{
int i,j,k,b[20],r;
i=low;
j=mid+1;
k=low;
while((i<=mid)&&(j<=high))
{
if(a[i]<a[j])
{
b[k]=a[i];
i++;
}
else
{
b[k]=a[j];
j++;
}
k++;
}
if(i<=mid)
{
for(r=i;r<=mid;r++)
{
b[k]=a[r];
k++;
}
}
else
{
for(r=j;r<=high;r++)
{
b[k]=a[r];
k++;
}
}
for(k=low;k<=high;k++)
a[k]=b[k];
}
Output:-
Enter size of the array5
Enter elements of the array1
65
20
12
8
After sorting the elements of the array are1 8 12 20 65
Quick Sort:
#include<stdio.h>
void quicksort(int
number[25],int first,int last)
{
int i, j, pivot, temp;
if(first<last)
{
pivot=first;
i=first;
j=last;
while(i<j)
{
while(number[i]<=number[pivot]&&i<last)
{
i++;
}
while(number[j]>number[pivot])
{
j--;
}
if(i<j)
{
temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}
temp=number[pivot];
number[pivot]=number[j];
number[j]=temp;
quicksort(number,first,j-1);
quicksort(number,j+1,last);
}
}
int main()
{
int i, count, number[25];
printf("How many elements are u going to enter?: ");
scanf("%d",&count);
printf("Enter %d elements: ", count);
for(i=0;i<count;i++)
{
scanf("%d",&number[i]);
}
quicksort(number,0,count-1);
printf("Order of Sorted elements: ");
for(i=0;i<count;i++)
{
printf(" %d",number[i]);
}
return 0;
}
Output:-
How many elements are u going to enter?: 5
Enter 5 elements: 5
20
18
51
21
Order of Sorted elements: 5 18 20
21 51
Bucket Sort:
#include<stdio.h>
#include<conio.h>
void bucket_sort(int [ ],int);
main()
{
int
n,a[20],i;
clrscr();
printf("\nEnter
size of the array\n");
scanf("%d",&n);
printf("\nEnter
elements of the array\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
bucket_sort(a,n);
printf("\nAfter
sorting th elements are\n");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
getch();
}
void bucket_sort(int a[],int n)
{
int
noeb[10],steps,big,nod=0,div=1,bucket[10][10],i,j,k,loc;
big=a[0];
for(i=1;i<n;i++)
{
if(a[i]>big)
big=a[i];
}
while(big>0)
{
nod++; /*nod->number of digits of biggest
number*/
big=big/10;
}
for(steps=1;steps<=nod;steps++)
{
k=0;
for(j=0;j<10;j++)
noeb[j]=0; /*Initialize no.
Of elements in each bucket with 0’s */
for(i=0;i<n;i++)
{
loc=(a[i]/div)%10;
/*Find the location of each element */
bucket[loc][noeb[loc]++]=a[i]; /*place the
element in appropriate
Bucket based on location */
}
for(j=0;j<10;j++)
{
for(i=0;i<noeb[j];i++) /*Combine all
the bucket elements into a array*/
a[k++]=bucket[j][i];
}
div=div*10;
}
}
Heap Sort:
#include<stdio.h>
void
heap_sort(int[],int);
void
max_heap(int[],int,int);
main()
{
int a[10],n,i;
printf("enter size of the
array:");
scanf("%d",&n);
printf("enter elements of the
array:");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
heap_sort(a,n);
printf("\n after sorting
elements of array are:\n");
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
}
void
heap_sort(int a[],int n)
{
int i,t;
for(i=n/2;i>0;i--)
{
max_heap(a,i,n);
}
for(i=n-1;i>0;i--)
{
t=a[0];
a[0]=a[i];
a[i]=t;
max_heap(a,0,i);
}
}
void
max_heap(int a[],int i,int n)
{
int child,t;
while(2*i+1<n)
{
child=2*i+1;
if(a[child+1]>a[child]&&child<n-1)
{
child=child+1;
}
if(a[child]>a[i])
{
t=a[child];
a[child]=a[i];
a[i]=t;
}
i=child;
}
}
Output: -
enter
size of the array:10
enter
elements of the array:16
4
10
14
7
9
3
2
8
1
after sorting elements of array are:
1 2
3 4 7
8 9 10
14 16
Comments
Post a Comment