Two very common activities in programs are sorting information on some basis and searching for particular item from a large body of data. The concept of an ordered set of elements is one that has considerable impact on our daily lives. Think of a telephone directory. Normally the names are listed in the directory in alphabetical order. This is known as sorted list. The process of finding a telephone number from the telephone directory is known as searching. It is easier to search a sorted list. Sorting can be defined as rearranging the data into a desired sequence based on some attribute of the data. It is a very tedious process because it can result into a massive reshuffling of the datas.
There are different sorting algorithms. There are several points to keep in mind when deciding on a sorting algorithm for a particular task. For example an algorithm may be very easy to implement but is slow while working on large volume of data.
Bubble Sort:-
This sorting technique is easy to implement but not very efficient. The basic technique of bubble sort is to pass through the values sequentially several times .During each pass each element of the list or array will be compared with its successor (A[i] with A[i+1]) and the values will be interchanged if they are not in proper position [ depending on the order , ascending or descending ].Consider the following values are to be sorted in ascending order :- 25 57 48 37 12 92 86 33 . The following operations are to be performed in the first pass.
Compare A[0] with A[1] -------- No interchanged
-- do -- A[1] with A[2]--------- Intechange
-- do -- A[2] with A[3]--------- Intechange
-- do -- A[3] with A[4]--------- Intechange
-- do -- A[4] with A[5]--------- No intechange
-- do -- A[5] with A[6]--------- Intechange
-- do -- A[6] with A[7]--------- Intechange
So after the first pass the array is in the order :- 25 48 37 12 57 86 33 92
After the first pass we find that the largest number 92 is placed in the last position of the array. After the second pass we will find that the second large number is placed just before 92 and this process will continue. Since each iteration will place a new value in its proper position, if there is n number of values then the number of iteration or number of passes will be n-1 times. So the position of the array after each pass will be as follows:-
Original: - 25 57 48 37 12 92 86 33
Pass 1:- 25 48 37 12 57 86 33 92
Pass 2:- 25 37 12 48 57 33 86 92
Pass 3:- 25 12 37 48 33 57 86 92
Pass 4:- 12 25 37 33 48 57 86 92
Pass 5:- 12 25 33 37 48 57 86 92
Pass 6:- 12 25 33 37 48 57 86 92
Pass 7:- 12 25 33 37 48 57 86 92
From the above chart it is clear that the values were positioned properly in the 5th iteration , still Pass 6 and Pass 7 took place without any effect.Such iterations can be stoped by determining whether any interchange of values took place in a given iteration.
Pseudocode algorithm of a bubble sort an array in descending order is as follows :-
N represents the number of elements in the array LIST.I and J are two integer type variables with initial value on I is 0.TEMP is another integer type variable.
Repeat through the following steps while(I< N)
Set J=0
Repeat through the following steps while(J< N-1)
If (LIST[J] > LIST[J+1])
Set TEMP=LIST[J]
Set LIST[J]=LIST[J+1]
Set LIST[J+1]=TEMP
[end of if block]
Set J=J+1
[end of inner loop]
Set I=I+1
[end of outer loop]
Exit
From the above algorithm it is clear that there are N-1 passes and on each pass there are N-1 comparisions.So the total number of comparisons is (N-1)*(N-1) =N2-2N+1.So we can say that the time complexity of the above algorithm is O(N2).
If the algorithm were so designed that when there is no exchange of values in a pass, the iterations will be stopped and the values are inserted in the array in complete sorted order then there will be only one pass of N-1 comparisons. So in this best case the complexity will be O(N).
#include < stdio.h>
void sort(int array[], int size)
{
int temp, i, j;
for (i = 0; i < size; i++)
{
for (j = 0; j < size-1; j++)
{
if (array[j] > array[j+1])
{
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
void main()
{
int values[30], i;
clrscr();
printf("\n Unsorted list is as follows\n");
for (i = 0; i < 5; i++)
{
printf("\nEnter any integer value :-");
scanf("%d",&values[i]);
}
sort(values, 5);
printf("\n Sorted list is as follows\n");
for (i = 0; i < 5; i++)
printf("%d ", values[i]);
getch();
}
No comments:
Post a Comment