[알고리즘] 버블 정렬(Bubble Sort)에 대해 알아보자

저별이 2022. 4. 29. 18:00

2022. 4. 29. 18:00

728x90

버블정렬이란?

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘을 의미한다.

버블정렬의 진행과정

5개 배열이 있다고 가정해보자

랜덤 숫자를 넣어보았다.

1. 첫번째 원소인 4와 두번째 원소 9를 비교해보자

오른쪽에 있는 숫자가 크다. 그럼 교환이 일어나지 않는다.

2. 두번째 원소인 9와 세번째 원소인 1을 비교해보자.

오른쪽 숫자가 더 크다.

배열 순서를 바꿔준다.

3. 두번 봤으니 이제는 약간의 감을 잡을 수도 있을것 같다.

9와 3을 비교해준다.

이번에도 교환이 필요한 상태다.

제일 큰 수가 이제 4번째까지 왔다.

4. 9를 위한 처리가 한번 남았다.

9와 5를 비교해준다.

이제 배열에서 가장 큰수가 뒤에 놓였다.

5. 그럼 이제 두번째 큰수를 처리하기 위해 다시 처음부터 시작한다. 이 사례에서는 4번째에 이미 두번째 큰 수가 놓였다.

6. 세번째 큰수인 4는 3번의 교환여부를 확인하고 2번의 교환으로 4는 3번째의 위치에 자리하게 된다.

7. 다음으로는 1부터 비교해야 하지만 이미 1과 3이 다 차례대로 정렬이 되어있기 때문에 이 케이스에서는 교환이 필요없다.

버블정렬 구현 코드(C)

이제 방법을 알았으니 코드로는 어떻게 해야 할지 의문이 들 것이다. 코드를 한번 살펴보자.

#include <stdio.h>

int main(){
	int n=5;
    int list={4,9,1,3,5};
    
    for(int i=0;i<n;i++){
    	for(int j=0;j<n-(i+1);j++){
        	if(list[j]>list[j+1]{
            	int temp=list[j+1];
                list[j+1]=list[j];
                list[j]=temp;
            }
        }
    }
}

C언어로 구현해보면 이렇게 이중 for문과 그 안에서 if문으로 앞 뒤 배열을 확인한 뒤에 비교를 해주는 코드를 넣어주면 된다. 반복은 변수를 설정해서 그만큼 돌도록 했는데 안쪽 for문이 특이할 것이다.

n-(i+1)을 하게 된 이유를 알아보자면

처음할 때는 배열크기-1만큼 교환 비교가 일어나는 것을 볼 수 있을 것이다.

그러면 5-1=4 총 4번 돌게된다

다음 비교는 1번 줄어야 하는데 5-(1+1)=3이므로 3번 돌게 된다.

for문 안에서 j의 최댓값이 줄면서 반복 해주면 정렬이 되게 된다.

버블 정렬 코드(Python)

l=[4,9,1,3,5]
for i in range(len(l)-1,0,-1):
    for j in range(i):
        if l[j]>l[j+1]:
            l[j], l[j+1]=l[j+1], l[j]
print(l)

파이썬으로도 구현해보았다.

C언어에 비해 정말 간단하다.

리스트 안에 값을 넣어주고 마찬가지로 for 이중문과 if문으로 값 비교를 해주었다. 여기서는 반복횟수가 줄어드는 과정을 len(l)-1로 만들어주었다. 바깥 for문에서 몇번 돌지 정해주면 안쪽 for문에서 그만큼 돌려주는 것이다.

바꿔주는 것은 파이썬 문법에서도 볼 수 있듯이 ,로 구분해주어 순서만 바꿔주면 값이 교환되어 들어가므로 쉽게 구현이 가능하다.

버블정렬 정리 그리고 결론: 시간복잡도는??

버블 정렬은 하나하나 모두 비교하고 뒤에서부터 차례대로 채워나가는 형태다. 그래서 매우 시간이 오래 걸릴 수 밖에 없다. 시간복잡도로 나타내면 O(N*N)이 되게 된다. 삽입정렬과 같은 복잡도이지만 연산수가 가장 많아 아 가장 느리고 효율성이 떨어지기 때문에 실제로는 많이 쓰이지는 않는다.