정렬 알고리즘 (1)

다양한 정렬 알고리즘을 공부하고 Rust로 구현합니다.

정렬 알고리즘

정렬 알고리즘(sorting algorithm)은 무작위로 형성된 숫자 리스트나 원소들을 순서에 맞게 나열해주는 알고리즘이다. 정렬 알고리즘의 종류는 선택정렬, 삽입정렬, 버블정렬, 합병정렬, 퀵정렬 등 다양하며, 종류에 따라 시간복잡도나 공간복잡도도 달라진다.

이번 글에서는 정렬 알고리즘 중에서 기본적인 선택정렬과 삽입정렬, 버블 정렬에 대해서 살펴볼 것이다.

선택 정렬

선택 정렬은 조건에 속하는 값을 선택하여 배열하는 정렬 알고리즘이다. 오름차순으로 정렬하는 방법을 최소선택정렬이라고 하며, 내림차순으로 정렬하는 방법을 최대선택정렬이라고 한다.

로직은 다음과 같다.

정렬되지 않은 리스트에서 최솟(댓)값을 찾아 인덱스를 저장한다.
리스트에서 더 작은 최솟(댓)값이 있다면 해당 인덱스로 변경한다.
마지막 인덱스에 도착하면 가장 작은 최솟(댓)값과 값을 변경한다.

위 로직에 따르면 맨 앞에서부터 최솟(댓)값이 정렬되기 때문에 반복할수록 비교해야 할 원소의 개수는 (총 개수 - 정렬된 개수)로 줄어든다. 또한 선택 정렬은 현재 상태와 상관없이 하나의 값 당 리스트 모든 원소를 살펴봐야 하기 때문에 시간복잡도는 $O(n^2)$이며, 리스트 내에서 정렬이 진행되기 때문에 공간복잡도는 $O(n)$이다.

선택 정렬 예시를 러스트(Rust)로 구현하면 다음과 같다.

fn main() {
    let lis: [i32; 10] = [10,9,6,2,4,5,7,1,0,3];
    selection_sort(lis);
}

fn selection_sort(mut lis: [i32; 10]) {
    for i in 0..lis.len()-1{
        for j in i..lis.len(){
            let mut min = lis[i];
            let mut idx = i;
            if min > lis[j]{
                idx = j;
                min = lis[j];
            }
            lis[idx] = lis[i];
            lis[i] = min;
        }
    }
    println!("{:?}",lis)
}

버블 정렬

버블 정렬은 연속된 두개의 값만 비교하여 기준에 따라 위치를 바꾸는 방식이다. 만약 오름차순을 조건으로 버블 정렬을 한다면 연속되는 두개의 값 중 큰 수를 뒷자리로 보내게 되며, 결국 한바퀴 돌았을 때 가장 큰 수가 맨 뒷자리에 위치하게 된다.

로직은 다음과 같다.

연속되는 두 수를 비교하여 큰 값을 뒤로 위치시킨다.
이를 반복하여 맨 뒷자리에 가장 큰 값이 위치된다.

위 로직에 따르면 맨 뒤에서부터 최댓값이 정렬되기 때문에 반복할수록 비교해야 할 원소의 개수는 (총 개수 - 정렬된 개수)로 줄어든다. 또한 버블 정렬은 하나의 값 당 리스트 모든 원소를 살펴봐야 하기 때문에 시간복잡도는 $O(n^2)$이며, 리스트 내에서 정렬이 진행되기 때문에 공간복잡도는 $O(n)$이다.

버블 정렬 예시를 러스트(Rust)로 구현하면 다음과 같다.

fn main() {
    let lis: [i32; 10] = [10,9,6,2,4,5,7,1,0,3];
    bubble_sort(lis);
}

fn bubble_sort(mut lis: [i32; 10]) {
    for _ in 0..lis.len(){
        for j in 0..lis.len()-1{
            if lis[j] > lis[j+1]{
                let temp = lis[j];
                lis[j] = lis[j+1];
                lis[j+1] = temp;
            }
        }
    }
    println!("{:?}",lis)
}

삽입 정렬

삽입 정렬은 현 위치에 있는 숫자를 그 이전 숫자와 비교하여 위치를 찾아주는 방식이다. 앞에 있는 숫자와 비교하기 때문에 인덱스 2번부터 시작되며, 앞 숫자가 자신보다 더 작은 경우에 정렬은 끝난다.

로직은 다음과 같다.

현 위치의 숫자는 바로 앞의 숫자와 크기를 비교하여 더 작은 경우 자리를 바꾼다.
계속 앞으로 가며 자리를 바꾸다가 앞 숫자가 크기가 작거나 같은 경우 이동을 멈춘다.
이를 2번째 인덱스부터 마지막 인덱스까지 진행한다.

위 로직에 따르면 자신보다 작은 값이 앞에 있을 때까지만 이동하면 되기 때문에 숫자마다 비교해랴 하는 개수는 리스트 형식에 따라 다르다. 따라서 삽입 정렬에서 시간복잡도는 리스트가 정렬되어 있는 경우의 $O(n)$부터 역으로 정렬되어 있는 경우의 $O(n^2)$까지 모두 가능하며, 공간복잡도는 리스트 내에서 정렬이 진행되기 때문에 $O(n)$이다.

삽입 정렬 예시를 러스트(Rust)로 구현하면 다음과 같다.

fn main() {
    let lis: [i32; 10] = [10,9,6,2,4,5,7,1,0,3];
    insertion_sort(lis);
}

fn insertion_sort(mut lis: [i32; 10]) {
    for i in 1..lis.len(){
        for j in (1..i+1).rev(){
            if lis[j] < lis[j-1]{
                let temp = lis[j];
                lis[j] = lis[j-1];
                lis[j-1]=temp
            }
            else{
                break
            }
        }
    }
    println!("{:?}",lis)
}