The Complete Codes

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

C Program To Accept The String That Ends With 011 #include <stdio.h> #include <string.h> int main () {     char str [ 10 ];     int len, i, q = 0 ;     printf ( "Enter the string which only contain 0 and 1 \n " );     scanf ( " %s " , str);     len = strlen (str);     for (i = 0 ; i <= len; i++)     {         if ( str [i] == '0' && q == 0 )             q = 1 ;         else if ( str [i] == '1' && q == 0 )             q = 0 ;         else if ( str [i] == '1' && q == 1 )             q = 2 ;         else if ( str [i] == '0' && q == 1 )             q = 1 ;         else if ( str [i] == '0' && q == 2 )             q = 1 ;         else if ( str [i] == '1' && q == 2 )             q = 3 ;         else if ( str [i] == '1' && q == 3 )             q = 0 ;         else if ( str [i] == '0' && q == 3 )        

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,

C Program For Selection Sort by Generating Random Numbers and Using time.h Function #include <stdio.h> #include <time.h> #include <stdlib.h> void selection_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 ]);     }     selection_sort ( list , n );     printf ( " \n Time taken to complete the selectionsort %u " , clock () / CLOCKS_PER_SEC);     printf ( " \n The sorted list is: \n " );     for ( i = 0 ; i < n ; i ++)         printf ( " %d \t " , list [ i ]);     return 0 ; } void selection_sort ( int list [], int n ) {     int temp , loc , j ;     for ( loc = 0 ; loc < n -