C & Data Structures (Charles River Media Computer Engineering) - page 111

< Day Day Up >

HEAPSORT

Introduction

Heapsort is a sorting technique that sorts a contiguous list of length n with O( n log ₂ ( 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 i ^th 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 i ^th position in the list will also satisfy the heap property.

Program

#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); }

Example

Input

Enter the number of elements in the list, max = 10

Enter the elements

56 1 34 42 90 66 87 12 21 11

Output

The list before sorting is:

The elements of the list are:

56 1 34 42 90 66 87 12 21 11

The list after sorting is:

The elements of the list are:

1 11 12 21 34 42 56 66 87 90

Explanation

In each pass of the while loop in the function adjust(x, i, n) , the position i is doubled , so the number of passes cannot exceed log( n /i). Therefore, the computation time of adjust is O(log n /i).

The function build_initial_heap calls the adjust procedure n/2 for values ranging from n1/2 to 0. Hence the total number of iterations will be:

This turns out to be some constant time n. So the computation time of build_initial_heap is O(n). The heapsort function calls the adjust (x,1, i) ( n − 1) times. So the total number of iterations made in the heapsort will be

which turns out to be approximately n log(n). So the computing time of heapsort is O(n log(n)) + O(n). The only additional space needed by heapsort is the space for one record to carry out the exchange.

< Day Day Up >

SEARCHING TECHNIQUES: LINEAR OR SEQUENTIAL SEARCH

Introduction

There are many applications requiring a search for a particular element. Searching refers to finding out whether a particular element is present in the list. The method that we use for this depends on how the elements of the list are organized. If the list is an unordered list, then we use linear or sequential search, whereas if the list is an ordered list, then we use binary search.

The search proceeds by sequentially comparing the key with elements in the list, and continues until either we find a match or the end of the list is encountered. If we find a match, the search terminates successfully by returning the index of the element in the list which has matched. If the end of the list is encountered without a match, the search terminates unsuccessfully.

Program

#include <stdio.h> #define MAX 10 void lsearch(int list[],int n,int element) { int i, flag = 0; for(i=0;i<n;i++) if( list[i] == element) { printf(" The element whose value is %d is present at position %d in list\n", element,i); flag =1; break; } if( flag == 0) printf("The element whose value is %d is not present in the list\n", element); } 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, element; printf("Enter the number of elements in the list max = 10\n"); scanf("%d",&n); readlist(list,n); printf("\nThe list before sorting is:\n"); printlist(list,n); printf("\nEnter the element to be searched\n"); scanf("%d",&element); lsearch(list,n,element); }

Example

Input

Enter the number of elements in the list, max = 10

Enter the elements

23 1 45 67 90 100 432 15 77 55

Output

The list before sorting is:

The elements of the list are:

23 1 45 67 90 100 432 15 77 55

Enter the element to be searched

The element whose value is 100 is present at position 5 in list

Input

Enter the number of elements in the list max = 10

Enter the elements

23 1 45 67 90 101 23 56 44 22

Output

The list before sorting is:

The elements of the list are:

23 1 45 67 90 101 23 56 44 22

Enter the element to be searched

The element whose value is 100 is not present in the list

Explanation

In the best case, the search procedure terminates after one comparison only, whereas in the worst case, it will do n comparisons.
On average, it will do approximately n /2 comparisons, since the search time is proportional to the number of comparisons required to be performed.
The linear search requires an average time proportional to O( n ) to search one element. Therefore to search n elements, it requires a time proportional to O( n ² ).
We conclude that this searching technique is preferable when the value of n is small. The reason for this is the difference between n and n ² is small for smaller values of n .