C++ 버블정렬 - 정렬2

두번째로 가장 간단한 정렬 알고리즘이다

 

아이디어는

1. 바로 옆의 값과 비교하여 큰값을 오른쪽으로 보낸다

2. 옆으로 한칸 이동하여 배열 끝까지 반복한다

3. 끝까지 반복하면 가장 큰 수가 가장 오른쪽에 위치하게 된다

1~3까지가 1회전

4. 배열의 개수만큼 회전한다

 

int* BubbleSort(int* arr, int size){

    for(int i=0; i < size; i++){
        for(int j=0; j < size-i-1; j++){// size - i를 해주는 이유는 size - i ~ 부터는
            if(arr[j] > arr[j+1]){	// 이미 정렬이 되어 있기 때문이다 && 추가적으로 -1을 해주는 이유는
                			// 원소들을 비교할때 j+1을 하기 때문이다.
                int temp = arr[j];	
                arr[j] = arr[j+1];	//왼쪽 원소가 더 클 경우 두 원소의 자리를 바꾼다
                arr[j+1] = temp;
            }
        }
    }

    return arr;
}

시간 복잡도는

O(n * (n+1) / 2) 이므로 

O(n²)의 시간복잡도를 갖는다.

 

선택정렬과 같은 시간복잡도지만 디테일하게 생각한다면 선택정렬보다 느린 알고리즘이다.

선택정렬같은 경우 최소값을 찾아서 마지막에 한번 스와핑을 해주지만,

버블정렬의 경우 계속해서 스와핑을 해야 하므로 선택정렬보다 느릴 수 밖에 없다.

 

하지만 만약 한 회전을 할때 스왑이 없었다면 정렬이 되었다는것을 알 수 있는데

#include <iostream>

using namespace std;
int* BubbleSort(int* arr, int size){
    int cnt = 0;

    for(int i=0; i < size; i++){
        cnt = 0;	//스왑 횟수를 저장하는 배열을 선언
        for(int j=0; j < size-i-1; j++){
            if(arr[j] > arr[j+1]){
                cnt++;	//스왑할때마다 +1
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        if(cnt == 0){	//만약 스왑이 없었다면 정렬이 되었음으로 바로 리턴을 해준다
            return arr;
        }
    }

    return arr;
}

이를 이용한다면 정렬이 이미 정렬이 되어있는 배열 즉 최선의 경우

O(n)의 시간복잡도를 갖게 되고

또한 거의 정렬된 배열을 처리하는데 선택 정렬보다 효율적으로 처리할 수 있게 된다.

 

하지만 최악의 경우(배열의 요소가 모두 내림차순일경우) 동일하게 O(n²)의 시간복잡도를 갖는다

사실 별 상관 없다