Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 2521-2•Understand various methods of sorting.•Use the qsort function to sort.•Binary search•Related Chapter: ABC 8.521-3To sort means to put in place or rank according to kind, class or nature. For example, consider a herd of cows. We can sort the cows by weight, age, amount of milk produced, etc. . The sort can be in ascending or descending order. Note that we could not include a lizard in among the sort if we were sorting with respect to amount of milk produced. That is, the items we want to sort must have the same nature. In C we will use arrays to do our sorting. Since the data-type(kind, class or nature) for each element of the array must be the same we are able to compare any two elements in the array (no lizards in the array of milk producing cows).Why sort?One application of sorting is the need to have a sorted array to use binary search.One method of sorting is called “selection sort”.The algorithm: find the smallest element in the list and swap the first item in the list with the smallest value.For example, suppose you are given the values(below):5 3 7 2 4 ( 2 is the smallest value )step 12 3 7 5 4 ( swap 2 with 5, now 3 is the smallest element)step 22 3 7 5 4 ( 3 is in place don’t swap, now 4 is the smallest element)step 32 3 4 5 7 ( swap 4 with 7, now 5 is the smallest element)step 42 3 4 5 7 ( 5 is in place don’t swap, 7 is in place )Another method of sorting is called “insertion sort”. You use insertion sort when you sort a hand of cards. For example, suppose you are given the five cards (below):5 3 7 2 4 (cards in Right hand)empty (cards in Left hand)step 13 7 2 4 (Right hand)5 (Left hand)step 27 2 4 ( R )3 5 ( L )step 32 4 ( R )3 5 7 ( L )step 44 ( R )2 3 5 7 ( L )step 5empty ( R )2 3 4 5 7 ( L ) ( the cards are now sorted )Insertion sort is faster than selection sort because it is easy to determine where we should add the next card to the left hand since the cards in the left hand are already sorted. In C we could use a version of binary search(Lecture 21-22) to tell us where to put the next card (in the left hand). Binary search is used only on the cards in the left hand since binary search only works on sorted arrays. Again, binary search is fast since it uses the transitive property of a sorted list of numbers.We will not have to write the C code for insertion sort, the built-in C function “qsort” (ABC p. 372 - implements a sorting algorithm that also uses the transitive property.See the example using qsort starting on the next slide.21-71. Problem DefinitionWrite a program that sorts the values in an array in ascending order. Use the built-in function ‘qsort’ to do the work of sorting.2. Refine, Generalize, Decompose the problem definition(i.e., identify sub-problems, I/O, etc.)Input = Array of integers.Output= Sorted array of integers (ascending order) is printed.#include <stdio.h> #include <stdlib.h> int compare(int *ptr1, int *ptr2) { if ( *ptr1 > *ptr2) return 1; else if ( *ptr1 < *ptr2) return -1; else return 0; } void main(void) { int numbers[100]; int k,i=0; printf("Enter an array of no more than 100 integers.\n"); while (EOF != scanf("%i",&numbers[i]))++i; qsort(numbers, i, sizeof(numbers[0]), compare); for (k=0; k<i; k++) printf("%i ", numbers[k]); printf("\n"); }21-9Execution:unixprompt>./a.outEnter an array of no more than 100 integers.3 4 2 1 5 (hit Enter and then Control-d to signal EOF)1 2 3 4 5 (this is the output the program produces)unixprompt>21-10arrayname - is the name of an existing array. This array can have any data-type. It can even be an array of pointers. We will refer to the array’s type as datatype .elts is the number of elements of array. qsort(arrayname,elts,size_of_elts,compare_function)The qsort function is a built-in C function that sorts values in an array. The algorithm behind qsort is called “Quick Sort” . In CS101 we are interested only in how to call this function. (see ABC p. 372-)The general format of the qsort function is:21-11size_of_elts is the size in bytes of each element in the array. Use the built-in operator sizeof that returns an integer value representing the number of bytes a variable or data-type takes up in RAM.Example: sizeof(integer) returns the value 4 on the Lab machines.sizeof(numbers[0]) returns the number of bytes the variable numbers[0] takes up in RAM, which is 4 since numbers is an integer array.compare_function is the name of the user defined function that actually does the comparison.qsort(arrayname,elts,size_of_elts,compare_function)21-12The general format of the header for the user defined compare function is: int compare_function( datatype * ptr1,datatype * ptr2)qsort will call the compare_function and pass two pointers ptr1 and ptr2 . Both ptr1 and ptr2 “point” to values in the array arrayname (see previous slide). The user must code the function compare_function so that it returns an integer value back to qsort (the function that called compare_function) . qsort will use this integer to determine whether or not to swap the values in the array. To sort in ascending order the return value is:0 if the elements *ptr1 and *ptr2 of the array are equalpositive if *ptr1 > *ptr2 (i.e. swap the array values)negative if *ptr1 < *ptr2 (i.e. don’t swap the array values)21-13Writing the code for compare_function depends on the data-type datatype and whether the data is sorted in ascending order, descending order, ... or by some other rule. Therefore it’s not possible to write one version of compare_function that does all.21-14The datatype in the sorting example is int . Therefore the header for the compare_function has the form:int compare( int * ptr1,int * ptr2)where ptr1 and ptr2 are pointers to values in the array numbers . As an example of how qsort works with compare see the pictures of memory in the following slides.21-15ptr1 ptr2 numbers[0] numbers[1] numbers[4]3 4Address 2000 2004 …200420002 15. . .Suppose qsort called the compare function and *ptr1 is “3” and *ptr2 is “4”. The picture above shows this situation. In this example, we want to tell qsort to sort 3 before 4(don’t swap the