Unit 2 Searching and Sorting Technique.pptx

Unit 2 Searching and Sorting Technique.pptx

1. SANJIVANI K. B. P. POLYTECHNIC, KOPARGAON With NBA ACCREDIATED programs , Approved by AICTE, New Delhi, Recognized by Govt. of Maharashtra , Affiliated to Maharashtra State Board of Technical Education, Mumbai, ISO 9001:2015 Certified Institute Department:- Computer Technology Class:- CM3I Name of Subject:- Data Structures Using 'C‘ MSBTE Subject Code:- 22317 Name of Faculty: Prof. Vaibhav A. Parjane

2. Searching and Sorting Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

3. Unit Outcome After going through this unit, the student will be able to : 2a. Explain working of the given search method with an example. 2b. Write an algorithm to search the given key using binary Search method 2c. Write an Algorithm to sort data using a specified sorting method. 2d. Explain the working of given sorting method step­ by-step with an example and small data set. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

4. Introduction: ( Searching) Searching: Searching is a process of finding the location of a particular element in an array is called searching. There are two types of searching: Linear Search: Binary Search: Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

5. Linear Search Linear search or sequential search is a method for finding a particular value in a list that consists of checking every one of its elements One element at a time and in sequence, until the desired one is found . It is simplest search algorithm Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

6. Linear Search Consider an array of 20 elements . Suppose, element 8 is to be search in the array. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

7. Linear Search ( Algorithm) Let us start with an array or list, L which may have the item in question. Step 1: If the list L is empty, then the list has nothing. The list does not have the item in question. Stop here. Step 2: Otherwise , look at all the elements in the list L. Step 3: For each element: If the element equals the item in question, the list contains the item in question. Stop here. Otherwise, go onto next element. Step 4: The list does not have the item in question. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

8. Linear Search (Program ) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

9. Linear Search (Program ) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane   Continued……

10. Binary Search Also known as half-interval search algorithm. Finds the position of a specified input value within an array sorted by key value. For binary search, the array should be arranged in ascending or descending order . The binary search is based on the divide-and-conquer approach. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

11. Binary Search In this technique, the element to be searched (say, item) is compared with the middle element of the array. If item is equal to the middle element, then search is successful. If the item is smaller than the middle element, then item is searched in the segment of the array before the middle element. If the item is greater than the middle element, item is searched in the array segment after the middle element. This process will be in iteration until the element is found or the array segment is reduced to a single element that is not equal to item. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

12. Binary Search Consider an sorted array of 11 elements as shown in figure below. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane Suppose we want to search the element 55 from the array of elements.

13. Binary Search For this we will take 3 variables Start, End and Middle Which will keep track of the status of start, end and middle value of the portion of the array, in which we will search the element. The value of the middle will be as: Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane   Initially, and . The key element 55 is to be compared with the Middle value . The value at index 6 is 48 and it is smaller than the target value i.e. (55).  

14. Binary Search If the key is less than the value at Middle then the key element is present in the first half else in other half; In our case, the key is on the right half . Hence, now Start = Middle + 1 = 6 + 1 =7 . Calculate the middle index of the second half Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

15. Binary Search Again, the Middle divides the second half into the two parts as shown in fig below Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane The key element 55 is lesser than the value at Middle which is 72 Hence it is present in the left half i.e., towards the left of 72. Hence now, End = Middle – 1 = 8. Start will remain 7

16. Binary Search At last, the Middle is calculated as Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane Now if key element 55 is compared with the value at middle, then it is found that they are equal. The key element is searched successfully and it is in 7th location  

17. Binary Search (Algorithm) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane Start with the middle element: If the  target  value is equal to the middle element of the array, then return the index of the middle element. If not, then compare the middle element with the target value, If the target value is greater than the number in the middle index, then pick the elements to the right of the middle index, and start with Step 1. If the target value is less than the number in the middle index, then pick the elements to the left of the middle index, and start with Step 1. When a match is found, return the index of the element matched. If no match is found, then return  -1

18. Binary Search (Program ) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

19. Binary Search (Program ) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

20. Introduction ( Sorting) Sorting: Sorting refers to arranging data in a particular format . Sorting means arranging the data in ascending or descending order. There are the several sorting techniques : Bubble Sort Selection Sort Insertion Sort Quick Sort Radix Sort Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

21. Bubble Sort (Algorithm) Following are the steps involved in bubble sort(for sorting a given array in ascending order): Starting with the first element(index = 0), compare the current element with the next element of the array. If the current element is greater than the next element of the array, swap them. If the current element is less than the next element, move to the next element. Repeat Step1. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

22. Bubble Sort Let's consider an array with values {5, 1, 6, 2, 4, 3} Next, we have a pictorial representation of how bubble sort will sort the given array. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

23. 5 1 6 2 4 3 5 1 6 2 4 3 1 5 6 2 4 3 1 5 2 6 4 3 1 5 4 2 6 3 1 5 2 4 3 6 Iteration 1 5 > 1 Interchange 5 < 6 No change 6 > 2 Interchange 6 > 4 Interchange 6 > 3 Interchange Bubble Sort Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

24. 2 1 5 4 3 6 1 2 4 5 3 6 Iteration 2 5 > 2 Interchange 5 > 4 Interchange 5 > 3 Interchange 1 5 2 4 3 6 1 2 4 3 5 6 1 < 5 No change 1 5 2 4 3 6 Bubble Sort Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

25. Iteration 3 2 < 4 No change 4 > 3 Interchange 1 2 4 3 5 6 1 < 2 No change 1 2 4 3 5 6 1 2 4 3 5 6 1 2 3 4 5 6 After Iteration 5 we get all elements sorted 1 2 3 4 5 6 Bubble Sort Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

26. Bubble Sort (Program) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

27. Bubble Sort (Program) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

28. Bubble Sort (Program) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

29. Bubble Sort ( Program using function) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

30. Bubble Sort ( Program using function) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

31. Bubble Sort ( Program using function) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

32. Selection Sort Selection sort is conceptually the most simplest sorting algorithm . This algorithm will first find the smallest element in the array and swap it with the element in the first position. Then it will find the second smallest element and swap it with the element in the second position It will repeat this until the entire array is sorted. It is called selection sort because it repeatedly selects the next-smallest element and swaps it into the right place. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

33. Selection Sort (Algorithm) Following are the steps involved in selection sort(for sorting a given array in ascending order): Step 1 - Set MIN to location 0 Step 2 - Search the minimum element in the list Step 3 - Swap with value at location MIN Step 4 - Increment MIN to point to next element Step 5 - Repeat until list is sorted Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

34. Selection Sort (Algorithm) Following are the steps involved in selection sort(for sorting a given array in ascending order): Set the first element as minimum Compare minimum with the second element. If the second element is smaller than minimum, assign the second element as minimum. Compare minimum with the third element. Again , if the third element is smaller, then assign minimum to the third element otherwise do nothing. The process goes on until the last element . After each iteration, minimum is placed in the front of the unsorted list . For each iteration, indexing starts from the first unsorted element. Step 1 to 3 are repeated until all the elements are placed at their correct positions. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

35. Step 1 21 11 8 13 1 21 11 8 13 1 21 11 8 13 1 21 11 8 13 1 1 11 8 13 21 Swapping         Min value at index 1 Min value at index 2 Min value at index 2 Min value at index 4 First Iteration Selection Sort Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

36. Step 1       Min value at index 2 Min value at index 2 Min value at index 2 Second Iteration 1 11 8 13 21 1 11 8 13 21 1 11 8 13 21 1 8 11 13 21 Swapping Selection Sort Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

37. Step 1     Min value at index 2 Min value at index 2 Already in Place Third Iteration 1 8 11 13 21 1 8 11 13 21 1 8 11 13 21 Selection Sort Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

38. Step 1     Min value at index 3 Fourth Iteration 1 8 11 13 21 1 8 11 13 21 Selection Sort Already in Place Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

39. Selection Sort (Program) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

40. Selection Sort (Program) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

41. Selection Sort (Program) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

42. Insertion Sort This is an in-place comparison-based sorting algorithm. In this, a sub-list is maintained which is always sorted. For example, the lower part of an array is maintained to be sorted. An element which is to be 'inserted’ in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort . Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

43. Insertion Sort (Characteristics) It is efficient for smaller data sets, but very inefficient for larger lists. Insertion Sort is adaptive, that means it reduces its total number of steps if a partially sorted array is provided as input, making it efficient. It is better than Selection Sort and Bubble Sort algorithms. Its space complexity is less. Like bubble Sort, insertion sort also requires a single additional memory space. It is a stable sorting technique, as it does not change the relative order of elements which are equal. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

44. Insertion Sort (Algorithm) Following are the steps involved in insertion sort: We start by making the second element of the given array, i.e. element at index 1, the key. The key element here is the new card that we need to add to our existing sorted set of cards(remember the example with cards above). We compare the key element with the element(s) before it, in this case, element at index 0: If the key element is less than the first element, we insert the key element before the first element. If the key element is greater than the first element, then we insert it after the first element. Then, we make the third element of the array as key and will compare it with elements to it's left and insert it at the right position. And we go on repeating this, until the array is sorted. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

45. Insertion Sort (Algorithm) Following are the steps involved in insertion sort: We start by making the second element of the given array, i.e. element at index 1, the key. The key element here is the new card that we need to add to our existing sorted set of cards(remember the example with cards above). We compare the key element with the element(s) before it, in this case, element at index 0: If the key element is less than the first element, we insert the key element before the first element. If the key element is greater than the first element, then we insert it after the first element. Then, we make the third element of the array as key and will compare it with elements to it's left and insert it at the right position. And we go on repeating this, until the array is sorted. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

46. 5 1 6 2 4 Start with second element as key 3 5 1 6 2 4 3 Reach the front enter 1 here 1 < 5 1 5 6 2 4 3 6 > 1 6 > 5 No Change in order 1 5 6 2 4 3 2 > 1 2 < 5 Insert 2 before 5 and after 1 2 < 6 Insertion Sort Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

47. 1 2 5 6 4 3 4 > 1 4 < 5 Insert 4 before 5 and after 2 4 < 6 4 > 2 1 2 4 5 6 3 3 > 1 3 < 5 Insert 3 before 4 and after 2 3 < 6 3 > 2 3 < 4 1 2 3 4 5 6 Sorted Array Insertion Sort Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

48. Insertion Sort (Program) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

49. Insertion Sort (Program) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

50. Quick Sort Quick Sort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of Quick Sort that pick pivot in different ways. Always pick first element as pivot. Always pick last element as pivot Pick a random element as pivot. Pick median as pivot. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

51. Quick Sort (Algorithm) Following are the steps involved in quick sort algorithm: After selecting an element as pivot, which is the last index of the array in our case, we divide the array for the first time. In quick sort, the array elements are so positioned that all the elements smaller than the pivot will be on the left side of the pivot and all the elements greater than the pivot will be on the right side of it. And the pivot element will be at its final sorted position. The elements to the left and right, may not be sorted. Then we pick subarrays, elements on the left of pivot and elements on the right of pivot, and we perform partitioning on them by choosing a pivot in the subarrays. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

52. Quick Sort (Algorithm) Partition considers the array elements a[first] through a[last ]. A ll items with keys less than the pivot are moved to lower positions in the array All items with keys greater than the pivot are moved to higher positions. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

53. Quick Sort (Algorithm) Partition considers the array elements a[first] through a[last ]. A ll items with keys less than the pivot are moved to lower positions in the array All items with keys greater than the pivot are moved to higher positions. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

54. 90 100 20 60 80 110 120 40 10 30 50 70 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] 50 30 20 60 10 40 70 110 80 100 90 120 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] 70 Pivot All are ≤ 70 All are > 70 First Last The Partition algorithm yields Quick Sort Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

55. 90 100 20 60 80 110 120 40 10 30 50 70 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] 70 Pivot First Last Quick Sort Leftpos Rightpos The algorithm increments Leftpos until the item at that position is greater than or equal to the pivot value It decrements Rightpos until the item at that position is less than or equal to the pivot value Then it swaps the values at those two positions Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

56. 90 100 20 60 80 110 120 40 10 30 50 70 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] 70 Pivot First Last Quick Sort Leftpos Rightpos 90 > 70 and 50 < 70 (swap) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

57. 50 100 20 60 80 110 120 40 10 30 90 70 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] 70 Pivot First Last Quick Sort Leftpos Rightpos 100 > 70 and 30 < 70 (swap) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

58. 50 30 20 60 80 110 120 40 10 100 90 70 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] 70 Pivot First Last Quick Sort Leftpos Rightpos 80 > 70 and 10 < 70 (swap) increment Leftpos until a[Leftpos] >= pivot Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

59. 50 30 20 60 10 110 120 40 80 100 90 70 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] 70 Pivot First Last Quick Sort Leftpos Rightpos 110 > 70 and 40 < 70 (swap) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

60. Rightpos 50 30 20 60 10 40 120 110 80 100 90 70 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] 70 Pivot First Last Quick Sort Leftpos Eventually this stops when the two variables cross paths The Partition algorithm finishes by swapping the pivot at position last with the item at Leftpos Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

61. Rightpos 50 30 20 60 10 40 70 110 80 100 90 120 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] 70 Pivot First Last Quick Sort Leftpos Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

62. Quicksort starts by partitioning the array. For the example above, the result of the first partition is 50 30 20 60 10 40 70 110 80 100 90 120 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] All are ≤ 70 All are > 70 The pivot value, 70, holds the same position it would if the array were sorted. All items to the left of it are smaller and all items to the right of it are larger. Quick Sort Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

63. The pivot value, 70 , holds the same position it would if the array were sorted. All items to the left of it are smaller and all items to the right of it are larger. Thus, the 70 is in the right spot and need not be considered further. Quicksort can continue by simply applying itself recursively to the two segments of the array above and below the pivot. Quick Sort Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

64. 50 30 20 60 10 40 70 110 80 100 90 120 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] Quick Sort 10 30 20 40 50 60 70 110 80 100 90 120 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] 10 20 30 40 50 60 70 110 80 100 90 120 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

65. Quick Sort 10 20 30 40 50 60 70 110 80 100 90 120 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] 10 20 30 40 50 60 70 110 80 100 90 120 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] 10 20 30 40 50 60 70 80 90 100 110 120 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

66. Quick Sort 10 20 30 40 50 60 70 80 90 100 110 120 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] Sorted Array Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

67. Quick Sort (Program) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

68. Quick Sort (Program) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

69. Quick Sort (Program) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

70. Quick Sort (Program) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

71. Radix Sort Radix sort is one of the sorting algorithms used to sort a list of integer numbers in order. In radix sort algorithm, a list of integer numbers will be sorted based on the digits of individual numbers. Sorting is performed from least significant digit to the most significant digit. Radix sort algorithm requires the number of passes which are equal to the number of digits present in the largest number among the list of numbers. For example, if the largest number is a 3 digit number then that list is sorted with 3 passes. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

72. Radix Sort (Algorithm) The Radix sort algorithm is performed using the following steps... Step 1 - Define 10 queues each representing a bucket for each digit from 0 to 9. Step 2 - Consider the least significant digit of each number in the list which is to be sorted. Step 3 - Insert each number into their respective queue based on the least significant digit. Step 4 - Group all the numbers from queue 0 to queue 9 in the order they have inserted into their respective queues. Step 5 - Repeat from step 3 based on the next least significant digit. Step 6 - Repeat from step 2 until all the numbers are grouped based on the most significant digit. Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane

73. Radix Sort (Algorithm) Example Consider the following list of unsorted integer numbers 82, 901, 100, 12, 150, 77, 55, 23 Step 1: Define 10 queues each represents a bucket for digit from 0 to 9 Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane queue 1 2 3 4 5 6 7 8 9

74. Radix Sort (Algorithm) Step 2: Insert all the numbers of the list into respective queue based on the Least Significant Digit (once placed digit) of every number 8 2 , 90 1 , 10 , 1 2 , 15 , 7 7 , 5 5 , 2 3 Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane queue 1 2 3 4 5 6 7 8 9 Group all the numbers from queue 0 to queue 9 in the order they have inserted & consider the list for next step as input list 100, 150, 901, 82, 12, 23, 55, 77

75. Radix Sort (Algorithm) Step 2: Insert all the numbers of the list into respective queue based on the next Least Significant Digit (tens placed digit) of every number 1 0, 1 5 0, 9 1, 8 2, 1 2, 2 3, 5 5, 7 7 Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane queue 1 2 3 4 5 6 7 8 9 Group all the numbers from queue 0 to queue 9 in the order they have inserted & consider the list for next step as input list 100, 901, 12, 23, 150, 55, 77, 82

76. Radix Sort (Algorithm) Step 2: Insert all the numbers of the list into respective queue based on the next Least Significant Digit (hundreds placed digit) of every number 1 00, 9 01, 12, 23, 1 50, 55, 77, 82 Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane queue 1 2 3 4 5 6 7 8 9 Group all the numbers from queue 0 to queue 9 in the order they have inserted & consider the list for next step as input list 12, 23, 55, 77, 82, 100, 150, 901 List got sorted in the increasing order

77. Radix Sort (Algorithm) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane    

78. Radix Sort (Algorithm) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

79. Radix Sort (Algorithm) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

80. Radix Sort (Algorithm) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane  

81. Radix Sort (Algorithm) Sanjivani K.B.P. Polytechnic, Kopargaon Department of Computer Technology Subject Faculty: V. A. Parjane