(구)boymin
정렬 알고리즘 - 버블 정렬(Bubble Sort) 본문
정렬 알고리즘은 주어진 데이터를 정해진 순서대로 나열하는 방법이고,
버블 정렬(Bubble Sort)는 정렬 알고리즘의 대표적인 방법 중 하나이다.
버블 정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다.
시간복잡도는 O(n^2)로 느린편이나 코드가 단순하여 자주 사용된다.
예시를 들어보자면, 다음 5개의 숫자가 있다고 가정하자.
5 4 1 3 2
먼저 앞 2개의 원소 5와 4를 비교한다. 4가 더 작으므로 두 수의 위치를 바꾼다.
5 4 1 3 2
-> 4 5 1 3 2
그리곤 5와 1로 넘어간다. 역시 1이 더 작으므로 두 수의 위치를 바꾼다.
4 5 1 3 2
-> 4 1 5 3 2
5와 3을 비교한다. 3이 더 작으므로 두 수의 위치를 바꾼다.
4 1 5 3 2
-> 4 1 3 5 2
5와 2를 비교한다. 2가 더 작으므로 두 수의 위치를 바꾼다.
4 1 3 5 2
-> 4 1 3 2 5
이렇게 한번을 돌았다.
모든 원소가 정렬이 될 때까지 이를 반복한다.
...하지만 조금만 생각해보면, 매 정렬시마다 가장 큰 수가 정렬이 된다는 것을 알 수 있다.
즉, n개의 인자를 정렬하면,
첫 번째에는 (크기순으로) n번째 원소가 정렬된다.
두 번째에는 n-1번째 원소가 정렬된다.
세 번째에는 n-2번째 원소가 정렬된다.
.
.
.
n-2 번째에는 3번째 원소가 정렬된다.
그리고 n-1번째에서는 2번째 원소가 정렬되며, 동시에 가장 작은 원소 역시 정렬된다.
즉 n개의 원소를 버블 정렬로 정렬하면, 아무리 많이 돌아도 최대 n-1번 돈다는 것과,
매번 정렬 시 정렬되지 않은 인자 중 가장 큰 인자가 정렬이 된다는 것을 알 수 있다.
이를 통해 간단히 코드로 버블 정렬을 만들어 보았다.
허나 이 코드에는 문제점이 있다.
무심코 넘어갈 수 있는 사소한 부분이지만 결코 사소하지 않다.
바로, 주어진 원소가 어떻게 배열되어있는지 관계없이 항상 최악의 방법, 즉 최대의 횟수를 돌린다는 점이다.
다시말해, 원소가 1 2 3 4 5로 주어지나 5 4 3 2 1로 주어지나 정렬을 똑같이 4번 돌리는 문제점이 있다.
이부분을 막기 위해 bool인자를 사용하여 다시 코드를 짜보았다.