This is the 27th day of my participation in the August Genwen Challenge.More challenges in August
Bubble sort
Bubble sort, sometimes called sinking sort, is a simple sorting algorithm that iterates over the list to be sorted, comparing each pair of adjacent items, and swapping them if they are in the wrong order (ascending or descending). Iterating through the list until swapping is not required indicates that the list is sorted.
Selection sort
Selection sort is a sort algorithm, especially in place comparison sort. Its time complexity of O(n2) makes it inefficient on large lists and generally performs worse than similar insertion sorts. Selection sorting is noted for its simplicity, and in some cases has a performance advantage over more complex algorithms, especially if secondary memory is limited.
Insertion sort
Insertion sort is a simple sorting algorithm that builds a final sorted array (or list) one at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heap sort, or merge sort.
Heap sort
Heap sort is a sort algorithm based on comparison. Heapsort can be thought of as an improved selection sort: like the algorithm, it divides the input into sorted and unsorted regions, and iteratively shrinks the unsorted region by extracting the largest element and moving it to the sorted region. Improvements include using heap data structures instead of linear time searches to find maximum values.
Merge sort
In computer science, merge sort (also commonly spelled merge sort) is an efficient, general, comparison-based sorting algorithm. Most implementations produce stable sorting, which means that the implementation preserves the input order of equal elements in the sorted output. Merge sort is a divide-and-conquer algorithm invented by John von Neumann in 1945.
An example of merge sort. The list is first divided into the smallest units (1 element), and then each element is compared to the adjacent lists, sorting and merging the two adjacent lists. Finally, all elements are sorted and merged.
Quick sort
Quicksort is a divide-and-conquer algorithm. Quicksort starts by dividing a large array into two smaller subarrays: the low element and the high element. Quicksort can then sort subarrays recursively
Steps are:
- Selects an element called pivot from the array.
- Partitioning: Rearranges the array so that all elements with values less than the pivot are before the pivot and all elements with values greater than the pivot are behind it (equality can be done in any way). After this partition, the pivot is in its final position. This is called partitioning.
- Apply the above steps recursively to subarrays of elements with smaller values, and separately to subarrays of elements with larger values.
Animated visualization of quicksort algorithms. The horizontal line is the pivot value.
Reference: github.com/trekhleb/ja…