버블 정렬 (bubble sort)

버블 정렬 (bubble sort)

• 인접한 두 개의 데이터를 비교한 후에 앞의 데이터가 뒤의 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘

출처: https://visualgo.net/en/sorting

알고리즘 생각해보기

• 인접한 두 개의 데이터를 비교하는 반복 횟수 -> len(data) - 1
• 앞의 데이터가 뒤의 데이터보다 크면 swap
• 한 바퀴 돌면 최댓값이 끝으로 이동하므로 다음 반복 횟수는 위 횟수의 -1 (끝값을 배제)
• 이 반복을 len(data) - 1 만큼 반복 (첫 번째 값만 남아 비교할 대상이 없을 때까지 = 끝값을 배제한 횟수)
• 처음부터 정렬된 데이터가 주어질 수 있으므로 swap_check 란 boolean 형 변수를 두어 swap 이 한번이라도 발생했는지 체크

알고리즘 구현

파이썬 코드 구현

import random

def bubblesort(data):
    for index in range(len(data) - 1):
        swap_check = False
        for index2 in range(len(data) - index - 1):
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap_check = True
        
        if swap_check == False:
            break
    return data

data_list = random.sample(range(100), 50)
print (bubblesort(data_list))

자바 코드 구현

import java.util.Arrays;

public class BubbleSort {

    static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    static void bubbleSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            boolean swapCheck = true;
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    swap(a, j, j + 1);
                    swapCheck = false;
                }
            }
            if (swapCheck) break;
        }
    }

    public static void main(String[] args) {
        int[] a = {17, 14, 11, 19, 13, 15, 20, 12, 16, 18};

        bubbleSort(a);
        System.out.println(Arrays.toString(a));
    }

}

수행 시간 분석

• 반복문이 두 개 O($n^2$)
  • 최악의 경우, $\frac { n * (n - 1)}{ 2 }$
• 완전 정렬이 되어 있는 상태라면 최선은 O(n)