[허언증/Algorithm] 버블정렬(Bubble Sort)

안녕하세요! 허언증입니다.

버블정렬에 대해 공부 하도록 하겠습니다.

 

---

 

 

버블정렬(Bubble Sort)? 

 

옆에 있는 값과 비교 후 작은 값을 앞으로 보내면 어떨까?

 

생각에서 만들어지게 된 알고리즘 입니다.

곧 바로 예시로 한 번 알아보도록 하겠습니다.

 

 

 

1, 5, 3, 10, 4, 7, 9, 2, 6, 8

(정렬되지 않은 숫자 1~10까지의 나열 된 상태입니다)

버블정렬의 방식으로 나열을 시작하면

 

 

첫 번째 자리에 있는 1을 기준으로 2번 자리 값과 비교를 하고 

작은 수와 자리를 바꿔줍니다.

1은 이미 제일 작은 수 이기도 하고 첫 번째자리에 있으니 변화가 없습니다.

 

 

이제는 두 번째 자리와 세 번째 자리와 비교를 합니다.

1, 5, 3, 10, 4, 7, 9, 2, 6, 8

두 번째자리인 5 와 세 번째 자리를 비교를 하면 3이

더 작은 수이기 때문에 교환이 일어납니다.

1, 3, 5, 10, 4, 7, 9, 2, 6, 8

 

 

세 번째자리 수와 네 번째 자리수를 비교를 합니다.

5,10을 비교하면  5가 작으니 그대로 가고 다음 단계인

 

네 번째 자리수와 다섯 번째 자리수인

10,4을 비교를 하면 4가 더 작기 때문에 교환이 일어납니다.

1, 3, 5, 4, 10, 7, 9, 2, 6, 8

 

이렇게 첫 번째자리 기준으로 교환이 다 일어나면 

그 다음엔 두번째 기준으로 교환을 합니다.

 

첫 번째가 끝난 지금은 

1, 3, 5, 4,

순이지만 두 번째 기준 / 세 번째기준 / 네 번째 기준으로 

계속 하다보면 결국 

1~10 순으로 나열이 되는걸 알 수 있습니다.

 

 

*첫번째를 먼저 시작해서 끝 번호까지 다 정렬하고

두번째 기준을 시작해서 끝 번호까지 다 정렬

...

...

...

결국 마지막에 다 정렬이 된다

 

 

 

 

---

 

이러한 과정을 소스코드로 작성하면

 

선택정렬과 버블정렬 중 더 빠른 정렬은?

 

위와 같이 만들 수 있습니다. (C언어로 작성)

 

 

 

i,j = for문 인자

temp = 서로 자리를 바꿀때 임시로 저장하는 변수

 

 

 

---

 

 

선택정렬의 시간 복잡도는

 

O(N^2)

 

 

 

 

 

 

 

* 참고 게시글 *

 

시간 복잡도 & 빅오표기법 - 시간복잡도&빅오표기법 공부하러 가자! Click!! Click!!

 

 

 

* 다른 알고리즘 *

선택 알고리즘(Selection Sort) -  선택 알고리즘(Selection Sort) 공부하러 가자! Click!! Click!!