문제

[코플릿 - bubbleSort]

---

코드

naive solution

// naive solution
public int[] bubbleSort(int[] arr) {
    int arrLength = arr.length;
    int tmp;

    for(int i = 0; i < arrLength; i++) {
      for(int j = 0; j < arrLength - 1; j++) {
        if(arr[j] > arr[j + 1]) {
             tmp = arr[j];
             arr[j] = arr[j+1];
             arr[j+1] = tmp;
        }
      }
    }
    return arr;
}

버블 정렬 코드를 작성하라고 했을 때, 처음으로 작성한 코드이다.

✔️ 수행 시간을 단축시키기 위해서 코드를 개선해보자!

• 버블 정렬에서 i는 회전의 횟수, 고정되는 값의 갯수를 나타낸다.
• 버블 정렬에서 j는 비교하는 값의 index를 의미한다.

• 1 회전(i=0)이 수행되면, 가장 큰 값이 맨 뒤로 이동한다.(1개 고정)
• 2 회전(i=1)이 수행되면, 두 번째로 큰 값이 맨 뒤에서 두번째로 이동한다.(2개 고정)
• 4 회전(i=3)이 수행되면, 4개의 값이 고정되고 가장 작은 값은 자동으로 첫 번째 위치에 고정된다.

즉 n개의 배열을 정렬하기 위해서는 n-1번의 회전이 필요하다.
=> i는 [0, n-1) 범위를 갖는다.

• 1 회전(i=0)에서 j는 3(n-1-1)까지 증가한다.
• 2 회전(i=1)에서 j는 2(n-1-2)까지 증가한다.

j는 [0, n-1-i) 범위를 갖는다.

---

개선한 코드

public int[] bubbleSort(int[] arr) {
    int arrLength = arr.length;
    int tmp;

    for(int i = 0; i < arrLength-1; i++) {
      for(int j = 0; j < arrLength - 1 - i; j++) {
        if(arr[j] > arr[j + 1]) {
             tmp = arr[j];
             arr[j] = arr[j+1];
             arr[j+1] = tmp;
        }
      }
    }
    return arr;
}

• i, j의 범위를 줄여주었다.

여기까지 수정하면 최선의 코드라고 생각했는데, 더 개선할 부분이 남아있다.

for문을 다 돌지 않아도 이미 정렬이 완료되는 경우가 발생하는데, 이 경우에 for문을 탈출하도록 수정해야 한다.

---

optimized solution

public int[] bubbleSort(int[] arr) {
    int tmp;
    boolean isSwapped = false;
    
    for (int i = 0; i < arr.length - 1; i++) {
        isSwapped = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                isSwapped = true;
           }
        }
        if(isSwapped==false) break;
    }
    return arr;
}

• isSwapped 변수를 추가해주었다.
• 회차를 돌면서 해당 배열에 swap이 발생하지 않는다면, 이미 정렬이 완료된 배열이므로 for문을 탈출한다.