[정렬] 버블정렬 + 최적화

버블정렬은 가장 큰 값 또는 가장 작은 값이 계속 버블되며(자리를 이동하며) 정렬이 되는 알고리즘이다.

 

만약

[1, 2, 7, 4, 6, 5, 3, 8] 이란 배열이 있을 경우에

쭉 오름차순으로 정렬할 수 있고, ex) [1, 2, 3, 4, 5, 6, 7, 8]

내림차순으로 정렬할 수 도 있다. ex) [8, 7, 6, 5, 4, 3, 2, 1]

 

---

버블정렬이 돌아가는 모양새. (출처- 위키백과)

 

 

단순한 정렬 알고리즘인 만큼

직관적이지만 비효율적으로 구현 해볼 수 있다.

아래 코드는 굉장히 naive한 버블정렬 구현이다.

 

원시적인 버블정렬 (Naive)

function naiveBubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j + 1]
                arr[j + 1] = arr[j]
                arr[j] = temp
            }   
        }    
    }
    return arr
}

 

• for문을 2개를 사용해서
• 외부 for문으로 배열 내 엘리먼트 만큼 반복하되,
• 내부 for문도 배열 내 엘리먼트만큼 순회하며 정렬하는 방법이다.

 

하지만 위 알고리즘은 비효율적인 구석이 있다.

1. j가 배열의 끝 인덱스일 때, j + 1은 undefined가 되어 쓰레기값과 연산하게 된다.
   (j + 1이 배열을 초과하기 때문에 존재하지않는 엘리먼트를 비교하게 된다.)
2. 정렬 시 최대값(또는 최소값)이 맨 끝에 오게되며 계속 정렬이 될 것이다.
   즉 정렬이 진행될 때마다,
   연산할 엘리멘트가 하나씩 줄어듦에도 불구하고 쓸데없이 모두 연산을 하게된다.
   ex)
   [8, 7, 1, 2, 3, 4, 5, 6 ]의 경우
   한번 정렬하면 [7, 1, 2, 3, 4, 5, 6, 8] 이 되고,
   두번 정렬하면 [1, 2, 3, 4, 5, 6, 7, 8] 이 된다.
   그렇다면 더 이상 정렬할 필요가 없다. 하지만 위의 알고리즘은 계속 엘리먼트를 순회할 것이다.

 

---

 

 

따라서 이러한 비효율을 해결해야 할 필요가 있다.

먼저, 버블정렬의 특성 상

정렬이 이뤄질때마다 마지막 엘리먼트는 정렬이 필요없게 된다.

따라서 반복문의 순회 로직을 조금 바꿔줄 필요가 있다.

아래 코드는 naive한 버블정렬의 순회 로직을 약간 바꾼 것이다.

 

1차 최적화

function bubbleSort(arr) {
    for(let i = arr.length; i > 0; i--) {
        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
}

• 외부 for문 카운터인 i의 첫 값은 배열의 길이로 한다. (arr.length)
  1을 빼지 않는 이유는 내부 for문의 반복문 로직에 i를 활용할 것이기 때문이다.
• 내부 for문 카운터인 j의 첫 값은 0으로 하되, 반복문 종료 조건을 j < i - 1로 한다.
  만약 배열의 길이가 6일 경우, 첫 i는 6이 되므로, j는 0번 인덱스부터 5번 인덱스까지 순회하게 된다.
  다음 반복문을 돌 경우 i는 5부터 시작하게 되고 j는 0번 인덱스부터 4번 인덱스까지 순회하게 된다.
• 위의 로직을 반영하여 연산이 끝난 엘리먼트는 더이상 연산하지 않게 된다.

 

---

 

위의 최적화에도 여전히 문제가 있다.
만약에 [8, 1, 2, 3, 5, 6, 7] 과 같은 배열을 받았다고 가정해보자.

이 배열은 버블정렬의 첫번째 순회가 끝나면 [1, 2, 3, 5, 6, 7, 8] 이 될 것이고, 더이상 순회할 필요가 없다.

이럴 경우에도 연산이 추가적으로 이루어진다면 굉장히 비효율적이다.

 

즉, 완전하게 순회를 돌았을 때

자리가 교체된 엘리먼트가 없다면

해당 배열은 정렬이 끝났다고 봐도 무방할 것이다.

 

아래는 위의 개선사항을 반영한 코드이다.

 

2차 최적화

function bubbleSort(arr) {
    let noSwaps
    for(let i = arr.length; i > 0; i--) {
        noSwaps = true
        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
                noSwaps = false
            }
        }
        if (noSwaps) break
    }
    return arr
}

• noSwaps 이라는 변수를 하나 생성한다. 이 값은 내부 순회에서 스왑이 이루어졌는지를 판단할 친구다.
• 외부 for문이 내부 for문을 동작시키기 전에 noSwaps을 true로 한다.
  내부 for문이 아직 돌아가지 않았으므로, noSwaps은 true가 된다.
• 내부 for문에서 정렬이 필요한 엘리먼트가 있을 경우에는 정렬하되, noSwaps을 false로 바꿔준다.
• 내부 for문의 순회를 마친 뒤, 만약 noSwaps가 여전히 true라면 (즉, 내부 for문에서 swap이 이루어지지 않았다면)
  내부 배열은 이미 정렬이 끝난 상태이므로 반복문을 break 하고 정렬된 arr를 리턴한다.

---

 

위와 같은 최적화 덕에

버블정렬은

정렬이 얼추 되어있는 배열의 정렬에서 좋은 효율을 보여준다.

 

• naive한 버블정렬의 시간복잡도는 O(N^2)이고
• 1차 최적화 한것의 시간복잡도도 엄밀히 따지자면 O(N^2)일 것이다.
• 하지만 아래 2차 최적화의 경우에는 시간복잡도로 따지기는 어렵지만
  거의 O(N)과 엇비슷하게 된다.

 

느낀 점

알고리즘을 짤 때는 효율적이지 못한 부분을 최대한 배제하려고 노력해라.