버블정렬 알고리즘(BubleSort) 과정 및 설명

저번 포스팅엔 다차원 배열과 for문에 대해 배워보았습니다.

이번엔 배열을 이용해서 버블정렬 알고리즘(BubleSort) 을 알아보도록 하겠습니다.

 

간단하게 버블정렬에 대해서 알아보도록 하겠습니다.

 

버블정렬이란 첫번째 값과 두번째 값, 두번째와 세번째 값, 세번째와 네번째 값 ...

이런식으로 (마지막 - 1)번째 값과 마지막 자료를 비교하여 교환하면서 정렬하는 것을 말합니다.

인접한 두 값을 검사하여 정렬하는 알고리즘입니다.

1회전시 제일 마지막에 가장 큰 수가 위치하며 2회전할때 마지막 값은 정렬에서 제외가 됩니다.

2회전시 마지막에서 두번째 값이 정렬에서 제외가 됩니다.

버블 정렬은 다른 정렬 알고리즘에 비해 속도가 느립니다.

일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않습니다.

 

사실 글로만 봐서는 이해가 잘 되지는 않을겁니다.

조금 긴 숫자를 가지고 예시를 들어보도록 하겠습니다.

 

저희는 1, 3, 4, 4, 2, 1, 3, 8, 4, 3 숫자를 한번 버블정렬을 해보도록 하겠습니다.

스크롤의 길이가 길어지는점 양해 부탁드리겠습니다.

1

3

4

4

2

1

3

8

4

3

---

1회전 과정

index를 앞에서부터 0~9 라고 생각하고 이해를 위한 몇번 인덱스끼리 비교하는지를 적어두겠습니다.index라고 적히지 않는 숫자는 표에 있는 숫자입니다.빨간 숫자 = 이번에 정렬된 숫자

파란 숫자 = 다음에 비교될 숫자 ( 마지막 빨간 숫자와 파란숫자 비교)

초록 숫자 = 회전 종료 후 비교대상 아닌 숫자 

 

1, 3 비교 및 정렬 결과

위의 표에서

index(0, 1) 비교 후 결과값

1

3

4

4

2

1

3

8

4

3

3, 4 비교 및 정렬 결과

위의 표에서

index(1, 2) 비교 후 결과값

1

3

4

4

2

1

3

8

4

3

4, 4 비교 및 정렬 결과

위의 표에서

index(2, 3) 비교 후 결과값

1

3

4

4

2

1

3

8

4

3

4, 2 비교 및 정렬 결과

위의 표에서

index(3, 4) 비교 후 결과값

1

3

4

2

4

1

3

8

4

3

4, 1 비교 및 정렬 결과

위의 표에서

index(4, 5) 비교 후 결과값

1

3

4

2

1

4

3

8

4

3

4, 3 비교 정렬 결과

위의 표에서

index(5, 6) 비교 후 결과값

1

3

4

2

1

3

4

8

4

3

4, 8 비교 및 정렬 결과

위의 표에서

index(6, 7) 비교 후 결과값

1

3

4

2

1

3

4

8

4

3

8, 4 비교 및 정렬 결과

위의 표에서

index(7, 8) 비교 후 결과값

1

3

4

2

1

3

4

4

8

3

8, 3 비교 및 정렬 결과

위의 표에서

index(8, 9) 비교 후 결과값

1

3

4

2

1

3

4

4

3

8

1회전 종료.

1

3

4

2

1

3

4

4

3

8

---

2회전 과정

index를 앞에서부터 0~9 라고 생각하고 이해를 위한 몇번 인덱스끼리 비교하는지를 적어두겠습니다.

index라고 적히지 않는 숫자는 표에 있는 숫자입니다.

빨간 숫자 = 이번에 정렬된 숫자

파란 숫자 = 다음에 비교될 숫자 ( 마지막 빨간 숫자와 파란숫자 비교)

초록 숫자 = 회전 종료 후 비교대상 아닌 숫자 

 

1회전이 완료된 값을 가지고 2회전을 시작한다.

1

3

4

2

1

3

4

4

3

8

1, 3 비교 및 정렬 결과

위의 표에서

index(0, 1) 비교 후 결과값

1

3

4

2

1

3

4

4

3

8

3, 4 비교 및 정렬 결과

위의 표에서

index(1, 2) 비교 후 결과값

1

3

4

2

1

3

4

4

3

8

4, 2 비교 및 정렬 결과

위의 표에서

index(2, 3) 비교 후 결과값

1

3

2

4

1

3

4

4

3

8

4, 1 비교 및 정렬 결과

위의 표에서

index(3, 4) 비교 후 결과값

1

3

2

1

4

3

4

4

3

8

4, 3 비교 및 정렬 결과

위의 표에서

index(4, 5) 비교 후 결과값

1

3

2

1

3

4

4

4

3

8

4, 4 비교 및 정렬 결과

위의 표에서

index(5, 6) 비교 후 결과값

1

3

2

1

3

4

4

4

3

8

4, 4 비교 및 정렬 결과

위의 표에서

index(6, 7) 비교 후 결과값

1

3

2

1

3

4

4

4

3

8

4, 3 비교 및 정렬 결과

위의 표에서

index(7, 8) 비교 후 결과값

1

3

2

1

3

4

4

3

4

8

2회전 종료.

1

3

2

1

3

4

4

3

4

8

---

3회전 과정

index를 앞에서부터 0~9 라고 생각하고 이해를 위한 몇번 인덱스끼리 비교하는지를 적어두겠습니다.

index라고 적히지 않는 숫자는 표에 있는 숫자입니다.

빨간 숫자 = 이번에 정렬된 숫자

파란 숫자 = 다음에 비교될 숫자 ( 마지막 빨간 숫자와 파란숫자 비교)

초록 숫자 = 회전 종료 후 비교대상 아닌 숫자 

2회전이 완료된 값을 가지고 3회전을 시작한다.

1

3

2

1

3

4

4

3

4

8

1, 3 비교 및 정렬 결과

위의 표에서

index(0, 1) 비교 후 결과값

1

3

2

1

3

4

4

3

4

8

3, 2 비교 및 정렬 결과

위의 표에서

index(1, 2) 비교 후 결과값

1

2

3

1

3

4

4

3

4

8

3, 1 비교 및 정렬 결과

위의 표에서

index(2, 3) 비교 후 결과값

1

2

1

3

3

4

4

3

4

8

3, 3 비교 및 정렬 결과

위의 표에서

index(3, 4) 비교 후 결과값

1

2

1

3

3

4

4

3

4

8

3, 4 비교 및 정렬 결과

위의 표에서

index(4, 5) 비교 후 결과값

1

2

1

3

3

4

4

3

4

8

4, 4 비교 및 정렬 결과

위의 표에서

index(5, 6) 비교 후 결과값

1

2

1

3

3

4

4

3

4

8

4, 3 비교 및 정렬 결과

위의 표에서

index(6, 7) 비교 후 결과값

1

2

1

3

3

4

3

4

4

8

3회전 종료.

1

2

1

3

3

4

3

4

4

8

---

4회전 과정

index를 앞에서부터 0~9 라고 생각하고 이해를 위한 몇번 인덱스끼리 비교하는지를 적어두겠습니다.

index라고 적히지 않는 숫자는 표에 있는 숫자입니다.

빨간 숫자 = 이번에 정렬된 숫자

파란 숫자 = 다음에 비교될 숫자 ( 마지막 빨간 숫자와 파란숫자 비교)

초록 숫자 = 회전 종료 후 비교대상 아닌 숫자 

 

2회전이 완료된 값을 가지고 3회전을 시작한다.

1

2

1

3

3

4

3

4

4

8

 

1, 2 비교 및 정렬 결과

위의 표에서

index(0, 1) 비교 후 결과값

1

2

1

3

3

4

3

4

4

8

1, 2 비교 및 정렬 결과

위의 표에서

index(1, 2) 비교 후 결과값

1

1

2

3

3

4

3

4

4

8

2, 3 비교 및 정렬 결과

위의 표에서

index(2, 3) 비교 후 결과값

1

1

2

3

3

4

3

4

4

8

3, 3 비교 및 정렬 결과

위의 표에서

index(3, 4) 비교 후 결과값

1

1

2

3

3

4

3

4

4

8

3, 4 비교 및 정렬 결과

위의 표에서

index(4, 5) 비교 후 결과값

1

1

2

3

3

4

3

4

4

8

4, 3 비교 및 정렬 결과

위의 표에서

index(5, 6) 비교 후 결과값

1

1

2

3

3

3

4

4

4

8

4회전 종료.

 

1

1

2

3

3

3

4

4

4

8

---

5회전 후 결과 /과정 생략. 정렬될 결과 없음.

1

1

2

3

3

3

4

4

4

8

6회전 후 결과 /과정 생략.정렬될 결과 없음.

1

1

2

3

3

3

4

4

4

8

7회전 후 결과 /과정 생략.정렬될 결과 없음.

1

1

2

3

3

3

4

4

4

8

8회전 후 결과 /과정 생략.정렬될 결과 없음.

1

1

2

3

3

3

4

4

4

8

9회전 후 결과 /과정 생략.정렬될 결과 없음.

1

1

2

3

3

3

4

4

4

8

정렬 완료

 

최종 버블정렬 값 

1, 1, 2, 3, 3, 3, 4, 4, 4, 8

 

이로써 버블정렬의 과정을 알아보았습니다.

다음 포스팅에선 랜덤 숫자를 이용해 배열을 버블정렬하는 방법을 알아보도록 하겠습니다.