C Library Functions - M_sort (3)
NAME
M_sort(3fm) - [M_sort::INTRO] Fortran module containing sorting algorithms for arrays of standard scalar types (LICENSE:PD)
CONTENTS
Synopsis
Description
Ranking
Quicksort
SYNOPSIS
Usage:
use M_sort, only : sort_quick_rx, sort_quick_compact use M_sort, only : sort_shell, sort_heap use M_sort, only : 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
RANKING
Sorting generally refers to rearranging data in a specific order. Ranking consists in finding, for each element of a set, its rank in the sorted set, without changing the initial order of the set. In many instances ranking is more flexible in that the order may be based on one value of a user-defined type, and the indices can be used to reorder virtually any type or related set; but it requires creating an array of indices as well as the data being sorted.
Ranking is also useful when the sizes of the elements being sorted are large, and therefore moving them around is resource-consuming.
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.
| Nemo Release 3.1 | M_sort (3) | February 23, 2025 |
