What is Sorting in Data Structure?
There are two types of sorting.:-
Internal sorting:- Which deals with the data stored in the computer memory.
External sorting:- Which deals with sorting the data stored in the file.
External sorting is implied where there is huge data, that can not be stored in the memory.
Types of sort
· Merge sort
·
Bubble sort
·
Selection sort
·
Insertion sort
Merge sort
Merge sort is the sorting algorithm that uses the divide, conquer and
combine algorithm technique.
These three concepts are as follows:-
· Divide :- That means partitioning the n element array to be sorted into two arrays of n/2 elements. If an array containing 0 or 1 element, then it is already sorted but if there are no elements in the array then divide by n/2 sub-arrays, each containing about half of the element of the original array.
· Conquer :- that means sorting the two sub-arrays recursively using merge sort.
· Combine :- merging the two sorted subarrays of size n/2 to produce the sorted array of n elements.
The basic steps of a merge sort algorithm are as follows:-
· If the array is of length 0 or 1 then it is already sorted
· Otherwise divide the unsorted array into two sub-arrays off about half of the size..
· Else merge sort algorithm recursively to sort each sub-array.
· Merge the two sub-array to form a single sorted list.
Algorithm for merge sort :-
Step 1: [initialized] set i=beg, j=mid, in=0
Step 2: repeat while (i<=mid) and (j<=end)
If a[i] <a[j]
Temp[in] =a[i]
Increment i++.
Else
Temp [in] =a[j]
Increment j
Set in=in+ 1
[end of the loop]
Step 3: [copy of remaining elements of right sub array in the temp, if any element left now]
Step 4: if i>mid
Repeat while (j<=end)
Set temp [in] =a[j]
Increment in
Increment j
[end of the loop ]
Step 5:- [copy of the remaining element of the left sub array in to temp, if any element left now]
Step 6: else
Repeat while (i<=mid)
Temp [in] =a[j]
Increment in
Increment i
[end of loop]
Step 7: [copy the elements of temp to the array a]
Step 8: set i=0
Repeat while (i<in)
A[i] =temp[i]
[end of the loop]
Step 9:end
Merge sort (a[], beg, end)
Step 1: [initialize] set beg, mid, end, in
Step 2: if (beg<mid)
Set mid=(beg + end)/2
Call_merge sort (a, beg, mid)
Else
Call_merge sort (a, mid-1, end )
Call_merge sort (a, beg, mid, end)
[end of loop]
Step 3: end
The complexity of merge sort:-
The running time of the merge sort in the average case and in the worst case it can be given as O(nlogn), in the worst-case efficiency is given O(n log n). But merge sort needs an additional space of O(n) for the temporary array (temp).
Program of merge sort
#include<conio.h>
#include<stdio.h>
void mergesort(int [],int,int);
void merge(int
[],int,int,int);
void main()
{
int n ,arr[50],i,j;
clrscr();
printf("\nenter
the size of array:-");
scanf("%d",&n);
printf("\nenter
the data in the array");
for(i=0;i<n;i++)
{
printf("enter
the %dth element",i+1);
scanf("%d",&arr[i]);
}
printf("\n display of array");
for(i=0;i<n;i++)
{
printf("\n%d",arr[i]);
}
mergesort(arr,0,n-1);
printf("\nafter merge sort") ;
for(i=0;i<n;i++)
{
printf("%d",arr[i]);
}
getch();
}
void mergesort( int arr[], int beg,
int end)
{
int i,j,temp[100],mid;
if(beg<end)
{
mid=(beg+end)/2;
mergesort(arr,beg,mid);
mergesort(arr,mid+1,end);
merge(arr,beg,mid,end);
}
}
void merge (int arr[],int beg,int mid,int end)
{
int i=beg,j=mid+1,in=beg,temp[100],k;
while((i<=mid)&&(j<=end))
{
if(arr[i]<arr[j])
{
temp[in]=arr[i];
i++;
}
else
{
temp[in]=arr[j];
j++;
}in++;
}
if(i>mid)
{
while(j<=end)
{
temp[in]=arr[j];
j++;
in++;
}
}
else
{
while (i<=mid)
{
temp[in]=arr[i];
i++;
in++;
}
}
for(i=0;i<in;i++)
{
arr[i]=temp[i];
}
}
BUBBLE SORT
In bubble sort, each element is compared
with its adjacent element. If the first element is larger than the second one,
then the positions of the elements are interchanged, otherwise, it is not
changed. Then next element is compared with its adjacent element and the same
process is repeated for all the elements in the array until we get a sorted
array
Let A be a linear array of n
numbers. Sorting of A means rearranging the elements
of A so that they are in
order. Here we are dealing with ascending order. i.e.,
A[1] < A[2] < A[3]
< ...... A[n].
Suppose the list of numbers
A[1], A[2], ………… A[n] is an element of array A.
The bubble sort algorithm
works as follows
Step 1:
Compare A[1] and A[2] and arrange them in the (or desired) ascending order,
that A[1] < A[2] .that is if A[1] is greater than A[2] then interchange the position
of data by
swap = A[1]
;
A[1]
= A[2];
A[2]
= swap.
Then compare A[2] and A[3]
and arrange them so that A[2] < A[3].
Step 2:
Repeat step 1 with one less comparison that is, now stop comparison at A [n – 1]
and
possibly rearrange A[N – 2] and A[N – 1] and so on.
The following figures will depict the various steps (or PASS) involved in the sorting of an array of 5 elements.
The elements of an array A to be sorted are:
42, 33, 23, 74, 44
FIRST PASS
33
swapped 33 33 33
42 23 swapped 23 23
23 42 42 no swapping 42
74 74 74 44 swapped
44 44 44 74
Second pass
23
swapped 23 23
33 33 no swapping 33
42 42 42 no swapping
44 44 44
74 74 74
Third pass
23 23
33 33 no swapping
42 42
44 44
74 74
Fourth pass
23
33
42
44
74
Thus the
sorted array is 23, 33, 42, 44, 74.
ALGORITHM
Let A be a linear array of n numbers. Swap is a temporary
variable for swapping (or interchange) the position of the numbers.
(1)
Input n numbers of an array A
(2)
Initialise i = 0 and repeat through step 4 if (i <
n)
(3)
. Initialize j = 0 and repeat through step 4 if (j
< n – i – 1)
(4)
If (A[j] > A[j + 1])
(a) Swap = A[j]
(b)A[j] = A[j + 1]
(c) A[j + 1] =
Swap
(5)
Display the sorted numbers of array A
(6)
Exit.
//PROGRAM TO IMPLEMENT BUBBLE SORT USING ARRAYS
//CODED AND COMPILED IN TURBO C
#include<stdio.h>
#include<conio.h>
void main()
{
int n,arr[100],i,j,temp=0;
clrscr();
//here first
enter the size of the array
printf("enter the size
of array");
scanf("%d",&n);
// enter the data in
array
for(i=0;i<n;i++)
{
printf("\nenter the %d th data=",i+1);
scanf("%d",&arr[i]);
}
//bubble sorting
can be implemented here
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
{
if(arr[j]>arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
} // after sorting display of the sorted list
printf("\nafter sorting");
for(i=0;i<n;i++)
{
printf("\n %d",arr[i]);
}
getch();
}
SELECTION
SORT
There are a number of applications in which
we are interested in identifying a single element in terms of its rank relative
to an ordering of the entire set. Examples include identifying the minimum and
maximum elements, but we may also be interested in, say, identifying the median
element, that is, the element such that half of the other elements are smaller
and the remaining half are larger. In general, queries that ask for an element
with a given rank are called order statistics.
Defining the Selection Problem
In this section, we discuss the
general order-statistic problem of selecting the kth smallest element from an
unsorted collection of n comparable elements. This is known as the selection
problem. Of course, we can solve this problem by sorting the collection and
then indexing it into the sorted sequence at index k−1. Using the best
comparison-based sorting algorithms, this approach would take O(nlogn) time,
which is obviously overkilled for the cases where k = 1 or k = n (or even k =
2, k = 3, k = n−1, or k = n−5), because we can easily solve the selection
problem for these values of k in O(n) time. Thus, a natural question to ask is
whether we can achieve an O(n) running time for all values of k (including the
interesting case of finding the median, where k =⌊n/2⌋).
Step
1:
Find the smallest element in the array of n numbers A[1], A[2], ...... A[n]. Let LOC is
the location of the smallest number in the array.
Then
interchange A[LOC] and A[1] by swap = A[LOC];
A[LOC] = A[1]; A[1] = Swap.
Step 2:
Find the second smallest number in the sub
list of n – 1 element A [2] A [3] ...... A [n – 1] (the first element is already
sorted). Now we concentrate on the rest of the elements in the array.
Again A
[LOC] is the smallest element in the remaining array and LOC the corresponding
location then interchange A [LOC] and A [2].
Now A [1]
and A [2] is sorted since A [1] less than or equal to A [2].
Step 3:
Repeat the process by reducing one element each from the array
Step n – 1:
Find the n – 1 smallest number in the sub array of 2 elements
(i.e., A(n– 1), A (n)).
Consider A [LOC] is the smallest element and LOC is its corresponding position.
Then
interchange A [LOC] and A(n – 1).
Now the array A [1], A [2], A [3], A
[4],………..A [n] will be a sorted array.
Sort five numbers 42, 33, 23, 74, 44 :
First pass:
A[1]=42 A[1]=23
A[2]=33 LOC=3 A[2] =33 LOC =2
A[3]=23 A[3]=42
A[4]=74 A[4]=74
A[5]=44 A[5]=44
SECOND
PASS:
THIRD PASS:
A[1]=
23
A[1]= 23
A[2]=
33 LOC=2 A[2]=33 LOC=3
A[3]=42
A[3]= 42
A[4]=74
A[4]= 74
A[5]=44
A[5]= 44
FOURTH PASS:
A[1]=23
A[2]=33 LOC=5
A[3]=42
A[4]=44
A[5]=74
ALGORITHM
Let A be a
linear array of n numbers A [1], A [2], A [3], ……… A [k], A [k+1], …….. A [n].
Swap be a temporary variable for swapping (or interchanging) the position of the numbers. Min is the variable to store the smallest number and Loc is the location of the smallest element.
(1)Input n numbers of an array A
(2)Initialize i = 0 and repeat through step5 if (i < n – 1)
(a ) min = a[i]
(b) loc = i
(3)
Initialize j = i + 1 and repeat through step 4 if (j < n – 1)
(4) if
(a[j] < min)
(a) min = a[j]
(b) loc = j
(5) if (loc
! = i)
(a) swap = a[i]
(b) a[i] = a[loc]
(c) a[loc] = swap
(6) Display
“the sorted numbers of array A”
(7) Exit
//PROGRAM TO IMPLEMENT SELECTION SORT
//USING STATIC MEMORY ALLOCATION, THAT IS
USING ARRAYS //CODED AND COMPILED IN TURBO C
#include<conio.h>
#include<stdio.h>
#define
MAX 20
void
main()
{
int arr[MAX], i,j,k,n,temp,smallest;
clrscr();
printf (“\nEnter
the number of elements : ”);
scanf (“%d”, & n);
for (i = 0; i < n; i++)
{
printf (“\nEnter
element %d : ”,i+1);
scanf (“%d”, &arr[i]);
}
printf (“\nUnsorted
list is : \n”);
for (i = 0; i < n; i++)
printf (“%d ”, arr[i]); printf (“\n”);
/*Selection sort*/
for (i =
0; i < n – 1 ; i++) {
/*Find
the smallest element*/
smallest
= i;
for(k = i
+ 1; k < n ; k++)
{
if
(arr[smallest] > arr[k])
smallest
= k ;
}
if ( i !=
smallest )
{
temp =
arr [i];
arr[i] =
arr[smallest];
arr[smallest]
= temp ;
}
printf (“\nAfter Pass %d elements are : ”,i+1);
for (j =
0; j < n; j++)
printf (“%d
”, arr[ j]);
printf (“\n”);
}/*End of
for*/
printf (“\nSorted list is : \n”);
for (i =
0; i < n; i++)
printf (“%d
”, arr[i]);
getch();
}
/*End of
main()*/
INSERTION SORT
Insertion sort algorithm sorts a set of values by inserting values
into an existing sorted file. Compare the second element with the first, if the
first element is greater than the second, place it before the first one. Otherwise, the place is just after the first one. Compare the third value with the second. If the
third value is greater than the second value then place it just after the
second. Otherwise, place the second value to the third place. And compare the third
value with the first value. If the third value is greater than the first value
place the third value to second place, otherwise place the first value to
second place. And place the third value to first place and so on.
Let A be a linear array of n numbers A [1], A [2], A [3], ...... A[n] . The algorithm scans the array A from A [1] to A [n], by
inserting each element A[k], into the proper position of the previously sorted
sub-list. A [1], A [2], A [3] , ...... A [k – 1]
Step 1:
As the single element A [1] by itself is sorted array.
Step 2:
A [2] is inserted either before or after A [1] by comparing it so
that A[1], A[2] is a sorted array.
Step 3:
A [3] is inserted into the
proper place in A [1], A [2], that is A [3] will be compared with A [1] and A
[2] and placed before A [1], between A [1] and A [2], or after A [2] so that A
[1], A [2], A [3] is a sorted array.
Step 4:
A [4] is inserted in to a proper place
in A [1], A [2], A [3] by comparing it; so that A [1], A [2], A [3], A [4] is a
sorted array.
Step 5:
Repeat the process by inserting the element in the proper place in
array
Step n:
A [n] is inserted into its proper place in an array A [1], A [2],
A [3], ...... A [n – 1] so that A [1], A [2], A [3], ...... ,A [n] is a sorted
array.
ALGORITHM
Let A be a linear array of n numbers A [1], A [2], A [3], ......
,A [n]......Swap be a temporary variable to interchange the two values. Pos is
the control variable to hold the position of each pass.
(1)
. Input an array A of n numbers
(2)
Initialize i = 1 and repeat through steps 4 by
incrementing i by one.
(a)
If (i < = n – 1)
(b)
Swap = A [I]
(c)
Pos = i – 1
(3)
Repeat the step 3 if (Swap < A[Pos] and
(Pos >= 0))
(a)
A [Pos+1] = A [Pos]
(b)
Pos = Pos-1
(4)
A [Pos +1] = Swap
(5) EXIT
//CODED AND COMPILED IN TURBO C
#include<conio.h>
#include<stdio.h>
#define MAX 20
void main()
{
int
arr[MAX],i,j,k,n;
clrscr();
printf (“\nEnter
the number of elements : ”);
scanf
(“%d”,&n);
for (i = 0; i
< n; i++)
{
printf (“\nEnter
element %d : ”,i+1);
scanf (“%d”,
&arr[i]);
}
printf
(“\nUnsorted list is :\n”);
for (i = 0; i < n; i++)
printf (“%d ”,
arr[i]);
printf (“\n”);
/*Insertion
sort*/
for(j=1;j <
n;j++)
{
k=arr[j];
/*k is to be inserted at proper place*/
for(i=j–1;i>=0 && k<arr[i];i--)
arr[i+1]=arr[i];
arr[i+1]=k;
printf (“\nPass
%d, Element inserted in proper place: %d\n”,j,k);
for (i = 0; i < n; i++)
printf (“%d ”,
arr[i]);
printf (“\n”); }
printf (“\nSorted list is :\n”);
for (i = 0; i < n; i++)
printf (“%d ”, arr[i]);
getch();
}
/*End of main()*/
Post a Comment