Algorithm - 버블 정렬(bubble sort)

안녕하세요 :-)

이번 포스팅에서 다루어볼 것은 선택정렬과 마찬가지로 시간복잡도 O(N^2)을 갖는 버블정렬 알고리즘입니다.

선택정렬 알고리즘의 경우 가장작은값을 찾아 기억할 변수 min값이 필요했었지만 버블정렬에서는 따로 필요하지 않습니다.

왜냐하면 버블정렬의 아이디어는 바로 원소 자신의 양옆의 인덱스와 비교하여 더 작은값을 앞으로 보내는 것이기 때문입니다.

선택정렬 알고리즘의 경우 조건 검사 범위를 앞에서 부터 제외했었습니다. 제외된 원소들은 이미 정렬이 완료되었다 간주했기 때문입니다. 하지만 버블정렬의 경우 뒤에있는 인덱스를 순서대로 제외하며 정렬을 수행합니다.

정렬 절차

1. 맨앞 인덱스의 원소 부터 자신과 오른쪽의 값을 비교하여 오른쪽이 더 크다면 자신과 위치를 바꿉니다.
2. 배열 전체를 조건검사 했다면 제일 마지막 인덱스를 제외 한후 다시 1번의 절차를 반복합니다.
3. 1,2 번의 절차를 조건검사할 인덱스의 범위가 1이 된다면 정렬 알고리즘이 완료됩니다.

결과

조건검사후 배열의 범위를 한바퀴 돌때마다 제외되는 마지막 인덱스에는 가장 큰 값이 밀려나기 때문에 이 알고리즘 또한 오름차순 정렬이 되는것을 알수 있습니다.

특징

버블 정렬과 선택정렬의 시간복잡도는 O(N^2)으로 서로 동일 합니다. 하지만 실제로 디버깅한다면 선택정렬보다 버블정렬이 느린것을 확인할수 있습니다. 매번 옆자리의 원소와 비교하여 인덱스를 스위칭 해주기 때문에 자리를 바꿔주는 SWAP연산이 선택정렬보다 잦아짐으로 실제 디버깅시 느릴 확률이 더 큽니다.

SWAP 연산이란?

두 원소의 인덱스를 바꿔주는 연산으로 java코드로 표현한다면 아래와 같습니다.

int a = 1;
int b = 2;

//swap 과정
int temp = a;
a=b;
b=temp;

마치며

이번 포스팅에서는 동일한 시간복잡도에서도 실제 디버깅에서는 처리속도가 더딜수 있는 버블정렬 알고리즘에 대하여 공부했습니다. 이번 포스팅 까지 정렬 알고리즘을 배우며 왜 자꾸 시간복잡도도 안좋고 실제 디버깅도 안좋은 알고리즘을 소개하는가? 정렬은 눈에 보이는 결과가 똑같은데 그냥 제일빠른거 하나만 알고 있어도 되지 않겠나? 생각이 들수 있습니다. 하지만 기초가 되고 느린 알고리즘들을 통해 성능이 좋고 빠른 알고리즘이 왜 빠르고 왜 좋은지 알게 될수 있다 생각합니다. 다음 포스팅은 마지막으로 시간복잡도가 O(N^2)인 삽입 정렬 알고리즘에 대해서 알아보겠습니다.