Manual Reference Pages - M_sort (3)
NAME
M_sort(3fm) - [M_sort] Fortran module containing sorting algorithms for arrays of standard scalar types (LICENSE:PD)
CONTENTS
Synopsis
Description
Quicksort
SYNOPSIS
use M_sort, only : sort_shell, sort_quick_rx, unique
DESCRIPTION
Under development. Currently only provides a few common routines, but it is intended that other procedures will provide a variety of sort methods, including ...
In the mean time those keywords can be useful in locating materials on the WWW, especially in Wikipedia.
Exchange sorts Bubble sort, Cocktail shaker sort, Odd-even sort, Comb sort, Gnome sort, Quicksort, Stooge sort, Bogosort Selection sorts Selection sort, Heapsort, Smoothsort, Cartesian tree sort, Tournament sort, Cycle sort Insertion sorts Insertion sort, Shellsort, Splaysort, Tree sort, Library sort, Patience sorting Merge sorts Merge sort, Cascade merge sort, Oscillating merge sort, Polyphase merge sort Distribution sorts American flag sort, Bead sort, Bucket sort, Burstsort, Counting sort, Pigeonhole sort, Proxmap sort, Radix sort, Flashsort Concurrent sorts Bitonic sorter, Batcher odd-even mergesort, Pairwise sorting network Hybrid sorts Block merge sortTimsort, Introsort, Spreadsort Other Topological sorting, Pancake sorting, Spaghetti sort and an overview of topics concerning sorting Theory Computational complexity theory, Big O notation, Total orderLists, InplacementStabilityComparison sort, Adaptive sort, Sorting network, Integer sorting, X + Y sorting, Transdichotomous model, Quantum sort
QUICKSORT
Quicksort, also known as partition-exchange sort, uses these steps
o Choose any element of the array to be the pivot. o Divide all other elements (except the pivot) into two partitions. o All elements less than the pivot must be in the first partition. o All elements greater than the pivot must be in the second partition. o Use recursion to sort both partitions. o Join the first sorted partition, the pivot, and the second sorted partition. The best pivot creates partitions of equal length (or lengths differing by 1).
The worst pivot creates an empty partition (for example, if the pivot is the first or last element of a sorted array).
The run-time of Quicksort ranges from O(n log n) with the best pivots, to O(n2) with the worst pivots, where n is the number of elements in the array.
Quicksort has a reputation as the fastest sort. Optimized variants of quicksort are common features of many languages and libraries.
| M_sort (3) | March 11, 2021 |
