Elementary sorting methods

The Mastery of Computer Programming: Primary Algorithms - Sykalo Eugene 2023

Elementary sorting methods
Sorting and Searching

Selection Sort

Selection sort is a simple and easy-to-understand algorithm that involves finding the minimum element in an array and placing it at the beginning of the array. Then, the process is repeated for the remaining elements. This algorithm works by dividing the input list into two parts: the sublist of items already sorted, which is initially empty, and the sublist of items remaining to be sorted. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest element in the unsorted sublist, exchanging it with the leftmost unsorted element, and moving the sublist boundaries one element to the right.

The algorithm consists of n-1 passes, where n is the number of elements in the array. During each pass, the smallest element in the unsorted portion of the array is identified and swapped with the leftmost element in the unsorted portion of the array. As a result, after each pass, the leftmost element in the unsorted portion of the array becomes a part of the sorted portion of the array.

Selection sort has a time complexity of O(n^2), which makes it inefficient for large lists. However, it has the advantage of requiring only a small amount of additional memory, which makes it useful for sorting small lists or in applications where memory is limited.

Bubble Sort

Bubble sort is another elementary sorting method that involves comparing adjacent pairs of elements in an array and swapping them if they are in the wrong order. The process is repeated until the array is sorted.

The algorithm works by repeatedly swapping the adjacent elements if they are in the wrong order. This process is repeated n-1 times, where n is the number of elements in the array. After each pass, the largest element is moved to its correct position at the end of the array.

Bubble sort has a time complexity of O(n^2), which makes it inefficient for large lists. However, it has the advantage of being simple to understand and implement, which makes it useful for educational purposes or in applications where the list is already mostly sorted.

Insertion Sort

Insertion sort is an algorithm that involves iterating through an array and inserting each element in its correct position in the sorted subarray. The algorithm works by dividing the input list into two parts: the sorted sublist and the unsorted sublist. Initially, the sorted sublist contains only the first element of the input list, while the unsorted sublist contains the remaining n-1 elements.

The algorithm proceeds by iterating through the unsorted sublist, one element at a time, and inserting each element in its correct position in the sorted sublist. To insert an element into the sorted sublist, the algorithm compares it with each element in the sorted sublist, from right to left, until it finds the correct position. The elements in the sorted sublist that are greater than the current element are shifted one position to the right to make room for the new element.

Insertion sort has a time complexity of O(n^2), which makes it inefficient for large lists. However, it has the advantage of being stable (i.e., it does not change the relative order of equal elements) and adaptive (i.e., it performs well on partially sorted lists).

One of the key applications of insertion sort is in the implementation of other sorting algorithms, such as quicksort and Timsort, which use insertion sort for small subarrays or as a fallback when the recursion depth exceeds a certain threshold.

Shell Sort

Shell sort is an improvement over insertion sort that involves sorting elements that are far apart first and then progressively narrowing the gap between the elements. The algorithm works by dividing the input list into smaller sublists, each of which is sorted using insertion sort. The sublists are created by choosing a gap sequence, which determines the spacing between the elements that are compared and swapped during the sorting process.

The gap sequence can be chosen in many ways, but one common method is to use the Knuth sequence, which is defined as follows:

h_i = 3 * h_{i-1} + 1

where h_0 = 1 and i is the index of the gap in the sequence. The last gap in the sequence should be less than or equal to the size of the array being sorted.

After the sublists are sorted, the gap is narrowed and the process is repeated until the gap is 1, at which point the algorithm becomes equivalent to insertion sort.

Shell sort has a time complexity of O(n^(3/2)), which makes it more efficient than insertion sort for large lists. However, its performance is still worse than more advanced sorting algorithms such as quicksort and mergesort.

Despite its relatively poor performance, shell sort is still used in some applications, especially when the input list is already partially sorted or when memory is limited.

Merge Sort

Merge sort is a divide-and-conquer algorithm that involves dividing an array into two halves, sorting each half, and then merging the two sorted halves. The algorithm works by recursively dividing the input array into smaller subarrays until each subarray has only one element. Then, the subarrays are merged back together in a sorted order.

The merge operation is the key to the efficiency of merge sort. It involves comparing the first element of each subarray and selecting the smaller one to be the next element in the merged array. This process is repeated until all elements from both subarrays have been merged into the final sorted array.

Merge sort has a time complexity of O(n log n), which makes it more efficient than elementary sorting methods such as selection sort and bubble sort. It is also a stable sorting algorithm, meaning that it preserves the relative order of equal elements.

Despite its efficiency, merge sort has the disadvantage of requiring additional memory to store the subarrays during the sorting process. However, this disadvantage can be mitigated by using an in-place merge sort algorithm, which rearranges the elements in the original array instead of creating new subarrays.