알고리즘 - Bubble Sort 개념 (버블 소트)

Bubble Sort(버블 정렬)이란 많은 숫자들을 정렬할 때 사용하는 알고리즘들 중의 하나이다.

 

 

 

결론부터 말하자면 왼쪽에 가장 작은 수를 두고 오른쪽으로 갈 수록 큰 수들이 정렬되어 있는 구조로 오른쪽 가장 끝에는 가장 큰 수가, 왼쪽 가장 끝에는 가장 작은 수가 정렬되게 끔 만드는 방식이다.

쉽게 말하면 숫자를 크기순으로 나열한 것이다.

 

 

 

 

 

 

EX-1)

5 9 3 1 2 8 4 7 6

                      |  |

                   (일명 저울)

 

 

무작위로 정렬된 일렬의 데이터에서 두개를 가리키는 눈금이 오른쪽 끝에서 왼쪽의 1개 오른쪽의 1개를 저울처럼 가리키며 비교를 하는 알고리즘이다.

그래서 비교한 결과, 오른쪽의 숫자가 더 작은 것으로 확인되면, 그 숫자가 바뀌게 된다.

 

이 경우 7과 6을 비교하게 될 겁니다.

오른쪽에 있는 숫자는 6으로 왼쪽보다 작으므로 두개의 숫자는 바뀌게 된다.

 

EX-2)

5 9 3 1 2 8 4 6 7

                   |  |

 

숫자가 바뀌고 비교가 끝나면 저울은 왼쪽으로 한칸 이동하게 된다.

 

그 숫자들을 다시 한 번 비교한다.

이동이 완료되면 다시 숫자를 비교하게 된다.

 

이번에는 오른쪽에 있는 6이 4보다 커서 숫자가 바뀌지 않는다.

그렇게되면 숫자의 위치는 변함이 없고 저울만 왼쪽으로 옮겨지게된다.

 

EX-3)

5 9 3 1 2 8 4 6 7

               |  |

 

 

이 작업은 저울이 왼쪽 끝에 도달할 때까지 반복이 된다.

 

 

EX-4)

Before

5 9 3 1 2 8 4 7 6

                      |  |

 

After

1 5 9 3 2 4 8 6 7

|  |

 

당연히 한바퀴 순회하면서 가장 작은 수였던 1은 비교될때마다 왼쪽으로 이동하여 가장 왼쪽에 자리잡게 되었고, 2는 초기에 1보다 오른쪽에 있었기 때문에 움직임에 변화가 없었던 것이다.

그러한 이유로 부분적인 움직임이 있었고 처음 한바퀴 돌았을 때 가장 작은 수가 왼쪽에 정렬된 다는 것만 기억하면 될 것 같다.

 

그리고 좀 더 생각을 나아가보면 다음 한바퀴를 돌때 우리는 숫자 2가 1 옆으로 가게 될 것이라는 것을 예측해 볼 수 있을 것이다.

 

저울이 왼쪽 끝에 다달으면 다시 오른쪽으로 이동을 하게된다.

 

EX-5)

1 5 9 3 2 4 8 6 7

                      |  |

 

모든 숫자가 완전히 정렬될 때까지 동일한 작업이 반복됨

그리고 모든 숫자가 완전하게 정렬될 때 까지 1 ~ 4번과정을 반복하게 된다.

그렇게되면 저울의 반복 횟수의 최대값은 데이터 개수가 될 것이고 최소값은 당연히 1이될 것이다.

 

그렇게 모든 숫자의 정렬이 완료되면 Sort작업은 끝이 난다.

 

EX-6, Complete)

1 2 3 4 5 6 7 8 9

 

그리고 이러한 방법을 Bubble sort(버블 솔트)라고 부른다.

 

 

다음 포스팅 때는 버블솔트를 C언어로 구현해 볼 것이다.