정렬 / 버블 정렬 / 옆에 있는 값과 비교하여 더 작은 값을 반복적으로 앞으로 보내는 정렬

이 글에서는 선택 정렬과 마찬가지로 몹시 직관적인 버블 정렬(Bubble Sort)에 대해서 알아보겠습니다.  

버블 정렬(Bubble Sort)

 

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

1 10 5 8 7 6 4 3 2 9

 

1 10 5 8 7 6 4 3 2 9

1 5 10 8 7 6 4 3 2 9

1 5 8 10 7 6 4 3 2 9

1 5 8 7 10 6 4 3 2 9

1 5 8 7 6 10 4 3 2 9

1 5 8 7 6 4 10 3 2 9

1 5 8 7 6 4 3 10 2 9

1 5 8 7 6 4 3 2 10 9

1 5 8 7 6 4 3 2 9 10

 

... 위와 같은 방식으로 1차 버블 정렬을 끝나면 가장 큰 수가 가장 뒤로 가게됩니다.

즉 가장 큰 수의 정렬이 확정되고, 이후 이를 제외한 나머지 배열에서 다음 버블 정렬을 수행합니다.

 

1 5 8 7 6 4 3 2 9 10

1 5 8 7 6 4 3 2 9 10

1 5 7 8 6 4 3 2 9 10

1 5 7 6 8 4 3 2 9 10

1 5 7 6 4 8 3 2 9 10

1 5 7 6 4 3 8 2 9 10

1 5 7 6 4 3 2 8 9 10

1 5 7 6 4 3 2 8 9 10

1 5 7 6 4 3 2 8 9 10

 

시간 복잡도

비교 횟수
최상, 평균, 최악 모두 일정
n-1, n-2, … , 2, 1 번 = n(n-1)/2
교환 횟수
입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 * 3) 번 = 3n(n-1)/2
입력 자료가 이미 정렬되어 있는 최상의 경우, 자료의 이동이 발생하지 않는다.
T(n) = O(n^2)

공간 복잡도

 

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 

특징

장점

• 알고리즘이 단순하다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. -> 제자리 정렬(in-place sorting)
• 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.

단점

• 평균과 최악의 시간복잡도가 O(n^2)으로 비효율적이다.
• 불안정 정렬(Unstable Sort) 이다.

문제 풀이 오답

https://www.acmicpc.net/problem/1838

1838번: 버블 정렬

 

[내가 푼 풀이]

n = input()
n = int(n)

a = input().split()

for i in range(n):
    a[i] = int(a[i])

for i in range(n):
    flag = 0
    for j in range(n-1):
        if a[j] > a[j+1]:
            flag = 1
            temp = a[j]
            a[j] = a[j+1]
            a[j+1] = temp
    if flag == 0 :
        index = i
        break  
                  
print(index)

[결과]

시간 초과

-> 버블 정렬 문제길래 버블 정렬로 풀었는데 왜? 라는 생각이 들었지만.. 알고보니 문제에서 준 코드를 계산하는 효율적인 방법을 요구하는 문제였던 것 .. ^^

 

[올바른 문제 풀이]

문제에서 i가 의미 하는 것을 생각 할 필요가 있다.

 

i는 모두 정렬이 완료 되었을 시점에, 지금까지 몇번 정렬이 이루어 졌는지를 나타내는 수이다. (해당 말이 이해가 되지 않는다면 이중 for 문 중, 가장 외곽의 값이기 때문이라고 생각해도 좋다.)

 

다시 한번 버블 정렬이란,

0번 인덱스부터 N-2번 인덱스까지 진행하면서 arr[i] 와 arr[i+1]을 비교하여 swap 하는 정렬이다.

위와 같은 과정을 최대 N번 반복하면 정렬된 배열을 얻을 수 있다.

 

인접한 두 원소를 검사하여 정렬하고 각 차수 마다 버블 정렬이 끝나면 가장 큰 값이 뒤로 이동하게된다.

즉 i는 뒤로 이동 한 값 중 가장 많이 이동한 거리인 것이므로 정렬 전과 후의 index 차이가 가장 큰 값을 찾으면 된다.

 

아래의 글을 참고하여 작성하였습니다.

 

https://minzzl.tistory.com/4

정렬 / 선택 정렬 / 가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘

https://bcp0109.tistory.com/48

백준 1838번. 버블 정렬 (Java)