| Hashing, Searching & Sorting |
|
| Quick Sort |
|
| In the quick sort method, an array a[1],…..,a[n] is sorted by selecting some value in the array as a key element. We then swap the first element of the list with the key element so that the key will be in the first position. We then determine the key's proper place in the list. The proper place for the key is one in which all elements to the left of the key are smaller than the key, and all elements to the right are larger. |
|
| To obtain the key's proper position, we traverse the list in both directions using the indices i and j, respectively. We initialize i to that index that is one more than the index of the key element. That is, if the list to be sorted has the indices running from m to n, the key element is at index m, hence we initialize i to (m+1). The index i is incremented until we get an element at the ith position that is greater than the key value. Similarly, we initialize j to n and go on decrementing j until we get an element with a value less than the key's value. |
|
| We then check to see whether the values of i and j have crossed each other. If not, we interchange the elements at the key (mth)position with the elements at the jth position. This brings the key element to the jth position, and we find that the elements to its left are less than it, and the elements to its right are greater than it. Therefore we can split the list into two sublists. The first sublist is composed of elements from the mth position to the (j–1)th position, and the second sublist consists of elements from the (j+1)th position to the nth position. We then repeat the same procedure on each of the sublists separately. |
|
|
| Choice of the key |
|
| We can choose any entry in the list as the key. The choice of the first entry is often a poor choice for the key, since if the list has already been sorted, there will be no element less than the first element selected as the key. So, one of the sublists will be empty. So we choose a key near the center of the list in the hope that our choice will partition the list in such a manner that about half of the elements will end up on one side of the key, and half will end up on the other. |
|
| Therefore the function getkeyposition is |
int getkeyposition(int i,j)
{
return(( i+j )/ 2);
} |
|
| The choice of the key near the center is also arbitrary, so it is not necessary to always divide the list exactly in half. It may also happen that one sublist is much larger than the other. So some other method of selecting a key should be used. A good way to choose a key is to use a random number generator to choose the position of the next key in each activation of quick sort. |
|
|
| Therefore, the function getkeyposition is: |
int getkeyposition(int i,j)
{
return(random number in the range of i to j);
} |
|
| Example: Program |
|
#include <stdio.h>
#define MAX 10
void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
int getkeyposition(int i,int j )
{
return((i+j) /2);
}
void qsort(int list[],int m,int n)
{
int key,i,j,k;
if( m < n)
{
k = getkeyposition(m,n);
swap(&list[m],&list[k]);
key = list[m];
i = m+1;
j = n;
while(i <= j)
{
while((i <= n) && (list[i] <= key))
i++;
while((j >= m) && (list[j] > key))
j-;
if( i < j)
swap(&list[i],&list[j]);
}
swap(&list[m],&list[j]);
qsort(list[],m,j-l);
qsort(list[],j+1,n);
}
}
void readlist(int list[],int n)
{
int i;
printf("Enter the elements\n");
for(i=0;i<n;i++)
scanf("%d",&list[i]);
}
void printlist(int list[],int n)
{
int i;
printf("The elements of the list are: \n");
for(i=0;i<n;i++)
printf("%d\t",list[i]);
}
void main()
{
int list[MAX], n;
printf("Enter the number of elements in the list max = 10\n");
scanf("%d",&n);
readlist(list,n);
printf("The list before sorting is:\n");
printlist(list,n);
qsort(list,0,n-1);
printf("\nThe list after sorting is:\n");
printlist(list,n);
}
|
|
|
| Output: |
| Try it yourself. |
|
|
|
|
| Hashing, Searching & Sorting |
|
| Merge Sort |
|
| Merge sort or mergesort is a O(n log n) sorting algorithm. It is easy to implement merge sort such that it is stable, meaning. |
|
| This is another sorting technique having the same average-case and worst-case time complexities, but requiring an additional list of size n. The technique that we use is the merging of the two sorted lists of size m and n to form a single sorted list of size (m + n). Given a list of size n to be sorted, instead of viewing it to be one single list of size n, we start by viewing it to be n lists each of size 1, and merge the first list with the second list to form a single sorted list of size 2. |
|
| We then check to see whether the values of i and j have crossed each other. If not, we Similarly, we merge the third and the fourth lists to form a second single sorted list of size 2, and so on. This completes one pass. We then consider the first sorted list of size 2 and the second sorted list of size 2, and merge them to form a single sorted list of size 4. Similarly, we merge the third and the fourth sorted lists, each of size 2, to form the second single sorted list of size 4, and so on. This completes the second pass. |
|
| In the third pass, we merge these adjacent sorted lists, each of size 4, to form sorted lists of size 8. We continue this process until we finally obtain a single sorted list of size n as shown next. |
|
|
|
|
|
|
|
| Hashing, Searching & Sorting |
|
| Heap Sort |
|
| Heapsort is a comparison-based sorting algorithm, and is part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantage of a worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort. |
|
| Heapsort is a sorting technique that sorts a contiguous list of length n with O(n log2 (n)) comparisons and movement of entries, even in the worst case. Hence it achieves the worst-case bounds better than those of quick sort, and for the contiguous list, it is better than merge sort, since it needs only a small and constant amount of space apart from the list being sorted. |
|
| Heapsort proceeds in two phases. First, all the entries in the list are arranged to satisfy the heap property, and then the top of the heap is removed and another entry is promoted to take its place repeatedly. Therefore, we need a function that builds an initial heap to arrange all the entries in the list to satisfy the heap property. The function that builds an initial heap uses a function that adjusts the ith entry in the list, whose entries at 2i and 2i + 1 positions already satisfy the heap property in such a manner that the entry at the ith position in the list will also satisfy the heap property. |
|
| Example: |
|
#include <stdio.h>
#define MAX 10
void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
void adjust( int list[],int i, int n)
{
int j,k,flag;
k = list[i];
flag = 1;
j = 2 * i;
while(j <= n && flag)
{
if(j < n && list[j] < list[j+1])
j++;
if( k >= list[j])
flag =0;
else
{
list[j/2] = list[j];
j = j *2;
}
}
list [j/2] = k;
}
void build_initial_heap( int list[], int n)
{
int i;
for(i=(n/2);i>=0;i-)
adjust(list,i,n-1);
}
void heapsort(int list[],int n)
{
int i;
build_initial_heap(list,n);
for(i=(n-2); i>=0;i-)
{
swap(&list[0],&list[i+1]);
adjust(list,0,i);
}
}
void readlist(int list[],int n)
{
int i;
printf("Enter the elements\n");
for(i=0;i<n;i++)
scanf("%d",&list[i]);
}
void printlist(int list[],int n)
{
int i;
printf("The elements of the list are: \n");
for(i=0;i<n;i++)
printf("%d\t",list[i]);
}
void main()
{
int list[MAX], n;
printf("Enter the number of elements in the list max = 10\n");
scanf("%d",&n);
readlist(list,n);
printf("The list before sorting is:\n");
printlist(list,n);
heapsort(list,n);
printf("The list after sorting is:\n");
printlist(list,n);
}
|
|
| Output: |
| Try it yourself. |
|
|
|
|
|
|
|
|
0 comments: