버블 정렬

버블 정렬

버블 정렬은 현재 배열 요소와 그 다음 배열 요소를 비교해 현재 요소가 더 크면 교환하는 정렬 방법입니다. 그러니까 배열의 0번 인덱스의 요소와 1번 인덱스의 요소를 비교하고, 그 다음 1번 인덱스의 요소와 2번 인덱스의 요소를 비교합니다. 이 과정을 계속하면 정렬이 됩니다.

인덱스를 j라고 표시하겠습니다. 우선 가장 앞 자리부터 그 다음 원소를 비교합니다. 9와 8을 우선 비교하는 것입니다. 9가 더 크니 8과 9를 바꿉니다.

그 다음 j가 하나 증가하여 다음 자리를 가리키고 9와 1을 비교합니다. 9가 더 크니 1과 9를 바꿉니다.

가장 큰 요소를 끝으로 보내려고 하는 겁니다. 다음 j를 하나 증가시키고 9와 3을 비교합니다. 9가 더 큽니다. 3과 9를 바꾸어줍니다.

다시 j가 하나 증가하게 되고 9과 2를 비교해보니 9가 더 크니까 자리를 바꾸어줍니다.

그 다음은 4번째(인덱스 3)까지 이런 방식을 반복합니다. 하나씩 줄여가면서 이런 방식을 반복하여 가장 큰수를 오른쪽으로 보내면 정렬이 되는 것입니다.

시간복잡도

이중 반복문 → $O(N^2)$

구현

class Solution {
    public int[] bubbleSort(int[] nums) {
        for (int i=0; i < nums.length-1; i++) {
            boolean isSorted = true;
            for (int j=0; j < nums.length-1-i; j++) {
                if (nums[j] > nums[j+1]) {
                    int tmp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = tmp;
                    isSorted = false;
                }
            }
            // 한바퀴를 돌아도 숫자 위치를 바꾼 경우가 한번도 없다면 이미 정렬된 것, 종료
            if (isSorted)
                break;
        }
        return nums;
    }
}