SORTING techniques.pptx

Sorting in data structures is a fundamental operation that is crucial for optimizing the efficiency of data retrieval and manipulation. By ordering data elements according to a defined sequence (numerical, lexicographical, etc.), sorting makes it possible to search for elements more quickly than would be possible in an unsorted structure, especially with algorithms like binary search that rely on a sorted array to operate effectively.

In addition, sorting is essential for tasks that require an ordered dataset, such as finding median values, generating frequency counts, or performing range queries. It also lays the groundwork for more complex operations, such as merging datasets, which requires sorted data to be carried out efficiently.

1. Data Structure & Algorithm Unit-III Sorting by: Dr. Shweta Saraswat

2. 10/8/2023 Contents Sorting Techniques:

3. S orting

4. I n t r o duc t i o n 4 Sorting techniques are fundamental algorithms in computer science and data structures. They are used to arrange data in a specific order, typically in ascending or descending order, making it easier to search for and retrieve information efficiently. There are various sorting techniques, each with its own advantages and disadvantages.

5. What is Sorting? Sorting is the process of arranging a collection of data elements in a specific order, typically in ascending or descending order. 10/8/2023

6. 6 S orting Techniques Here are some of the most commonly used sorting techniques: Bubble Sort: Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. 2. Selection Sort: Selection sort divides the input list into two parts: a sorted sublist and an unsorted sublist . It repeatedly selects the minimum element from the unsorted sublist and moves it to the sorted sublist .

7. 7 S orting Techniques Here are some of the most commonly used sorting techniques: 3. Insertion Sort: Insertion sort builds the final sorted array one item at a time. It takes one element from the input data and inserts it into its correct position within the sorted array. 4. Quick Sort: Quick sort is a divide-and-conquer sorting algorithm that works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

8. 8 S orting Techniques Here are some of the most commonly used sorting techniques: 5. Merge Sort: Merge sort is another divide-and-conquer algorithm. It divides the unsorted list into n sub-lists, each containing one element, and then repeatedly merges sub-lists to produce new sorted sub-lists until there is only one sub-list remaining. 6. Heap Sort: Heap sort is based on the data structure called a binary heap. It involves building a binary heap from the input data and repeatedly extracting the maximum element from the heap until the heap is empty.

9. 9 S orting Techniques Here are some of the most commonly used sorting techniques: 7. Counting Sort: Counting sort is a non-comparison-based sorting algorithm. It works well for integers or objects with a small, finite range of values. It counts the number of occurrences of each element and uses this information to place elements in their correct positions. 8. Radix Sort: Radix sort is another non-comparison-based sorting algorithm that works well for integers. It sorts data by processing individual digits, starting from the least significant digit to the most significant digit.

10. 10 S orting Techniques Here are some of the most commonly used sorting techniques: 9. Bucket Sort: Bucket sort divides the input data into a fixed number of buckets, and each bucket is sorted individually. After sorting, the buckets are concatenated to obtain the final sorted list. 10. Tim Sort: Tim sort is a hybrid sorting algorithm that combines elements of merge sort and insertion sort. It is designed for sorting real-world data and takes advantage of partially ordered data.

11. Basic Concepts of S orting

12. Basic Concepts of sorting Here are some basic concepts and terms related to sorting algorithms: Key: The key is the value or attribute used to compare and order the data elements. In a list of numbers, the key is the number itself. Comparison: Most sorting algorithms determine the order of elements by comparing their keys. Elements are swapped or rearranged based on the results of these comparisons. 10/8/2023

13. Basic Concepts of sorting 3. Stable vs. Unstable Sort: A sorting algorithm is stable if it maintains the relative order of equal elements. In other words, if two elements have the same key, the one that appeared first in the original list will still appear first after sorting. 4. Sorting: An in-place sorting algorithm rearranges the elements within the input data structure without requiring additional memory for a new data structure. In-place sorting algorithms are memory-efficient but may have a higher time complexity. 10/8/2023

14. Basic Concepts of sorting 5. Out-of-Place Sorting: An out-of-place sorting algorithm creates a new data structure to store the sorted elements. While it preserves the original data, it requires extra memory. 6. Comparison-Based Sorting: Many sorting algorithms are based on comparing elements to determine their order. The number of comparisons made during the sorting process is a key factor in evaluating the efficiency of these algorithms. 10/8/2023

15. Basic Concepts of sorting 7. Time Complexity: Sorting algorithms are often analyzed in terms of their time complexity, which describes how the running time of the algorithm scales with the size of the input data. Common time complexities for sorting algorithms include O(n^2), O(n*log(n)), and O(n). 8. Space Complexity: Space complexity refers to the amount of additional memory required by the sorting algorithm to perform its task. It is usually measured in terms of auxiliary memory space. 10/8/2023

16. Bubble sort 10/8/2023

17. Why it is named as bubble? It is called bubble sort because the movement of array elements is just like the movement of air bubbles in the water. Bubbles in water rise up to the surface; similarly, the array elements in bubble sort move to the end in each iteration. At each step, if two adjacent elements of a list are not in order, they will be swapped. Thus, larger elements will “bubble” to the end, (or smaller elements will be “bubbled” to the front, depending on implementation) and hence the name. 10/8/2023

18. Bubble sort Bubble sort works on the repeatedly swapping of adjacent elements until they are not in the intended order. Although it is simple to use, it is primarily used as an educational tool because the performance of bubble sort is poor in the real world. The bubble sort, also known as the ripple sort, is one of the least efficient sorting algorithms.  10/8/2023

19. Bubble short is majorly used where - complexity does not matter simple and shortcode is preferred 10/8/2023

20. Working of Bubble sort Compare the first two values and swap if necessary. Then compare the next pair of values and swap if necessary.  This process is repeated n-1 times, where n is the number of values being sorted. 10/8/2023

21. Example 10/8/2023 The example above sorts 4 numbers into ascending numerical order. As you can see, this requires 3 (n-1) passes to achieve since there are 4 items of data. The bigger numbers can be seen to bubble (or ripple) to the top.

22. Algorithm In the algorithm given below, suppose  arr  is an array of  n  elements. The assumed  swap  function in the algorithm will swap the values of given array elements. begin  BubbleSort ( arr )       for  all array elements          if   arr [ i ] >  arr [i+1]            swap( arr [ i ],  arr [i+1])         end  if       end  for           return   arr       end  BubbleSort   

23. EFFICIENCY OF THE BUBBLE SORT The bubble sort algorithm is a reliable sorting algorithm. This  algorithm  has a worst-case  time complexity  of O(n2). The bubble sort has a space complexity of O(1). The number of swaps in bubble sort equals the number of inversion pairs in the given  array.  When the array elements are few and the array is nearly sorted, bubble sort is effective and efficient. 10/8/2023

24. Bubble Sort Exercise

25. BUBBLE SORT THE CARDS AS FOLLOWS: Start from the left Compare cards 1 and 2.  If card 1 is bigger than card 2, swap their positions, otherwise leave them alone. Compare cards 2 and 3. If card 2 is bigger than card 3, swap their positions, otherwise leave them alone. Compare cards 3 and 4. If card 3 is bigger than card 4, swap their positions, otherwise leave them alone. Repeat this process until you reach the end of the row (The biggest number should have bubbled up to the right hand side of the list). Now repeat the WHOLE PROCESS again, starting from the left hand side of the list.

26. Advantages & disadvantages

27. Insertion Sort 10/8/2023

28. What Is Insertion Sort? Insertion sort is a simple and intuitive sorting algorithm in which we build the sorted array using one element at a time. It is easy to implement and is quite efficient for small sets of data, especially for substantially sorted data. It is flexible — it is useful in scenarios where all the array elements are not available in the beginning.

29. Insertion Sort? You may have used this sorting method unknowingly at some point in your life. Insertion sort is also known as “card player” sort. If you’ve ever played a game of cards, chances are you have used some form of insertion sort to arrange the cards in your hand in a strategic order. 

30. How Insertion Sort Works 1. If it is the first element, it is already sorted. 2. Pick the next element. 3. Compare with all the elements in sorted sub-list. 4. Shift all the elements in sorted sub-list that is greater than the value to be sorted. 5. Insert the value. 6. Repeat until list is sorted.

31. Example

32. Example

33. Insertion Sort Algorithm Step 1 -  If the element is the first element, assume that it is already sorted. Return 1. Step2 -  Pick the next element, and store it separately in a  key. Step3 -  Now, compare the  key  with all elements in the sorted array. Step 4 -  If the element in the sorted array is smaller than the current element, then move to the next element. Else, shift greater elements in the array towards the right. Step 5 -  Insert the value. Step 6 -  Repeat until the array is sorted.

34. Advantages & disadvantages

35. Selection Sort 10/8/2023

36. What Is Selection Sort? selection sort is an in-place comparison-based sorting algorithm. This sorting algorithm is known for its simplicity and memory efficiency it doesn’t take up any extra space. The selection sort method repeatedly searches “remaining items” to find the least one and moves it to its final location.  10/8/2023

37. Selection Sort Working Principle This algorithm divides the input array into two subparts — the sorted part and the unsorted part. Initially, the sorted part of the array is empty, and the unsorted part is the input array. The algorithm works on the principle of finding the lowest number from the unsorted part of the array and then swapping it with the first element of the unsorted part. This is done over and over until the entire array becomes sorted (in ascending order). 10/8/2023

38. Selection Sort Example Input array:  arr [ ]= 19 10 4 8 3 10/8/2023

39. First, we search for the lowest number in arr [0-4] to swap it with the unsorted part’s first element. And so, we swap 3 with 19, and the array gets modified as follows: arr [ ]=  3  10 4 8 19 Next, we need to find the lowest number in arr [1-4] to swap with the unsorted array’s first element. So, we swap 4 with 10. arr [ ]= 3  4  10 8 19 Now, we must find the lowest number in arr [2-4] and swap. arr [ ]= 3 4  8  10 19 Do the same for arr [3-4] arr [ ]= 3 4 8  10  19 And our array is sorted!

40. Selection Sort Algorithm Step 1:  Set minIndex to position 0 ( minIndex will hold the index of the smallest number in the unsorted subarray ) Step 2:  Search for the smallest element in the unsorted subarray and update minIndex Step 3:  Swap the element at the position minIndex with the first element of the unsorted subarray . Step 4:  Again set minIndex to the first position of the  unsorted subarray Step 5:   Repeat steps 2 to 4 until the array gets sorted

41. Selection Sort Complexity Time Complexity The time complexity of the selection sort algorithm is  O(n^2). Let’s look at the total number of comparisons made to get a better idea: 

42. Worst-case complexity: O(n^2) When the input array is sorted in descending order. In this case, n-1 swaps are performed Best-case complexity: O(n^2) When the array is already sorted (ascending order) In this case, no swap operation is performed Average-case complexity: O(n^2) When the array is neither sorted in ascending nor in descending order 10/8/2023

43. Space Complexity Selection sort’s space complexity is  O(1) , as it doesn’t take any extra space.  10/8/2023

44. Quick Sort 10/8/2023

45. Definition QuickSort  is a sorting algorithm based on the  Divide and Conquer algorithm  that picks an element as a pivot and partitions the given array around the picked pivot by placing the pivot in its correct position in the sorted array.

46. Divide and conquer approach Divide and conquer is a technique of breaking down the algorithms into subproblems , then solving the subproblems , and combining the results back together to solve the original problem. Divide:  In Divide, first pick a pivot element. After that, partition or rearrange the array into two sub-arrays such that each element in the left sub-array is less than or equal to the pivot element and each element in the right sub-array is larger than the pivot element. Conquer:  Recursively, sort two subarrays with Quicksort .

47. working The key process in  quickSort   is a  partition() . The target of partitions is to place the pivot (any element can be chosen to be a pivot) at its correct position in the sorted array and put all smaller elements to the left of the pivot, and all greater elements to the right of the pivot. Partition is done recursively on each side of the pivot after the pivot is placed in its correct position and this finally sorts the array. 10/8/2023

48. Choice of Pivot: There are many different choices for picking pivots.  Always pick the first element as a pivot . Always pick the last element as a pivot Pick a random element as a pivot . Pick the middle as the pivot.

49. example 10/8/2023

50. Quick sort algorithm visualization

51. Quick Sort Algorithm Step 1: An array is divided into subarrays by selecting a  pivot element  (element selected from the array). Step 2:While dividing the array, the pivot element should be positioned in such a way that elements less than pivot are kept on the left side and elements greater than pivot are on the right side of the pivot. Step 3:The left and right subarrays are also divided using the same approach. This process continues until each subarray contains a single element. Step 4: At this point, elements are already sorted. Finally, elements are combined to form a sorted array.

52. Example Array elements before quick sort are: [4 6 3 2 1 9 7 ] pivot swapped: 9, 7 Updated Array: [4 6 3 2 1 7 9 ] pivot swapped: 4, 1 Updated Array: [1 6 3 2 4 7 9 ] item swapped: 6, 2 pivot swapped: 6, 4 Updated Array: [1 2 3 4 6 7 9 ] pivot swapped: 3, 3 Updated Array: [1 2 3 4 6 7 9 ] Array elements after quick sort are: [1 2 3 4 6 7 9 ] 10/8/2023

53. Example

54. Heap Sort

55. What is a heap? A heap is a complete binary tree, and the binary tree is a tree in which the node can have the utmost two children. A complete binary tree is a binary tree in which all the levels except the last level, i.e., leaf node, should be completely filled, and all the nodes should be left-justified.

56. What is heap sort? Heapsort is a popular and efficient sorting algorithm. The concept of heap sort is to eliminate the elements one by one from the heap part of the list, and then insert them into the sorted part of the list. Heapsort is the in-place sorting algorithm.

57. working  It involves building a max heap for increasing order sorting which contains largest element of the heap at the root. For decreasing order sorting min heap is used which contains smallest element of the heap at the root. The process step of for increasing order sorting of heap sort is summarized below: Step 1:  Build a max heap which contains largest element of the heap at the root Step 2:  Swap the last element of heap with root element and remove the last element from the heap. With the remaining elements repeat the step 1.

58. example To understand the heap sort, lets consider an unsorted array  [10, 1, 23, 50, 7, -4] In the below figure, the heap structure of input array and max heap is shown. The index number of the root element of the heap is 0. In max heap, the largest element of the heap always resides at the root.

59. example

60. example

61. Advantages and Disadvantages

62. Merge sort

63. Definition Merge Sort is a popular and efficient comparison-based sorting algorithm. It is a divide-and-conquer algorithm that divides the input list into smaller sublists , sorts those sublists , and then merges the sorted sublists to produce a fully sorted list. The key idea is to repeatedly divide the list in half until it is broken down into smaller, sortable pieces and then combine (merge) those pieces to produce the final sorted result.

64. Merge sort is similar to the quick sort algorithm as it uses the divide and conquer approach to sort the elements. It is one of the most popular and efficient sorting algorithm. It divides the given list into two equal halves, calls itself for the two halves and then merges the two sorted halves. We have to define the  merge()  function to perform the merging.

65. Algorithm Merge Sort is a divide-and-conquer algorithm for sorting a list of elements. Here are the high-level steps for the Merge Sort algorithm: Divide : Divide the unsorted list into two roughly equal halves. This can be done by finding the middle index of the list. Conquer : Recursively sort the two smaller sublists created in the previous step. This process continues until the sublists are small enough to be considered sorted by definition (i.e., they contain only one element). Merge : Merge the two sorted sublists to produce a single, sorted list. This is the most critical step in the Merge Sort algorithm. a. Create two temporary arrays (or lists) to hold the two sublists . b. Initialize three index variables: one for each of the two sublists and one for the main merged list. c. Compare the elements at the current indices of the two sublists and select the smaller element. Copy this element to the merged list and increment the corresponding sublist index. d. Repeat the comparison and copying process until you've gone through both sublists . e. If one of the sublists still has elements remaining, copy those elements to the merged list. Return the merged, sorted list as the final result.

66. example

67. example

68. example

69. Applications of Merge Sort: Sorting large datasets:  Merge sort is particularly well-suited for sorting large datasets due to its guaranteed worst-case time complexity of O(n log n). External sorting:  Merge sort is commonly used in external sorting, where the data to be sorted is too large to fit into memory. Custom sorting:  Merge sort can be adapted to handle different input distributions, such as partially sorted, nearly sorted, or completely unsorted data.

70. Merge sort

71. Radix Sort

72. What is radix? In radix sorting, the term "radix" refers to the base of the numeral system being used to represent the numbers you are sorting. It is essentially the number of unique digits or symbols that can be used to represent values in that numeral system. Commonly used radices include base-2 (binary), base-10 (decimal), and base-16 (hexadecimal). Example : In decimal radix sorting (base-10), there are 10 unique digits (0-9) that can be used to represent numbers. Each digit can be considered a "radix."

73. Definition Radix sort is a non-comparative integer sorting algorithm that works by distributing elements into a set of "buckets" or "bins" based on their individual digits or radix (e.g., decimal digits in the case of base-10 numbers). The algorithm processes the elements from the least significant digit (LSB) to the most significant digit (MSB) or vice versa, performing multiple passes until all digits have been considered. 10/8/2023

74. Working The Radix sort algorithm works by ordering each digit from least significant to most significant.  In base 10, radix sort would sort by the digits in the one's place, then the ten's place, and so on. To sort the values in each digit place, Radix sort employs counting sort as a subroutine. This means that for a three-digit number in base 10, counting sort will be used to sort the 1st, 10th, and 100th places, resulting in a completely sorted list. Here's a rundown of the counting sort algorithm.

75. Example 10/8/2023

76. Example

77. What Is a Radix Sort Algorithm? Radix Sort is a linear sorting algorithm. Radix Sort's time complexity of O( nd ), where n is the size of the  array  and d is the number of digits in the largest number. It is not an in-place sorting algorithm because it requires extra space. Radix Sort is a stable sort because it maintains the relative order of elements with equal values. Radix sort algorithm may be slower than other sorting algorithms such as merge sort and  Quicksort  if the operations are inefficient. These operations include sub-inset lists and delete functions, and the process of isolating the desired digits. Because it is based on digits or letters, radix sort is less flexible than other sorts. If the  type of data  changes, the Radix sort must be rewritten.

78. Application Radix sort is a stable sorting algorithm, which means that it preserves the relative order of equal elements. It is particularly efficient when sorting a large number of integers with a limited range of values. However, it may not be the best choice for sorting data with variable-length keys or data that doesn't have a clear radix (e.g., strings or floating-point numbers).

79. Advantages Radix Sort Algorithm Fast when the keys are short, i.e. when the array element range is small. Used in suffix arrays construction algorithms such as Manber's and the DC3 algorithm. Radix Sort is a stable sort because it maintains the relative order of elements with equal values. 10/8/2023

80. Disadvantages of Radix Sort Algorithm The Radix Sort algorithm is less flexible than other sorts because it is based on digits or letters. As a result, for each different type of data, it must be rewritten. Radix sort has a higher constant than other sorting algorithms. It takes up more space than Quicksort , which is used for in-place sorting. Radix sort may be slower than other sorting algorithms such as merge sort and Quicksort if the operations are inefficient. These operations include sub-inset lists and delete functions, as well as the process of isolating the desired digits. Because it is based on digits or letters, the radix sort is less flexible than other sorts. If the data type must be rewritten, so must the Radix sort.

81. Note Radix sort and bucket sort are almost equivalent; bucket sort goes from MSD to LSD, while radix sort is capable of both "direction" (LSD or MSD).

82. Counting Sorting 10/8/2023

83. Definition Counting sort is a sorting technique that is based on the keys between specific ranges 10/8/2023

84. Approach This sorting technique doesn't perform sorting by comparing elements. It performs sorting by counting objects having distinct key values like hashing. After that, it performs some arithmetic operations to calculate each object's index position in the output sequence. Counting sort is not used as a general-purpose sorting algorithm. Counting sort is effective when range is not greater than number of objects to be sorted. It can be used to sort the negative input values. 10/8/2023

85. Working of counting sort Algorithm Now, let's see the working of the counting sort Algorithm. To understand the working of the counting sort algorithm, let's take an unsorted array. It will be easier to understand the counting sort via an example. Let the elements of array are – 10/8/2023

86. example 10/8/2023

87. example Now, we have to store the count of each array element at their corresponding index in the count array. The count of an element will be stored as - Suppose array element '4' is appeared two times, so the count of element 4 is 2. Hence, 2 is stored at the 4 th  position of the count array. If any element is not present in the array, place 0, i.e. suppose element '3' is not present in the array, so, 0 will be stored at 3 rd  position. 10/8/2023

88. example 10/8/2023

89. example

90. example

91. example

92. Advantages of Counting Sort: It is quite fast It is a stable algorithm Note:  For a sorting algorithm to be stable, the order of elements with equal keys (values) in the sorted array should be the same as that of the input array. 10/8/2023

93. Disadvantages of Counting Sort: It is not suitable for sorting large data sets It is not suitable for sorting string values

94. Comparison of Time and space complexity

95. Types of Sorting 1. Comparison based sorting algorithm 2.Linear time sorting algorithm 3.In-place sorting algorithm 4. Stable sorting algorithm 10/8/2023

96. 1. Comparison based sorting

97. 2.Linear time sorting

98. 3. In-place sorting algorithm

99. 4. Stable sorting algorithm

100. 10/8/2023