버블정렬 어디까지 속도 개선할 수 있을까?

일단 버블정렬이 뭐하는 건지 기본적 방식은 익숙하다는 가정하고 글을 적는다.

버블정렬이 느린 이유는 순회의 순회, 그러니까 N^2 이 알고리즘에 필연적으로 포함되어 있기때문!

그렇다면 알고리즘 자체를 바꾸지 않는 선에서
정렬 성능을 개선하기 위해서는 순회에 대한 제어가 필요하다는 말이 되겠다.

순회 개선을 하기 위해서는 일종의 숏컷 검사기들을 도입하면 되는데.
먼저 아래 코드를 보자. (Golang)

func minimumBribes(q []int32) {
    totalSwapCnt := int32(0)
    tmp := int32(0)
    chaos:=false
    swapInLoop:=false
    offset:=0
    backOffset:=0
    for i:=len(q)-1;!chaos&&i>0;i--{
        for j:=offset;j<i-backOffset;j++ {
            if q[j] > int32(j)+3 {
                chaos = true
                break
            }
            if q[j] > q[j+1] {
                if swapInLoop == false {
                    if j>1 && q[j-1]==int32(j) && offset < j-1 {
                        offset=j-1
                    }
                    swapInLoop=true
                }
                totalSwapCnt++
                tmp = q[j+1]
                q[j+1] = q[j]
                q[j] = tmp
            }
            if j==i-1 && q[j]==int32(j+1) {
                backOffset++
            }
        }
        if swapInLoop == false {
            break
        }
    }
    if chaos {
        fmt.Println("Too chaotic")
    } else {
        fmt.Println(totalSwapCnt)
    }
}

위 코드에 적용된 버블정렬 숏컷의 종류는 총 3가지다.
(코드만 보고 다 찾고 이해했다면 뒤로가기를 눌러주세요)

• 적용이 부적절할때

1. Too chaotic : 너무 복잡한 인풋이 들어왔을 때 포기하는 숏컷
   이게 무슨 숏컷이야? 싶지만 기본적으로 N^2 알고리즘이기도 하고
   인풋에 따라 프로그램이 스스로 "내가 하기 부적절해!"라고 말해주는 것도 좋으니깐ㅎㅎ

• 크기에 따라 있어야 할 위치번호를 알 때!

2. offSet : 순회 범위 앞쪽 잘라내기
   버블정렬에서 내부 순회 중 swap이 한번도 발생하지 않은 상태에서 비교 항목이 해당 항목이 있어야할 적절한 위치에 있다면, 그 지점까지 정렬이 완료된 것으로 볼 수 있으므로 이후 순회부터 앞부분 비교를 스킵!
3. BackOffSet : 순회 범위 뒤쪽 2개씩 잘라내기
   매 순회 N회차마다 N번째로 가장 큰 수를 맨 뒤로 보내는 버블정렬 특성상 범위 뒤쪽 1개씩 잘리는 게 기본이지만, 크기에 따른 위치 2개씩 자를 수 있음

** 값을 크기에 따라 있어야 할 위치번호를 아는경우에는 솔직히 버블정렬 할 필요 없지만 이동횟수 측정 등이 필요한 경우에 적용할 수 있음