Sorting and Searching

Bubble sort and selection sort are two of the simplest sorting algorithms, both running in O(n^2) time and O(1) additional space, which makes them easy to understand but impractical for large datasets. Bubble sort repeatedly steps through the list, comparing each pair of adjacent elements and swapping them if they are out of order, so that with each full pass the largest remaining unsorted element "bubbles" up to its correct position at the end. Selection sort instead repeatedly scans the unsorted portion of the list to find its minimum element and swaps that minimum into place at the front of the unsorted portion; it performs far fewer swaps than bubble sort, which makes it preferable in situations where the cost of a swap is high relative to the cost of a comparison.