[Java+Python]버블 정렬(Bubble Sort)

<Java + Python>으로 구현한 다른 정렬:

 

[Java+Python]삽입 정렬(Insert Sort)

[Java+Python]선택 정렬(Selection Sort)

[Java+Python]병합 정렬(Merge Sort)

[Java+Python]힙 정렬(Heap Sort)

[Java+Python]퀵 정렬(Quick Sort)

[Java+Python]카운팅 정렬(Counting Sort)

 

버블 정렬(Bubble Sort)은 간단히 말하면 처음부터 시작해 인접한 원소와 비교해 자리를 바꾸는 알고리즘이다.

 

한 바퀴 돌 때마다 원소 하나가 확실히 정렬되기 때문에, 거품이 떠오르는 것 같다고 해서 붙은 이름이기도 하다.

 

선택 정렬, 삽입 정렬과 함께 최악의 효율을 보여주며, 그 와중에도 삽입 정렬보다 느리다.

 

최선의 상황(정렬이 끝난)에선 최고의 효율을 보여주긴 하지만, 어지간해선 사용되지 않는 알고리즘이라고 한다.

 

대신 구현이 편하다고.

 

작동 방식과 구현을 살펴보자.

 

Algotirhm

 

위에 적은 것과 같이 순서대로 원소를 비교하며 자리를 정하고,

 

한 바퀴 돌 때마다 적어도 하나의 원소의 자리가 정해지는 것을 확인할 수 있다.

 

어떻게 보면 삽입정렬보다 직관적인 것 같기도 하다.

 

Implementation

 

역시 구현은 간단한 편이다.

 

배열 길이보다 하나 적은 횟수를 순회하며

 

원소를 순서대로 비교해 자리를 바꾼다.

 

import java.util.Arrays;

public class BubbleSort {

    public static void main(String[] args) {

        int[] arr = {4, 16, 31, 5, 4, 17, 1, 10, 15, 3, 16, 6, 7, 2, 2, 1, 5, 13, 17, 14, 4, 0};

       bubbleSortImpl(arr);

        System.out.println(Arrays.toString(arr));
    }

    public static void bubbleSortImpl(int[] arr) {

        for (int i = 1; i < arr.length; i++) { // 배열 길이보다 하나 적은 횟수만큼 반복

            for (int j = 0; j < arr.length - 1; j++) { // 비교 횟수도 마찬가지로 하나 작음

                if (arr[j] > arr[j + 1]) { // 비교 후 자리바꿈

                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

[0, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 7, 10, 13, 14, 15, 16, 16, 17, 17, 31]

파이썬 구현은 아래와 같다.

def bubble_sort(target):
    for i in range(len(target)):
        for j in range(len(target) - 1):
            if target[j] > target[j + 1]:
                temp = target[j]
                target[j] = target[j + 1]
                target[j + 1] = temp


target = [4, 16, 31, 5, 4, 17, 1, 10, 15, 3, 16, 6, 7, 2, 2, 1, 5, 13, 17, 14, 4, 0]

bubble_sort(target)

print(target)

[0, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 7, 10, 13, 14, 15, 16, 16, 17, 17, 31]