📙

거품 정렬 BubbleSort

거품 정렬

bubble sort

거품 정렬은 가장 기본적인 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘

Process

첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)

두 번째 요소와 세 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)

1, 2를 마지막까지 반복합니다. (마지막에서 두 번째 요소와 마지막 요소를 비교)

1~3의 과정을 한 번 거치게 되면, 가장 큰 요소가 배열의 마지막으로 밀려납니다.

1~3의 과정을 첫 요소부터 다시 반복합니다.

5를 통해 두 번째로 큰 요소가 배열의 마지막 바로 두 번째로 밀려납니다.

1~3의 과정을 총 n번(배열의 크기) 반복합니다.

JavaScript

const bubbleSort = function (arr) {

  for (let i = 0; i < arr.length; i++) {
    let temp;
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
    if (!temp) {
      break;
    }
  }
  return arr;
};
JavaScript
복사

Python

def bubble_sort(data):
		list_length = len(data) - 1
    for i in range(list_length):
        swap = False
        for j in range(list_length - index):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
                swap = True

        if swap == False:
            break

    return data
Python
복사

# http://ejklike.github.io/2017/03/04/sorting-algorithms-with-python.html
def bubbleSort(x):
    for size in reversed(range(len(x))):
        for i in range(size):
            if x[i] > x[i + 1]:
                x[i], x[i + 1] = x[i + 1], x[i]
    return x
Python
복사

•

시간복잡도 :  (n−1)+(n−2)+...+2+1=n(n−1)/2(n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2(n−1)+(n−2)+...+2+1=n(n−1)/2  →  O(n2n^2n2)

→ 데이터가 잘 정렬되어있다면 O(

n

)이므로 데이터의 정렬 여부를 파악하기 위한 알고리즘으로 사용

시간복잡도가 상당히 느리지만 코드가 단순하기 때문에 자주 사용된다.

•

공간복잡도 : O(nnn)

장점

•

구현이 매우 간단하고, 소스코드가 직관적

•

이미 정렬된 데이터를 정렬할 때 가장 빠름

•

정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않음 ⇒ 제자리 정렬 (In-place sorting)

•

안정 정렬 (Stable Sort)

단점

•

시간복잡도가 최악, 최선, 평균 모두 O(n2n^2n2)으로, 굉장히 비효율적

•

정렬되어있지 않은 원소가 정렬 되었을 때의 자리로 가기 위해서 교환 연산(swap)이 많이 일어남