Sorting Insertion sort Selection sort Bubble sortThe efficiency of handling data can be substantially improved if the data are sorted according to some criteria of order. In a telephone directory we are able to locate a phone number, only because the names are alphabetically ordered. Same thing holds true for listing of directories created by us on the computer. It would be very annoying if we don’t follow some order to store book indexes, payrolls, bank accounts, customer records, items inventory records, especially when the number of records is pretty large. • We want to keep information in a sensible order. − alphabetical order − ascending/descending order − order according to names, ids, years, departments etc. • The aim of sorting algorithms is to put unordered information in an ordered form. • There are dozens of sorting algorithms. The more popular ones are listed below: − Selection Sort − Bubble Sort − Insertion Sort − Merge Sort − Quick Sort As always, we want to decide which algorithms are best for a particular situation. The efficiency is decided by the number of comparisons and the number of data movements, using the big-O notation. The order ofmagnitude can vary depending on the initial ordering of data. How much time, does a computer spend on data ordering if the data are already ordered? We often try to compute the data movements, and comparisons for the following three cases: best case ( often, data is already in order), worst case( sometimes, the data is in reverse order), and average case( data in random order). Some sorting methods perform the same operations regardless of the initial ordering of data. Why should we consider both comparisons and data movements? If simple keys are compared, such as integers or characters, then the comparisons are relatively fast and inexpensive. If strings or arrays of numbers are compared, then the cost of comparisons goes up substantially. If on the other hand, the data items moved are large, such as structures, then the movement measure may stand out as the determining factor in efficiency considerations.Insertion Sort The key idea is to pick up a data element and insert it into its proper place in the partial data considered so far. An outline of the algorithm is as follows: Let the n data elements be stored in a array list[ ]. Then, for ( cur = 1; cur < n ; cur++ ) move all elements list [ j ] greater than data [ cur ] by one position; place data [ cur ] in its proper position. Note that the sorting is restricted only to fraction of the array in each iteraion. The list is divided into two parts: sorted and unsorted. Ö In each pass, the first element of the unsorted part is picked up, transferred to the sorted sublist, and inserted at the appropriate place. A list of n elements will take at most n-1 passes to sort the data.Insertion Sort Example Sorted Unsorted 23 78 45 8 32 56 23 78 45 8 32 56 23 45 78 8 32 56 8 23 45 78 32 56 8 23 32 45 78 56 8 23 32 45 56 78 Original ListAfter pass 1After pass 2After pass 3After pass 4After pass 5Insertion Sort Algorithm /* With each pass, first element in unsorted sublist is inserted into sorted sublist. */ void insertionSort(int list[], int n) { int cur, located, temp, j; for (cur = 1; cur <= n ; cur++){ located = 0; temp = list[cur]; for ( j = cur - 1; j >= 0 && !located;) if(temp < list[ j ]){ list[j + 1]= list[ j ]; j--; } else located = 1; list[j + 1] = temp; } return; } An advantage of this method is that it sorts the array only when it is really necessary.If the array is already in order, no moves are performed. However, it overlooks the fact that the elements may already be in their proper positions . When an item is to be inserted, all elements greater than this have to be moved. There may be large number of redundant moves, as an element ( properly located) may be moved , but later brought back to its position. The best case is when the data are already in order. Only one comparison is made for each position, so the comparison complexity is O(n), and the data movement is 2n – 1 , i.e. it is O(n). The worst case is when the data are in reverse order. Each data element is to be moved to new position and for that each of the other elements have to be shifted. This works out to be complexity of O(n2). What happens when the elements are in random order? Does the over complexity is nearer to the best case , or nearer to the worst case? It turns out that both number of comparisons and movements turn out to be closer to the worst case .Selection Sort Selection sort is an attempt to localize the exchanges of array elements by finding a misplaced element first and putting it in its final place. Ö The list is divided into two sublists, sorted and unsorted, which are divided by an imaginary wall. Ö We select the smallest element from the unsorted sublist and swap it with the element at the beginning of the unsorted data. Ö Then the smallest value among the remaining elements is selected and put in the second position and so on. Ö After each selection and swapping, the imaginary wall between the two sublists move one element ahead, increasing the number of sorted elements and decreasing the number of unsorted ones. Ö Each time we move one element from the unsorted sublist to the sorted sublist, we say that we have completed a sort pass. Ö A list of n elements requires n-1 passes to completely rearrange the data.Selection Sort Example Sorted Unsorted 23 78 45 8 32 56 8 78 45 23 32 56 8 23 45 78 32 56 8 23 32 78 45 56 8 23 32 45 78 56 8 23 32 45 56 78 Original ListAfter pass 1After pass 2After pass 3After pass 4After pass 5Selection Sort Algorithm /* Sorts by selecting smallest element in unsorted portion of array and exchanging it with element at the beginning of the unsorted list. */ void selectionSort(int list[], int n) { int cur, j, smallest, tempData; for (cur = 0; cur <= n; cur ++){ smallest = cur; for ( j = cur +1; j <= n ; j++) if(list[ j ] < list[smallest]) smallest = j ; // Smallest selected; swap with current element tempData = list[cur]; list[cur] = list[smallest]; list[smallest] = tempData; } }The outer loop is executed n