학부 시절 때 부터 정렬에 대한 문제들은 정말 많이 접해보았을 것이다.
버블정렬과 이 버블 정렬의 시간 복잡도를 최대로 보완한 로직도 살펴보기로 하자.
가장 기본적인 버블정렬 알고리즘에서 파생된 알고리즘이다.

public static void bubbleSort(int[] a, int n) {
    // k를 0으로 초기화 해 주는 이유는 함수가 처음 실행될 때
    // 전체를 훑으면서 마지막에 교환된 위치를 반환하여
    // 범위를 좁혀줘야 하기 때문이다.
    int k = 0;
    //while : 처음 실행 한번 이후에는 k보다 큰 범위로 범위를 좁힌다.
    while (k < n - 1) {
        // 마지막으로 교환된 위치를 저장하는 last
        int last = n - 1;
        // for문은 위치변경이 일어났을 때 
        // 현재 위치변경이 일어난 우측 방향으로 k값을 정한다.
        //while문의 범위를 좁혀준다.
        for (int j = n - 1; j > k; j--) {
            if (a[j - 1] > a[j]) {
                swap(a, j - 1, j);
                last = j;
            }
        }
        k = last;
    }
}

위 코드를 살펴보면 k를 0으로 초기화 해 주는 이유는 함수가 처음 실행될 때 전체를 훑으면서 마지막에 교환된 위치를 반환하여 범위를 좁혀줘야 하기 때문이다.
while 문에서는 맨 처음 한 번 실행된 이후에는 비교하고자 하는 인덱스를 k보다 큰 범위로 범위를 좁힌다.
마지막으로 교환된 위치를 저장하는 last는 k로 넘어가게 되어 k의 값을 증가시키는 역할을 하게 된다.
즉, for문은 k보다 큰 변수를 항상 last에 넣어주며 while문의 범위를 좁혀준다.
쉽게 말해, k의 값은 정렬이 될 때 마다 오른쪽으로 이동하게 된다는 것이다.

기존에 for문 2개를 사용했을 때는 1개의 for문 요소들을 나머지 안쪽 1개의 for문에 계속해서 넣어줬다는 것을 알 수 있다.

for문 2개를 사용하는 일반적인 버블정렬과 비교했을 때 시간 복잡도가 보완됐다는 것을 알 수 있다.