what is Selection Sort algorithm

what is Selection Sort algorithm

  2월 25, 2022    Eunhan's library

---

Selection Sort Algorithm

Definition

one way of sorting algorithms by using brute force.
check every possible ways to sort the list.

Algorithm steps

1. find smallest number in the list
2. swap the smallest number and first place
3. the first element is sorted
4. find smallest number in the list except the sorted element.
5. swap the smallest number and second place
6. Repeat 1~5 until all of them sorted.

Avg. time complexity

$O(n^2)$

Worst time complexity

$O(n^2)$

space complexity

$O(1)$

stability

no

Java code

    public static int[] selectionSort(int[] input) {
        for (int i = 0; i < input.length - 1; ++i) {
            for (int j = input.length - 1; j > i; --j) {
                if (input[j] < input[i]) {
                    int temp = input[i];
                    input[i] = input[j];
                    input[j] = temp;
                }
            }
        }
        return input;
    }

---

How to calculate

numbers of loop

$n-1$

The most visited place of the list

$n-1$ (the last place)

The least visited place of the list

$1$ (the first place)

Avg. visited numbers of the list

(The most visited place of the list+The least visited place of the list)/2 $= \frac{(n-1+1)}{2} = \frac{n}{2}$

Polynomial Time

numbers of loop*Avg. visited numbers of the list $=(n-1)\cdot \frac{n}{2}$

Time Complexity

$O(Polynomial\; Time)=O((n-1)\cdot \frac{n}{2})=O((\frac{n^2}{2}-\frac{n}{2}))=O(n^2)$