SORTING:
Sorting means
arranging a set of data either in ascending (or) descending order
Sorting methods are
divided into two categories.
(1) Internal
sorting
(2) External
sorting
(1) Internal sorting:
Internal
sorting means arranging the number with in the array only which is in computer
primary memory.
If all the
data that is to be stored can be accommodated at a time in memory then internal
sorting methods are used.
(2) External sorting:
External
sorting means sorting of numbers from the external file by reading it from
secondary memory
When the
data to be stored is so large that some of the data is present in memory and
some is kept is auxiliary memory, at that time external sorting methods are
used.
Bubble sort:
Bubble sort
technique is the simplest and oldest sorting technique.
This method takes
two elements at a time. It compares these two elements. If the first element is
less than the second element, they are left undisturbed. If the first element
is greater than the second element, then they are swapped. This procedure
continues with the next two elements, goes and ends when all the elements are
sorted.
Consider the list
74, 39, 35, 97, 84
Pass 1: (first
element is compared with all other elements)
Note first element
way change during the process.
(1) Compare 74 and
39. Since 74>39, they are swapped
The array is,
39, 74, 35, 97, 84
(2) Compare 39 and
35. Since 39>35, they are swapped
The array is,
35, 39, 74, 97, 84
(3)Compare 35 and
97. Since 35<97, they are undisturbed
(4) Compare 35 and
84. Since 35<84, they are undisturbed.
At the end of pass
(1), the first element will be in the correct place.
The second pass
begins with the second element and is compared with all other elements. Note
that the number of comparisons will be reduced by one since the first element
is not compared any more
Pass 2: (second
element is compared)
(1) Compare 39 and 74. Since 39<74,
they are undisturbed.
(2) Compare 39 and
97. Since 39<97, they are undisturbed.
(3) Compare 39 and
84. Since 39<84, they are undisturbed.
This pass did not
bring any change in the array elements.
Pass 3: (third
element is compared)
(1) Compare 74 and
97. Since 74<97, they are undisturbed.
(2) Compare 74 and
84. Since 74<84, they are undisturbed.
This pass also did not bring any change in the array
elements
Pass 4: (fourth
element is compared)
(1) compare 97 and
84. since 97>84, they are swapped. The array is now,
35, 39, 74, 84, 97
The sorting is end
here. Note that last number is not compared with any more numbers.
Program to perform bubble sort:
#include<stdio.h>
#include<conio.h>
#define MXSIZE 50
void bsort(int
arr[],int maxsize);
int arr[n],n;
void main()
{
int i;
printf("Enter how many
elements to sort");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter
element");
scanf("%d",&arr[i]);
}
printf("Array before
sorting");
for(i=0;i<n;i++)
{
printf("%d",arr[i]);
printf("\n");
}
bsort(arr,n);
printf("Array after
sorting");
for(i=0;i<n;i++)
{
printf("%d",arr[i]);
printf("\n");
}
}
void bsort(int
arr[],int n)
{
int i,j,temp;
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(arr[i]>arr[j])
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
}
Efficiency of
bubble sort:
In the bubble sort,
the first pass requires (n-1) comparisons to fix the correct position of the
first element. The second pass requires
(n-2), kth pass requires (n-k) and the last pass requires only one
comparison.
Therefore, the
total number of comparisons at the end of the algorithm
f(n)=
(n-1)+(n-2)+(n-3)+(n-4)+----------+(n-k)+3+2+1
f(n)= n(n-1)/2
f(n)= 0(n2)
Hence the order of bubble sort algorithm
is 0(n2)
Selection Sort:
It is also called
as push-down sorting. In the selection sort as the name suggests, the first
element of the list as selected and a pass through the array is made to locate
the minimum value. Once it is found them first element and minimum element are
swapped. This procedure is repeated till
the entire array is sorted.
Consider the
example, 74, 39, 35, 32, 97, and 84
Pass 1: Select 74
and search for smallest in remaining i.e., 32 is smallest. So, 74 and 32 are
swapped. Array is 32, 39, 35, 74, 97,84
Pass 2: Select 39
and search for smallest in remaining i.e., 35 is smallest. So, 39 and 35 are
swapped. Array is 32, 35, 39, 74, 97,84.
Pass 3: Select 39
and search for smallest. Since no element found, the array is left undisturbed.
Pass 4: Select 74
and search for smallest number. Since no elements found, the array is left
undisturbed.
Pass 5: Select 97
and search for smallest in remaining. i.e., 84 is smallest so, 97 and 84 are
swapped. Array is 32, 35, 39, 74, 84, 94.
Therefore
the sorting ends here.
Example program:
#include<stdio.h>
#include<conio.h>
define MAXSIZE 50
void ssort(int
arr[],int MAXSIZE);
int arr[n],n;
void main()
{
int i;
printf("Enter how many
elements to send");
scanf("%d",&n);
for(i=o;i<n;i++)
{
printf("Enter
element");
scanf("%d",&arr[i]);
}
printf("Array before
sorting");
for(i=0;i<n;i++)
{
printf("%d",arr[i]);
printf(\n);
}
ssort(arr,n);
printf("Array after
sorting");
for(i=0;i<n;i++)
{
printf("%d",arr[i]);
printf("\n");
}
}
void ssort(int
arr[],itn n)
{
int i,jk;
int min,temp;
for(i=0;i<n-1;i++)
{
min=i;
for(j=i+1;j<n;j++)
{
if(arr[j]<arr[min])
min=j;
}
temp=arr[i];
arr[i]=arr[min];
arr[min]=temp;
}
}
Efficiency of
selection sort:
We can early understand from the
algorithm that the first pass of the program does (n-1) comparisons. The next pass does (n-2) comparisons and so
on. Thus the total number of comparisons
at the end of sort would be
(n-1)+(n-2)+---------+2+1= n(n-1)/2
=0(n2)
Not that this efficiency is same as
bubble sort. But selection sort is
faster than bubble sort. The selection
sort takes more time than the bubble sort even in those cases where the records
already in order.
Insertion sort:
An insertion sort
is one that sort a set of values by inserting values
Example program:
Efficiency of Insertion sort:
Quick Sort:
Program:
Efficiency of Quick Sort:
No comments:
Post a Comment