[알고리즘] 정렬 알고리즘(1) - selection sort, 선택정렬

정렬 알고리즘 시리즈를 시작해보려고 한다.

기초 정렬 알고리즘인 selection sort부터 시작해서 Insertion sort, merge sort, heap sort, bubble sort 등등..

오늘은 그 첫번째인 선택정렬이다.

Sorting algorithm 1. 선택정렬

 선택정렬은 가장 작은 수를 선택하여 교환을 반복하는 정렬이다.

interger type 배열의 정렬으로 예를 들어보자.

아래와 같은 배열이 있다.

이 배열을 순차적으로 돌며 가장 작은 값을 교환해줄 것이다.

1. 0번째 index부터 시작하여, 0번째 이후의 원소 중 가장 작은 값을 찾아서 값을 교환한다.

2. 1번째 index를 가리키며 1번째 이후의 원소 중 가장 작은 값을 찾아서 값을 교환한다.

3. 1번과 2번을 반복한다.

4. 마지막엔 정렬이 된 배열을 얻을 수 있다.

 

코드로 구현(Javascript)

function selectionSort(){
    let array = [6, 5, 2, 4, 3, 1];
    for(let i = 0; i < array.length; i++){
        let minIndex = i;
        for(let j = i + 1; j < array.length; j++){
            if(array[j] < array[minIndex]){
                minIndex = j;
            }
        }
        const curr = array[minIndex];
        array[minIndex] = array[i];
        array[i] = curr;
    }
    console.log(array);
}

rust

impl ArraySort {
    fn selection_sort(array: &mut Vec<i32>) {
        for i in 0..array.len() {
            let mut min_index = i;
            for j in i + 1..array.len() {
                if array[j] < array[min_index] {
                    min_index = j;
                }
            }
            let curr = array[min_index];
            array[min_index] = array[i];
            array[i] = curr;
        }
        println!("{:?}", array);
    }
}

 

2중 반복문을 이용하여 구현하며 배열의 index마다 배열의 길이만큼 반복하므로

Time complexity = O(n²)이다.