CHAPTER - 4.pdf

Data Structure Prof. Vijya Tulsani, Assistant Professor IT and Computer Science  CHAPTER-4 Sorting , Searching and File Structure What is Sorting? Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particul...

Data Structure Prof. Vijya Tulsani, Assistant Professor IT and Computer Science  CHAPTER-4 Sorting , Searching and File Structure What is Sorting? Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. Sorting is nothing but storage of data in sorted order, it can be in ascending or descending order. Sorting arranges data in a sequence which makes searching easier. Complexity of Sorting algorithm The complexity of sorting algorithm calculates the running time of a function in which 'n' number of items are to be sorted. The choice for which sorting method is suitable for a problem depends on several dependency configurations for different problems. The most noteworthy of these considerations are: The length of time spent by the programmer in programming a specific sorting program Amount of machine time necessary for running the program The amount of memory necessary for running the program Types of Sorting Selection Sort Bubble sort Insertion sort Quick Sort Shell Sort Merge Sort etc. Image source : Youtube video Selection Sort In selection sort the list is divided into two sub-lists sorted and unsorted. These two lists are divided by imaginary wall. We find a smallest element from unsorted sub-list and swap it to the beginning. And the wall moves one element ahead, as the sorted list is increases and unsorted list is decreases. Image source : Google Selection Sort Assume that we have a list on n elements. By applying selection sort, the first element is compared with all remaining (n-1) elements. The smallest element is placed at the first location. Again, the second element is compared with remaining (n-1) elements. At the time of comparison, the smaller element is swapped with larger element. Similarly, entire array is checked for smallest element and thenn swapping is done accordingly. Here we need n-1 passes or iterations to completely rearrange the data. Image source : Google Algorithm Steps Pass1: Find the Location LOC of the smallest in the List N elements A,A….A[N], and then interchange A[LOC] and A.Then A is Sorted. Pass 2: Find the Location LOC of the smallest in the List N-1elements A,A….A[N], and then interchange A[LOC] and A. Then A,A is Sorted. Since A left, go to 1. pivot_index = 40 20 10 30 60 50 7 80 100 0 Image source : left right Youtube video Complexity 1. While data[left] data[pivot] --right 3. If left < right swap data[left] and data[right] 4. While right > left, go to 1. pivot_index = 40 20 10 30 60 50 7 80 100 0 Image source : Youtube video left right Complexity 1. While data[left] data[pivot] --right 3. If left < right swap data[left] and data[right] 4. While right > left, go to 1. pivot_index = 40 20 10 30 7 50 60 80 100 0 Image source : Youtube video left right Complexity 1. While data[left] data[pivot] --right 3. If left < right swap data[left] and data[right] 4. While right > left, go to 1. pivot_index = 40 20 10 30 7 50 60 80 100 0 Image source : left right Youtube video Complexity 1. While data[left] data[pivot] --right 3. If left < right swap data[left] and data[right] 4. While right > left, go to 1. pivot_index = 40 20 10 30 7 50 60 80 100 0 Image source : Youtube video left right Complexity 1. While data[left] data[pivot] --right 3. If left < right swap data[left] and data[right] 4. While right > left, go to 1. pivot_index = 40 20 10 30 7 50 60 80 100 0 Image source : Youtube video left right Complexity 1. While data[left] data[pivot] --right 3. If left < right swap data[left] and data[right] 4. While right > left, go to 1. pivot_index = 40 20 10 30 7 50 60 80 100 0 Image source : Youtube video left right Complexity 1. While data[left] data[pivot] --right 3. If left < right swap data[left] and data[right] 4. While right > left, go to 1. pivot_index = 40 20 10 30 7 50 60 80 100 0 Image source : left right Youtube video Complexity 1. While data[left] data[pivot] --right 3. If left < right swap data[left] and data[right] 4. While right > left, go to 1. pivot_index = 40 20 10 30 7 50 60 80 100 0 Image source : Youtube video left right Complexity 1. While data[left] data[pivot] --right 3. If left < right swap data[left] and data[right] 4. While right > left, go to 1. pivot_index = 40 20 10 30 7 50 60 80 100 0 Image source : left right Youtube video Complexity 1. While data[left] data[pivot] --right 3. If left < right swap data[left] and data[right] 4. While right > left, go to 1. pivot_index = 40 20 10 30 7 50 60 80 100 0 Image source : left right Youtube video Complexity 1. While data[left] data[pivot] --right 3. If left < right swap data[left] and data[right] 4. While right > left, go to 1. pivot_index = 40 20 10 30 7 50 60 80 100 0 Image source : Youtube video left right Complexity 1. While data[left] data[pivot] --right 3. If left < right swap data[left] and data[right] 4. While right > left, go to 1. pivot_index = 40 20 10 30 7 50 60 80 100 0 Image source : left right Youtube video Complexity 1. While data[left] data[pivot] --right 3. If left < right swap data[left] and data[right] 4. While right > left, go to 1. Swap data[right] and data[pivot_index] pivot_index = 40 20 10 30 7 50 60 80 100 0 Image source : Youtube video left right Complexity 1. While data[left] data[pivot] --right 3. If left < right swap data[left] and data[right] 4. While right > left, go to 1. Swap data[right] and data[pivot_index] pivot_index = 7 20 10 30 40 50 60 80 100 4 Image source : left right Youtube video Complexity 7 20 10 30 40 50 60 80 100 data[pivot] Image source : Youtube video Recursion: Quicksort Sub-arrays 7 20 10 30 40 50 60 80 100 data[pivot] Image source : Youtube video  Quicksort Analysis Assume that keys are random, uniformly distributed. What is best case running time? Recursion: 1. Partition splits array in two sub-arrays of size n/2 2. Quicksort each sub-array Depth of recursion tree? O(log2n) Number of accesses in partition? O(n) Image source : Youtube video Quicksort Analysis Assume that keys are random, uniformly distributed. Best case running time: O(n log2n) Worst case running time: O(n2)!!! Image source : Youtube video Quicksort Analysis Assume that keys are random, uniformly distributed. Best case running time: O(n log2n) Worst case running time: O(n2)!!! What can we do to avoid worst case? Image source : Youtube video Code #include if(i // Do a gapped insertion sort for this gap size. // temp; j -= gap) The first gap elements a[0..gap-1] are already in arr[j] = arr[j - gap]; gapped order // put temp (the original a[i]) in its // keep adding one more element until the correct location entire array is // gap sorted arr[j] = temp; void printArray(int arr[], int for (int i = gap; i < n; i += 1) } { } n) // add a[i] to the elements that have been gap sorted return 0; // { save a[i] in temp and make a hole at position i } for (int i=0; i