The Complete Codes

Tree Data Structures Tree is a collection of nodes. If the collection is empty the tree is empty otherwise it contains a distinct node called root (r) and zero or more sub-trees whose roots are directly connected to the node r by edges. The root of each tree is called child of r, and r the parent. Any node without a child is called leaf. We can also call the tree as a connected graph without a cycle. So there is a path from one node to any other nodes in the tree. The main concern with this data structure is due to the running time of most of the operation require O(logn). We can represent tree as an array or linked list. Some of the definitions Level h of a full tree has d^(h-1) nodes. The first h levels of a full tree have 1 + d + d^2 + …………………….. d^(h-1) = (d^h -1)/(d-1) Binary Search Trees BST has at most two children for each parent. In BST a key at each vertex must be greater than all the keys held by its left descendents and smaller or equal than all the keys held by its r

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

Selection Sort A selection sort is a sorting techniqlue in which successive elements are selected in order and paced into their proper sorted positions. By starting from the first element and using a nest of for loops, a pass through the array is made to locate the minimum value. Once this is found, it 1s placed in the first position of the array (position 0). Then the remaining elements is made to find the next smallest element, which is placed in the second position (position 1), and so on. Once the next to last element is compared with the last element, all the elements have been sorted into ascending order. The algorithm works as follows: Find the minimum value in the list. Swap it with the value in the first position. Repeat the above steps for the remainder of the list (starting at the second position and advancing each time). Algorithm for Selection Sort This algorithm sorts the array list with n elements Initialization, Set loc=o

Quick Sort It is also called partition exchange sort because it works by partitioning the array to be sorted. Basic Idea: Let x be an array and n be the number of elements in the array. Let us choose an element (called pivot) a from a specific position within the array (for example, a can be chosen as the first element so that a=x[o]). Now suppose that the elements of array x are partitioned in such a way that a is placed into position j of the array and the following conditions hold: Each of the elements in positions j through j-1 is less than or equal to a. Each of the elements in positions j+1 through n-1 is greater than or equal to a. If these two conditions hold for a particular a and j, a is the jth smallest element of array x, so that remains in position j when the array is completely sorted. lf the same process is repeated for sub-arrays x[o] through x[j-1] and x[j+1] through x[n-1] and any sub arrays created by the process in successive iterations,