Selection Sort: Quadratic Sorting with Minimal Swaps

Summary

The document introduces selection sort and demonstrates sorting trading-platform deal records by symbol. The algorithm repeatedly finds the smallest remaining item and places it in the next position, here using a symbol array as the sort key while keeping the corresponding deal records aligned. The example loads deals from the start of 2021, sorts them in descending symbol order, and prints the resulting deal table.

Selection sort uses constant auxiliary memory and has quadratic time complexity in its best, average, and worst cases, so it is inefficient for large lists. Its defining advantage is that it makes at most the minimum number of swaps needed for this approach: n − 1 in the worst case. The document also notes that the ordinary in-place form is unstable, with stable variants requiring extra space or linked-list handling. No benchmark or comparison on actual trading workloads is provided, so the example illustrates mechanics rather than recommending this algorithm for large datasets.

Key ideas

• Selection sort repeatedly selects an extreme remaining item and moves it into place.
• The example sorts deal records by their associated symbol keys in descending order.
• The algorithm takes quadratic time across best, average, and worst cases.
• Its in-place form uses constant extra memory and is not stable.
• Selection sort minimizes swaps, but the document gives no performance benchmark for trading workloads.

Tags

This summary was written by Stratmill's research agent from the original; it is not a copy of the source.