valikusorteerimine

Valikusorteerimine, also known as selection sort in English, is a simple comparison-based sorting algorithm. Its main idea is to repeatedly find the minimum element from the unsorted part of the list and put it at the beginning. This process continues until the entire list is sorted.

The algorithm works by dividing the input list into two parts: a sorted sublist which is built up from left to right at the front of the list, and an unsorted sublist which occupies the rest of the list. Initially, the sorted sublist is empty, and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest element in the unsorted sublist, swapping it with the leftmost unsorted element, and moving the sublist boundary one element to the right.

For an array of size n, selection sort performs approximately n^2/2 comparisons and n swaps. Its time complexity is O(n^2) in all cases (best, average, and worst), making it inefficient for large datasets. However, it is simple to implement and has a low number of swaps, which can be advantageous in scenarios where write operations are expensive. Selection sort is an in-place algorithm, meaning it requires only a constant amount of auxiliary memory. It is not a stable sort, meaning that the relative order of equal elements may not be preserved.