Selection Sort & Insertion Sorts Algorithms

Selection Sort is a simple comparison-based sorting algorithm. It works by repeatedly finding the smallest (or largest, depending on the sorting order) element from the unsorted portion of the list and swapping it with the first element of the unsorted portion.

1. Selection & Insertion Sort Algorithms Ahmad Baryal Saba Institute of Higher Education Computer Science Faculty Oct 2, 2024 1

2. Selection Sort Algorithm Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end . Initially, the sorted part is empty and the unsorted part is the entire list. The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundary by one element to the right. This algorithm is not suitable for large data sets as its average and worst case complexities are of Ο(n2), where n is the number of items. 2

3. How Selection Sort Works? Consider the following depicted array as an example. For the first position in the sorted list, the whole list is scanned sequentially. The first position where 14 is stored presently, we search the whole list and find that 10 is the lowest value. So we replace 14 with 10. After one iteration 10, which happens to be the minimum value in the list, appears in the first position of the sorted list. For the second position, where 33 is residing, we start scanning the rest of the list in a linear manner. 3

4. How Selection Sort Works? We find that 14 is the second lowest value in the list and it should appear at the second place. We swap these values. After two iterations, two least values are positioned at the beginning in a sorted manner. 4

5. How Selection Sort Works? The same process is applied to the rest of the items in the array. Following is a pictorial depiction of the entire sorting process − 5

6. Algorithm 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 6

7. Pseudocode 7

8. Applications 8 Small Data Sets: Insertion sort is efficient for sorting small amounts of data or nearly sorted data due to its simplicity and low overhead. Online Algorithms: Suitable for online algorithms where data is received incrementally. The sorted array is updated with each new element, making it practical for streaming data. Linked Lists: Particularly advantageous for sorting linked lists. Unlike arrays, linked lists don't require expensive element-shifting during the insertion process. Adaptive Sorting: Adaptive nature allows it to perform better on partially sorted data. It adapts well to situations where the input is already somewhat ordered. Stability: Maintains the relative order of equal elements, making it valuable in applications where preserving the original order is crucial. Binary Insertion Sort: A variant that uses binary search to reduce the number of comparisons, making it more efficient in scenarios where comparisons are costly. Hardware Optimizations: Can be more cache-friendly on certain architectures, especially for small datasets, as it works well with localized data access patterns.

9. Insertion Sort Algorithm 9

10. Insertion Sort Algorithm This is an in-place comparison-based sorting algorithm. Here, 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 ' insert’ ed in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort . The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list (in the same array). 10

11. How Insertion Sort Works? We take an unsorted array for our example. Insertion sort compares the first two elements. It finds that both 14 and 33 are already in ascending order. For now, 14 is in sorted sub-list. Insertion sort moves ahead and compares 33 with 27. 11

12. How Insertion Sort Works? And finds that 33 is not in the correct position. It swaps 33 with 27. It also checks with all the elements of sorted sub-list. Here we see that the sorted sub-list has only one element 14, and 27 is greater than 14. Hence, the sorted sub-list remains sorted after swapping. By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with 10. These values are not in a sorted order. 12

13. How Insertion Sort Works? So we swap them. However, swapping makes 27 and 10 unsorted. Hence, we swap them too. Again we find 14 and 10 in an unsorted order. 13

14. How Insertion Sort Works? We swap them again. By the end of third iteration, we have a sorted sub-list of 4 items. This process goes on until all the unsorted values are covered in a sorted sub-list. Now we shall see some programming aspects of insertion sort. 14

15. Time Complexity of Insertion sort Insertion Sort is an elementary sorting algorithm that builds the final sorted array one item at a time. The time complexity of Insertion Sort depends on the number of comparisons and swaps it makes. Here's a breakdown of its time complexity in various cases: Worst-case time complexity : O(n^2) The worst-case scenario occurs when the input array is in reverse order (i.e., the largest element is at the beginning). In this case, Insertion Sort makes the maximum number of comparisons and swaps. The number of comparisons and swaps is roughly proportional to n^2, where n is the number of elements in the array. Best-case time complexity : O(n) The best-case scenario occurs when the input array is already sorted in ascending order. In this case, Insertion Sort performs n-1 comparisons but no swaps because each element is in its correct place. The number of comparisons is linear, making it the best-case time complexity. Average-case time complexity : O(n^2) In the average case, Insertion Sort also exhibits a quadratic time complexity. On average, it requires roughly n^2/4 comparisons and swaps. The exact number of comparisons and swaps depends on the distribution of input data. 15

16. Advantages of Insertion sort Efficiency for Small Datasets : Insertion Sort is efficient for sorting small datasets. Its simplicity and low overhead make it a practical choice when dealing with a limited number of elements. Nearly Sorted Arrays : When the data is already nearly sorted or has a small number of elements out of place, Insertion Sort can perform exceptionally well. It minimizes unnecessary comparisons and swaps in such scenarios. Stable Sorting : It is a stable sorting algorithm, meaning it preserves the relative order of equal elements. This property is valuable in certain applications where preserving the original order of equal elements is essential. Lack of Parallelism : Insertion Sort's step-by-step nature makes it less amenable to parallel processing compared to some other sorting algorithms, which can take advantage of multiple processors or cores for faster sorting. 16

17. Disadvantages of Insertion sort Quadratic Time Complexity : In the worst-case scenario, such as when the array is in reverse order, Insertion Sort exhibits quadratic time complexity. This means that the number of comparisons and swaps grows rapidly with the size of the input, leading to poor performance. Not Suitable for Highly Unsorted Data : Insertion Sort is not suitable for highly unsorted or randomly ordered data. It requires a significant number of comparisons and shifts to rearrange elements in such cases, resulting in inefficient sorting. Lack of Parallelism : Insertion Sort's step-by-step nature makes it less amenable to parallel processing compared to some other sorting algorithms, which can take advantage of multiple processors or cores for faster sorting. 17

18. Algorithms Step 1 − If it is the first element, it is already sorted. return 1; Step 2 − Pick next element Step 3 − Compare with all elements in the sorted sub-list Step 4 − Shift all the elements in the sorted sub-list that is greater than the value to be sorted Step 5 − Insert the value Step 6 − Repeat until list is sorted 18

19. Pseudocode 19

20. Any Questions? 20