버블정렬

목표

버블정렬 정의 설명

과정 설명

구현

시간복잡도와 공간복잡도 계산

버블 정렬 정의

서로 인접한 값을 비교하여 조건에 맞지 않으면 자리를 교환하여 정렬하는 알고리즘이다.

버블 정렬 과정

정렬은 총 n라운드로 이루어진다.

1. 라운드마다 배열의 원소를 쭉 살펴보면서 순서가 잘못되어 있는 것을 발견하면 원소를 맞바꾼다.

2. 라운드가 진행될 때마다 가장 큰 수가 배열 가장 끝 인덱스로 이동하게 되므로 해당 인덱스를 정렬에서 제외하고 다음 라운드로 넘어간다.

3. 라운드가 진행될수록 제외되는 데이터가 하나씩 늘어나며 n라운드 모두 진행되면 정렬이 완료된다.

버블 정렬 구현

#include <iostream>

using namespace std;

int arr[10] = {1, 4, 2, 6, 5, 9, 10, 5, 3, 7};

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(NULL);

    for(int i=0; i<10; i++) // 10개의 원소이므로 10라운드 진행

    {

        for(int j=0; j<9-i; j++) // 라운드가 진행될수록 데이터가 1개씩 줄어드므로 9-i

        {

            if(arr[j] > arr[j+1]) // 순서가 잘못되었다면 정렬

            {

                int temp = arr[j];

                arr[j] = arr[j+1];

                arr[j+1] = temp;

            }

        }

    }

    for(int i=0; i<10; i++)

        cout << arr[i];

    return 0;

}

 

시간복잡도

시간 복잡도의 경우 버블정렬은 비교를 무조건 진행하기에 

(n-1) + (n-2) + (n-3) ... + 2 + 1 = n(n-1)/2 이므로 O(n^2)이다.

또한 2개의 원소 비교를 무조건 진행하기에 최선, 평균, 최악 모두 O(n^2)이다.

공간복잡도

공간 복잡도의 경우 n 길이의 배열을 추가적인 공간 사용없이 그대로 사용하므로 O(n)이다.

 

 

버블 정렬은

매우 간단하고 직관적이며 다른 메모리 공간을 필요로 하지 않는다는 점이 장점이지만

시간 복잡도가 굉장히 비효율적이며 역위의 개수가 최대인 경우 교환연산이 매우 많이 일어나게 된다.