정렬 알고리즘[Quick Sort]

Quick sort 란?

 

Quick sort는 최선,평균 시간복잡도가 O(n log n)이고, 최악의 경우에는 O(n^2)인것을 확인할 수 있다.

그리고 메모리는 O(n log n)인것을 확인할 수 있다

 

Quick sort는 이름에서도 나타나듯이 평균적으로 매우 빠른 수행속도를 자랑하는 정렬방법이다. 

Quick sort도 Merge sort와 같이 분할정복법을 사용한다. 그러나 Merge sort와 달리 리스트를 균등하게 분할할 필요는 없다.

Quick sort도 Merge sort와 같이 시간복잡도가 O(n log n)인데, Quick sort가 훨씬 짧은 시간이 걸린다는것을 알 수 있다. 왜그럴까??

이는 "참조지역성의 원리"로 설명할 수 있다!

• Quick sort는 알고리즘 특성상 동일한 배열 내에서 자리를 이동시킨다. 그래서 인접한 데이터들 사이에서 이동이 발생하기 때문에, 제일 처음 배열에 접근할 때만 실제메모리에서 데이터를 가져오고, 이후에는 캐시에 올려놓고 바로바로 데이터를 가져올 수 있기 때문에 훨씬 짧은 시간이 걸리는 것이다

또한 "pivot(피봇) 연산 제외" 의 특성도 속도에 영향을 끼친다

• 한번 위치가 정해진 pivot(피봇)값은 이후의 연산에서는 해당값은 제외시키고 연산하기 때문에, 정렬(분할)이 진행될수록 계산해야할 요소가 점점 줄어들어, 계산해야할 수가 줄어들기때문에 정렬속도가 빨라지는 특징이 있다.

 

보통 정렬방법들은 이름으로부터 어떻게 정렬을 할지 유추할 수 있다. Quick sort도 그런식으로 이름을 바꾼다면 피벗정렬(pivot sort)로 바꿀 수 있을것같다. 

Quick sort는 배열(or 리스트)중에 한 요소를 pivot(피벗)으로 선택한다.

그런다음 pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽에, 큰 요소들은 모두 pivot의 오른쪽으로 옮긴다.

이렇게하면 pivot을 중심으로 왼쪽은 pivot보다 작은요소, 오른쪽은 큰요소로 구성된다.

더이상 쪼갤 부분집합이 없을때까지 위의 과정을 반복하면 전체리스트가 정렬된다.

 

 

이제 그림을 통해 Quick sort가 정렬(분할)되는 과정을 구체적으로 살펴보자

 

먼저 pivot값을 정해줘야한다

pivot값은 리스트에서 가장앞에 있는 원소여도되고, 중간, 가장 뒤에있는 원소로 설정해도 상관없다.

그대신 중간으로 정했다면 다음번에 정렬할때도 계속 중간에 있는 원소를 pivot값으로 설정해야된다

 

지금은 중간에 위치한값인 5를 pivot으로 설정해보겠다!

중간에 위치한 5를 pivot값으로 설정

 

 

 

 

이제 pivot값을 기준으로 원소들을 재배치해야한다.

pviot값을 기준으로 왼쪽에는 pviot보다 작은값, 오른쪽에는 pviot보다 큰값이 위치하게된다.

pviot값을 기준으로 왼쪽에는 pviot보다 작은값, 오른쪽에는 pviot보다 큰값이 위치

 

 

 

이렇게하면 pviot값을 기준으로 왼쪽과 오른쪽 2개의 서브리스트를 확인할 수 있다.

이제 각각의 서브리스트에서도 앞에 했던 로직과 똑같이 반복해준다.

왼쪽의 리스트에서는 중간값인 1을 pivot값으로 설정하고, 오른쪽 리스트에서는 pivot값을 6으로 설정할 수 있다.

 

왼쪽,오른쪽 서브리스트에서 pivot값을 설정

 

 

 

 

왼쪽, 오른쪽의 설정한 pivot값을 기준으로 재정렬을 한 모습이다.

왼쪽 서브리스트에서 1보다 작은값은 왼쪽, 큰값은 오른쪽 / 오른쪽 서브리스트에서도 6보다 작은값은 왼쪽,큰값은 오른쪽에 정렬을 해서 재정렬을했다.

이제 오른쪽의 서브리스트는 원소의 개수가 7 하나만 남았기때문에, 더이상 분할할 수 없는 단위가 되었다. 따라서 오른쪽의 서브리스트는 퀵정렬이 종료된다.

왼쪽은 아직 서브리스트가 남아있기때문에 다시 진행해준다.

중간값인 3을 pivot으로 설정해줘야될것이다.

 

재정렬된 모습

 

 

중간값인 3을 pivot으로 설정해준 모습이다

왼쪽 서브리스트의 pivot값을 3으로 설정

 

 

 

이제 3을 기준으로 작은값을 왼쪽에, 큰값을 오른쪽에 위치시킨 모습이다.

이렇게되면 왼쪽 서브리스트의 원소의 개수도 모두 1이 되기때문에, 더이상 분할될 수 없어서 퀵소트는 종료되게 된다.

결과를 보면 순서대로 잘 정렬이 된것을 확인할 수 있다.

이런 방식을 보면 자기자신을 계속 호출(pivot을 계속 지정)하므로 재귀호출 방식으로 정렬된다고도 볼 수 있다

퀵소트 종료

 

 

 

 

 

 

방금 설명했던 이런 원리에 의해서 Quick sort가 정렬되는데, 

이는 분할정복을 이용하여 구성하는 함수와, 피벗을 기준으로 왼쪽과 오른쪽으로 옮겨 정렬하는 partition()함수로 나눌 수 있다.

 

그러면 컴퓨터는 어떻게 pivot을 기준으로 왼쪽 리스트와 오른쪽 리스트를 정렬할까?? 

여러가지 방법으로 구현할 수 있겠지만, 제일 많이 사용하는 Lomuto(로무토) 분할방법을 사용해서 살펴보겠다.

 

 

Lomuto 분할방법 이란?

규칙에 따라 pivot값과 나머지값을 하나하나씩 비교하고 swipe하는 방법이다

배열의 가장 오른쪽값을 pivot으로 사용하고(가장 왼쪽값으로 해도됨), 배열의 가장 왼쪽위치-1을 i로 둔다.

범위안의 요소들을 pivot값 전까지 방문하고,

방문한값(j)와 pivot을 비교해서

• pivot보다 값이 크면 -> 넘어감(j값 한칸이동)
• pivot보다 값이 작으면 -> i위치 1 증가, i의 위치값과 j값을 swipe

j가 pivot값에 도달하면 ->  i를 1 증가시키고, i위치값과 pivot을 swipe

 

 

 

j와 pivot을 비교했을때 3<6 (j<pivot)이므로 i를 1증가시키고, i와 j위치값 swipe

기본설정

 

i = j이므로 swipe해도 똑같음

3<6 이므로 i값 1증가하고 i,j swipe

 

 

다시 j,pivot 비교

4<6 이므로 i값 증가시키고, i,j swipe

 

 

역시 i=j 이므로 swipe해도 똑같음

 

1,6 비교

1<6 이므로 i값 증가시키고 swipe

역시 같기때문에 바뀌는거 없음

 

5,6 비교

5<6 이므로 i값 증가시키고 swipe

이번에도 같기때문에 바뀌는거 없음

7,6 비교

7>6 (j>pivot) 이므로 j값 한칸 이동!

 

2,6 비교

2<6 이므로 i값 증가시키고 i,j값 swipe!

j값 한칸이동

i값 증가

i,j값 swipe

 

 

j 가 pivot값에 도달했기 때문에, i를 1 증가시키고, i값과 pivot을 swipe

i 1증가

i값과 pivot을 swipe

 

이렇게하면 Lomuto를 사용한 분할이 끝난다

정렬된 결과를 보면, 기준값이였던 6앞에는 6보다 작은값들이 오고, 뒤에는 6보다 큰 값으로 정렬된것을 확인할 수 있다

 

 

 

Quick sort의 시간복잡도

아까 위에서 설명했던것처럼

데이터를 절반씩 분할하면서 줄여나가기 때문에 log N만큼의 분할이 이뤄지게되고,

각 분할에서 N번의 값 비교를 통해서 자신의 위치를 찾아나가기 때문에 시간복잡도가 N log N 이 나오게 되는것이다.

 

그치만 최악에 경우에, 정렬하고자하는 리스트의 경우가 이미 정렬된 상태라면(pivot이 그룹 내의 가장 큰값이나 작은값이 되면)

시간복잡도는 N제곱까지 늘어날수있다.

 

 

예를들어, 오름차순으로 되어있는 리스트가 있는데, 가장 앞에있는 1의 값을 pivot값으로 정했다고 가정해보자

 

 

 

 

이걸 분할하면, 1이 제일 작은값이기 때문에 왼쪽에 넣을값이 없어서 당연히 아래그림처럼 분할될것이다

 

 

그럼 이제 pivot은 2가되고 또 아래 그림처럼 분할이 될것이다

 

계속 이런식으로 분할이될텐데, 그러면 분할이 절반씩 이루어지지 않아서 최악의 효율을 낸다고 할 수 있다

 

절반씩 분할할때 logN번의 분할횟수가 나온다는것을 도출해서 NlogN이라는 시간복잡도가 나왔던건데,

이런경우에는 분할횟수가 데이터의 개수만큼, 즉 N번만큼 발생하게된다는것이다.

따라서 시간복잡도가 N제곱만큼 나오게되는것이다.

 

그래서 최악의 시간복잡도를 피하기위해서 pivot값을 고를때 

몇가지 pivot값의 후보군을 두고, 그중에 가장 중간값을 찾아서 pivot으로 사용하는 알고리즘을 사용하기도 한다고한다.

이를 Median of Three 라고한다. 이것도 추후에 공부해봐야겠다.

 

 

 

 

예제를 통해 보기

이번에도 백준 알고리즘 [수정렬하기 - 2750번]을 quick sort 알고리즘을 사용해서 풀어봤다

(https://www.acmicpc.net/problem/2750)

 

 

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    println("줄의 개수를 입력하세요:")
    val n = reader.readLine().toInt()
    val list = mutableListOf<Int>()

    println("숫자를 입력하세요:")
    repeat(n) {
        list.add(reader.readLine().toInt())
    }

    println("결과:")
    val startTime = System.currentTimeMillis()  // 시간비교위해
    quickSort(list, 0, list.size - 1)
    val endTime = System.currentTimeMillis()
    list.forEach { println(it) }

    println("quickSort 수행 시간: ${endTime - startTime}")
    reader.close()
}


// 하위배열의 요소를 재배열하고, 피벗의 최종위치 반환하는 함수 -> 피벗을 기준으로 왼쪽에는 작은값, 오른쪽에는 큰값 배치됨
// low=시작 인덱스, high=마지막 인덱스
fun partition(arr: MutableList<Int>, low: Int, high: Int): Int {
    // pivot설정(마지막 값으로 지정) [처음,중간 또는 랜덤으로 지정해도됨]
    val pivot = arr[high]
    var i = low - 1
    /// 하위배열 반복
    for (j in low until high) {
        // arr[j] <= pivot 이면
        // i증가하고, arr[i]와 arr[j] 교환
        if (arr[j] <= pivot) {
            i++
            val temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
        }
    }

    // 피벗을 올바른 위치에 할당 -> 피벗을 기준으로 왼쪽에는 작은값, 오른쪽에는 큰값 배치
    val temp = arr[i + 1]   // 피벗과 바꿀수있도록 인덱스의값을 일시적으로 저장
    arr[i + 1] = arr[high]  // 피벗을 올바른 위치에 할당
    arr[high] = temp
    return i + 1            // 분할 후 피벗의 최종인덱스 반환
}


// 배열을 하위배열로 나누고, 각부분을 별도로 정렬하는 함수
fun quickSort(arr: MutableList<Int>, low: Int, high: Int) {
    // 하위배열에 두개이상의 요소가 있는지 확인
    if (low < high) {
        // 피벗이 최종정렬된 위치에 있도록 partition 재정렬
        val pi = partition(arr, low, high)
        quickSort(arr, low, pi - 1) // 피벗보다 작거나 같은 요소가 포함된 하위 배열을 재귀적으로 정렬
        quickSort(arr, pi + 1, high) // 피벗보다 큰 요소가 포함된 하위 배열을 재귀적으로 정렬
    }
}

 

입력값으로 [29, 10, 14, 37, 13]을 입력했다고 가정하자

partition()함수 실행으로 pivot = arr[4] = 13 ,  i = arr[-1] 이됨

 

arr[j], pivot과 비교 

29>13 이므로 그냥 넘어감

 

10<13 이므로

i 증가, arr[i],arr[j] 교환

i 증가

arr[i],arr[j] 교환

 

14>13 이므로 넘어감

 

37>13 이므로 넘어감

 

 

j가 pivot의 위치에 도달함

arr[1] 값과 arr[4]값 교환

arr[1] 값과 arr[4]값 교환

 

피벗인덱스 i+1 반환 

즉, 1 반환

최종적으로 13을 기준으로 왼쪽엔 13보다 작은값, 오른쪽은 13보다 큰값이 온것을 확인할 수 있음

 

 

이제 quicksort 함수 실행

왼쪽 하위배열 -> quickSort(arr, 0, 0) -> 10이라는 한개의 요소밖에 없기때문에 정렬종료

오른쪽 하위배열 -> quickSort(arr, 2, 4) -> 다시 partition()함수 사용해서 정렬

 

14<29 비교

i 증가, arr[i],arr[j] 교환 (교환해도 변경없음)

i 증가 (교환해도 변경없음)

 

37>29 이므로 넘어감

j가 pivot의 위치에 도달함

arr[3] 값과 arr[4]값 교환

피벗인덱스 i+1 반환

즉, 3 반환

arr[3] 값과 arr[4]값 교환

 

역시 29를 기준으로 왼쪽엔 29보다 작은값, 오른쪽은 29보다 큰값이 온것을 확인할 수 있음

 

 

이제 quicksort 함수 실행

왼쪽 하위배열 -> quickSort(arr, 2, 2) -> 14이라는 한개의 요소밖에 없기때문에 정렬종료

오른쪽 하위배열 -> quickSort(arr, 4, 4) -> 역시 37이라는 한개의 요소밖에 없기때문에 정렬종료

 

정렬 끝!!!

전체 배열이 잘 정렬된것을 확인할수있음!!!

코드를 통해 quicksort가 정렬되는 원리를 다시한번 확인해볼 수 있었다

 

 

 

 

 

 

 

 

 

 

 

 

#참고자료

https://spacebike.tistory.com/29

퀵 정렬 (Quick sort) 쉽게 알기

https://dev-musa.tistory.com/entry/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A0%95%EB%A6%AC-%EC%BD%94%ED%8B%80%EB%A6%B0

정렬 알고리즘 정리 코틀린

 

https://rosweet-ai.tistory.com/53

알고리즘 퀵정렬(Quick sort) 그림으로 쉽게 이해하기