The Complete Codes

Heap Sort   A heap is a nearly complete binary tree with the following two properties: Structural property: all levels are full, except possibly the last one, which is filled from left to right Order (heap) property: for any node x, Parent(x) ≥ x Array Representation of Heaps A heap can be stored as an array A. Root of tree is A[1] Left child of A[i] = A[2i] Right child of A[i] = A[2i + 1] Parent of A[i] = A[ i/2 ] Heapsize[A] ≤ length[A] The elements in the subarray A[( ⌊ n/2 ⌋ +1) .. n] are leaves Max-heaps (largest element at root), have the max-heap property:   for all nodes i, excluding the root:     A[PARENT(i)] ≥ A[i] Min-heaps (smallest element at root), have the min-heap property: for all nodes i, excluding the root:   A[PARENT(i)] ≤ A[i] Adding/Deleting Nodes New nodes are always inserted at the bottom level (left to right) and nodes are removed from the bottom level (right to left). Operations on Heaps Maintai

Heap A heap is a complete tree with an ordering-relation R holding between each node and its descendant. Note that the complete tree here means tree can miss only rightmost part of the bottom level. R can be smaller-than, bigger-than. E.g. Heap with degree 2 and R is “bigger than”. Heap Sort  Build a heap from the given set (O(n)) time, then repeatedly remove the elements from the heap (O(n log n)). Implementation Heaps are implemented by using arrays. Insertion and deletion of an element takes O(log n) time. More on this later Heap Sort Pseudo Code Heapsort ( A ) {     BuildHeap ( A )     for i <- length (A) downto 2 {       exchange A [ 1 ] <-> A [i]       heapsize <- heapsize - 1       Heapify (A, 1 ) } BuildHeap (A)    {    heapsize <- length (A)     for i <- floor ( length/ 2 ) downto 1       Heapify (A, i)    }     Heapify (A, i)    {        le < - left (i)                    ri < - right (i)                             if (le

C Program For Bubble Sort by Generating Random Numbers and Using time.h Function #include <stdio.h> #include <time.h> #include <stdlib.h> void bubble_sort ( int [], int ); int main () {     int list [ 100 ], n , i ;     time_t t ;     printf ( "Enter the max number \n " );     scanf ( " %d " , & n );     srand (( unsigned ) time (& t ));     for ( i = 0 ; i < n ; i ++)     {         list [ i ] = rand () % 100 ;     }     for ( i = 0 ; i < n ; i ++)     {         printf ( " %d \t " , list [ i ]);     }     bubble_sort ( list , n );     printf ( " \n\n Time taken to complete the bubblesort %u \n " , clock () / CLOCKS_PER_SEC);     printf ( " \n The sorted list is:" );     for ( i = 0 ; i < n ; i ++)         printf ( " %d \t " , list [ i ]);     return 0 ; } void bubble_sort ( int list [], int n ) {     int temp , i , j ;     for ( i = 0 ; i < n ; i ++)     {    

Bubble Sort Bubble sort is a very simple sorting technique. However, this sorting algorithm is not efficient in comparison to other sorting algorithms. The basic idea underlying the bubble sort is to pass through the file sequentially several times. Each pass consists of comparing each element in the file with its successor (x[i] with x[i+1]) and interchanging the two elements if they are not in proper order. Example: Consider the following file, 25          57          48          37          12          92          86          33 In first pass, following comparisons are made: x[o] with x[1] (25 with 57) No interchange x[1] with x[2] (57 with 48) Interchange x[2] with x[3] (57 with 37) Interchange x[3] with x[4] (57 with 12) Interchange x[4] with x[5] (57 with 92) No interchange x[5] with x[6] (92 with 86) Interchange x[6] with x[7] (92 with 33) Interchange Thus, after the first pass, the file is on the order: 25          48          37          

Insertion Sort An insertion sort is one that sorts a set of values by inserting values into an existing sorted file. Suppose that Iist[] is a list of n elements in memory. The insertion sort technique scans the list Iist[] from Iist[1] to list[n-1], inserting each element list[ k] into its proper position in the previously sorted sublist list[o], list[1], ..., list[n-1]. Illustration: Let list[] be an array of 7 elements: 25, 15, 30, 9, 99, 20, 26. Initial scenario, Step 1: list[1] Step 2:   list[2]>list[1] , so position of elements remain same. Step 3:   list[3] is less than list[2.],list [1] and list[o], thus list[3] is inserted at list[o] position and others are shifted by one position. Step 4:  list[4]>list[3] , so position of elements remain same. Step 5:   list[5] is less than list[4], list[3], and list[2], so list[5] is inserted at the position of list[2] and others are shifted by one position. Step 6:   list

Merge Sort Merging is the process of combining two or more sorted files into a third sorted file. Procedure: In merge sort, we divide the file into n subfiles of size 1 and then merge adjacent pair of files. We then have n/2 files of size 2. We repeat this process until there is only one file remaining of size n. Efficiency of Merge Sort Let us assume that the file size n is a power of 2, say n=2 m . Thus m=log 2 n. It is therefore obvious that there are no more than m or log 2 n passes in merge sort (since each pass divides the file into two parts), with each pass involving at most n comparisons. Thus, total number of comparisons in merge sort is at most = n*m = n*log 2 n. Hence the time complexity of merge sort = O (n Iog n). Average case complexity = Worst case complexity = Best case complexity = O(n log n). C Program For Merge Sort #include <stdio.h> void mergesort ( int a [], int i , int j ); void merge ( int a [], int i1 , int j1 , int