[Algorithm] bubble sorting 이해하기

- 목차

 

* 소개

버블 정렬은 아주 단순한 정렬 알고리즘입니다.

나열된 숫자들을 일일이 비교하는 연산을 수행하는데요.

그래서 시간복잡도는 크지만 직관적으로 이해할 수 있는 정렬 알고리즘입니다.

 

버블 정렬의 정렬 방식에 대해서 간단히 설명해보겠습니다.

무작위로 나열된 숫자들이 있다고 가정합니다.

이 나열된 숫자들 중 첫번째 수와 그 인접한 수를 한데 묶어 크기를 비교합니다.

( 즉, 첫번째 수와 두번째 수를 비교하는 것입니다. )

그리고 정렬 방식에 따라 두 수의 위치를 변경합니다.  (swap)

오름차순인 경우에는 큰 수가 뒤에 위치하고 내림차순읜 경우에는 작은 수가 뒤에 위치합니다.

 

그리고 두번째 수와 그 인접한 수를 비교하고 swap 을 합니다.

그리고 세번째 수와 그 인접한 수를 비교하고 swap 을 합니다.

그리고 네번째 수와 그 인접한 수를 비교하고 swap 을 합니다.

그리고 다섯번째 수와 그 인접한 수를 비교하고 swap 을 합니다.

... ...

 

이러한 Comparision 과 Swap 을 반복하는 것이 bubble sorting 입니다.

 

구체적인 예시를 들어보겠습니다.

 

 

* 예시

예를 들어 1 부터 9 까지의 값들을 무작위로 나열되어 있다고 가정하겠습니다.

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

 

1번째 : 7 과 8을 비교합니다. 8이 7보다 크기 때문에 swap 되지 않습니다.
(7, 8), 9, 3, 6, 1, 4, 2, 5

2번째 : 8과 9를 비교합니다. 9가 8보다 크기 떄문에 swap 되지 않습니다.
7, (8, 9), 3, 6, 1, 4, 2, 5

3번째 : 9와 3을 비교합니다. 9가 3 보다 크기 때문에 swap 됩니다.
7, 8, (9, 3), 6, 1, 4, 2, 5

4번째 : 9와 6을 비교합니다. 9가 6 보다 크기 때문에 swap 됩니다.
7, 8, 3, (9, 6), 1, 4, 2, 5

5번째 : 9와 1을 비교합니다. 9가 1 보다 크기 때문에 swap 됩니다. 
7, 8, 3, 6, (9, 1), 4, 2, 5

6번째 : 9와 4을 비교합니다. 9가 4 보다 크기 때문에 swap 됩니다. 
7, 8, 3, 6, 1, (9, 4), 2, 5

7번째 : 9와 2을 비교합니다. 9가 2 보다 크기 때문에 swap 됩니다. 
7, 8, 3, 6, 1, 4, (9, 2), 5

8번째 : 9와 5을 비교합니다. 9가 5 보다 크기 때문에 swap 됩니다. 
7, 8, 3, 6, 1, 4, 2, (9, 5)

9번째 : 9가 제일 마지막 index 에 위치하게 됩니다.
7, 8, 3, 6, 1, 4, 2, 5, (9)

 

첫번째 cycle 에서 가장 큰 수인 9 가 맨 마지막 위치에 놓이게 됩니다.

이러한 방식을 나열된 숫자의 갯수만큼 반복하면 모든 값들이 정렬되게 됩니다.

 

그리고 가장 큰 수 또는 작은 수가 맨 마지막 위치로 이동하는 이러한 모습이

수면 위로 올라가는 물방울과 닮았다고 하여 bubble sort 라고 불리게 되었습니다.

시작한 김에 두번쨰 사이클도 설명해보겠습니다.

첫번째 사이클에서 정렬된 결과는

 

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

입니다.

 

1번째 : 7 과 8을 비교합니다. 7이 8보다 크기 때문에 swap 되지 않습니다.
(7, 8), 3, 6, 1, 4, 2, 5, 9

2번째 : 8과 3를 비교합니다. 8 이 3보다 크기 떄문에 swap 됩니다.

7, (8, 3), 6, 1, 4, 2, 5, 9

3번째 : 8와 6을 비교합니다. 8 이 6 보다 크기 때문에 swap 됩니다.

7, 3, (8, 6), 1, 4, 2, 5, 9

4번째 : 8와 1을 비교합니다. 8 이 1 보다 크기 때문에 swap 됩니다.

7, 3, 6, (8, 1), 4, 2, 5, 9

5번째 : 8와 4을 비교합니다. 8 이 4 보다 크기 때문에 swap 됩니다.

7, 3, 6, 1, (8, 4), 2, 5, 9

6번째 : 8와 2을 비교합니다. 8 이 2 보다 크기 때문에 swap 됩니다. 
7, 3, 6, 1, 4, (8, 2), 5, 9

7번째 : 8와 5을 비교합니다. 8 이 5 보다 크기 때문에 swap 됩니다. 
7, 3, 6, 1, 4, 2, (8, 5), 9

8번째 : 8와 9을 비교합니다. 8 이 9 보다 작기 때문에 swap 되지 않습니다.
7, 3, 6, 1, 4, 2, 5, (8, 9)

두번째로 큰 8 이 마지막에서 두번째에 위치하게 됩니다.

 

 

* 코드

 

<Python Code by chat GPT>

def bubble_sort(arr):
    n = len(arr)

    # Traverse through all elements in the array
    for i in range(n):
        # Flag to optimize the algorithm by checking if any swaps are made in a pass
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n - i - 1):
            # If the element found is greater than the next element, swap them
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        # If no two elements were swapped in the inner loop, the array is already sorted
        if not swapped:
            break

 

<Javascript Code by chat GPT>

function bubbleSort(arr) {
    const n = arr.length;
    let swapped;

    do {
        swapped = false;
        for (let i = 0; i < n - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                // Swap arr[i] and arr[i+1]
                const temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                swapped = true;
            }
        }
    } while (swapped);

    return arr;
}

 

 

<Java Code by chat GPT>

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;

        do {
            swapped = false;
            for (int i = 0; i < n - 1; i++) {
                if (arr[i] > arr[i + 1]) {
                    // Swap arr[i] and arr[i+1]
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    swapped = true;
                }
            }
        } while (swapped);
    }
}

 

 

<Go Code by chat GPT>

package main

import "fmt"

func bubbleSort(arr []int) {
    n := len(arr)
    swapped := true

    for swapped {
        swapped = false
        for i := 0; i < n-1; i++ {
            if arr[i] > arr[i+1] {
                // Swap arr[i] and arr[i+1]
                arr[i], arr[i+1] = arr[i+1], arr[i]
                swapped = true
            }
        }
    }
}