[Algorithm] 버블정렬(Bubble Sort)

설명

• 옆에 있는 값과 비교해서 큰 갚을 뒤로 보내는 방식
• 코드가 단순하기 때문에 자주 사용
• 시간 복잡도 : O(N^2)
• 참고
  • https://youtu.be/EZN0Irp2aPs

예시

• 초기값
  • 1 10 5 8 7
• 앞 값(j)과 뒷 값(j + 1)을 비교해서 큰 값을 뒤로 이동, j가 맨 뒷값(i)을 만나기 전까지 반복
  • 1(j) 10(j + 1) 5 8 7(i)
  • 1 10(j) 5(j + 1) 8 7(i) → 1 5(j) 10(j + 1) 8 7(i)
  • 1 5 10(j) 8(j + 1) 7(i) → 1 5 8(j) 10(j + 1) 7(i)
  • 1 5 8 10(j) 7(j + 1)(i) → 1 5 8 7(j) 10(j + 1)(i)
• i를 한 칸 앞으로, j는 0부터해서 위 과정을 반복

코드

public class Solution {
    public static int[] sort(int[] data) {
        for (int i = data.length - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (data[j] > data[j + 1]) {
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                }
            }
        }

        return data;
    }
}

class SolutionTest extends Specification {
    @Unroll
    def "#data -> #result"() {
        expect:
        Solution.sort(data as int[]) == result

        where:
        data                            | result
        [1, 10, 5, 8, 7, 6, 4, 3, 2, 9] | [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    }
}