버블 정렬이 무엇일까

버블 정렬#

배열의 첫 번째부터 그다음 배열과 비교하여 크다면 swap하고 작다면 다음 index으로 넘어간다 그렇게 배열끝까지 정렬을 시작한다

말로만 설명을 하려니 어렵다

[6,2,4,10,8,1] 배열이 있을 때 버블 정렬을 적용해보도록 하자

1. 6 > 2 2보다 큰가 ? swap [2,6,4,10,8,1]
2. 6 > 4 4보다 큰가 ? swap [2,4,6,10,8,1]
3. 6 > 10 10보다 큰가 ? next [2,4,6,10,8,1]
4. 10 > 8 8보다 큰가 ? swap [2,4,6,8,10,1]
5. 10 > 1 1보다 큰가 ? swap [2,4,6,8,1,10]

첫 번째 순회를 돌게되면 [2,4,6,8,1,10] 다음과 같이 값이 나온다 배열의 길이만큼 돌게 되면 [1,2,4,6,8,10] 이라는 정렬된 배열이 나오게 된다

코드는 다음과 같다

1
function bubbleSort(arr) {
2
  for (let i = 0; i < arr.length; i++) {
3
    for (let j = 0; j < arr.length - 1; j++) {
4
      if (arr[j] > arr[j + 1]) {
5
        let temp = arr[j];
6
        arr[j] = arr[j + 1];
7
        arr[j + 1] = temp;
8
      }
9
    }
10
  }
11
  return arr;
12
}

하지만 문제가 하나 있다

거의 정렬된 배열에서 버블 정렬을 시작하게 되면 효과적이지 않다

2번 순회만에 완벽이 정렬이 되어도 해당 로직은 배열의 길이만큼 순회를 하면서 정렬을 시도하기 때문이다

그렇다면 중간에 멈추면 되지않을까?

맞다 swap이 한 번도 일어나지 않는다면 그 배열은 정렬이 끝난것이다 그래서 swap이 일어났는지 체크를 해주면 된다

1
function bubbleSort(arr) {
2
  for (let i = 0; i < arr.length; i++) {
3
    let noswap = true;
4
    for (let j = 0; j < arr.length - 1; j++) {
5
      if (arr[j] > arr[j + 1]) {
6
        let temp = arr[j];
7
        arr[j] = arr[j + 1];
8
        arr[j + 1] = temp;
9
        noswap = false;
10
      }
11
    }
12
    if (noswap) break;
13
  }
14
  return arr;
15
}

noswap을 추가하여 1회의 순회가 돌아도 true라면 break로 반복문을 탈출하여 결과를 리턴하게 된다

한동룡