[알고리즘] 정렬알고리즘(2) - bubble sort, 버블정렬

Sorting algorithm 2. 버블정렬

버블정렬은 현재 인덱스와 현재 인덱스 + 1의 원소를 비교하여 정렬하는 방법이다.

1. 0번째 index의 값과 0 + 1번째 index의 값을 비교한다.

2. 0번째 index의 값이 더 클경우 swap을 진행한다.

간단하게 위 과정을 배열의 길이만큼 반복하면 된다.

 

코드로 구현 rust

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

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

Time Complexity = O(n²)이다.