버블 솔트 (Bubble sort)

왼쪽과 오른쪽을 비교해서, 오른쪽이 더 크면 swap해주는 방식

 

파이썬

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

bubble_sort([37, 45, 29, 8])

 

 

자바스크립트

function bubbleSort(arr) {
  // 처음에 i가 4
  for (let i = arr.length; i > 0; i--) {
    // j = 0 , i-1 = 3
    // i가 4면 j는 3까지만 반복   => 맨 끝에는 이미 정렬된거니까, 맨 끝의 길이까지 갈 필요가 없어서
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

bubbleSort([37, 45, 29, 8]);

 

 

시간복잡도

최악, 최선, 평균 모두 O(n^2)