퀵 정렬 (quick sort)

퀵정렬 (quick sort)

이번엔 퀵정렬을 알아 보겠다. 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. 위키출처 이라고 한다. 말그대로 빠른 정렬 방식이다. 위키 출처 일단 설명을 해보자 만약

6, 3, 8, 7, 9, 2, 1, 5

이런 리스트가 있다고 가정하자! 그럼 일단 왼쪽에 있는걸 피벗으로 잡자 6을 피벗으로 잡는다. 그리고 또한 left도 6 이라고 정하고 맨 오른쪽에 있는걸 right라 정하자 그럼 이런 형식이 될거다

6, 3, 8, 7, 9, 2, 1, 5
P                    R
L

P: 피벗 L: left R: right 그리고 나서 left 는 피벗보다 큰 값이 나올때 까지 오른쪽으로 이동하고 rigth는 피벗보다 작은 값이 나올때까지 왼쪽으로 이동한다.

6, 3, 8, 7, 9, 2, 1, 5
P     L              R

이렇게 됐다. 이동한 후에 두개를 교환한다.

6, 3, 5, 7, 9, 2, 1, 8
P     L              R

계속 이동해야된다.

6, 3, 5, 7, 9, 2, 1, 8
P        L        R   

7은 6보다 큰값이나 정지! 1은 6보다 작은값이니 정지! 다시 교환

6, 3, 5, 1, 9, 2, 7, 8
P        L        R   

아직 더 가야된다. 고고!

6, 3, 5, 1, 9, 2, 7, 8
P           L  R         

또 교환해야된다.

6, 3, 5, 1, 2, 9, 7, 8
P           L  R         

이제 왔다 left가 한번더 가고 right더 한번더가면 곂친다. right 더 앞서 있다.

6, 3, 5, 1, 2, 9, 7, 8
P           R  L         

그럼 이제 피벗이랑 right랑 교환해야된다. 두개가 만났다면 left는 0번째 2이고 rigth는 rigth - 1 즉 배열의4번째요소 1이 된다. 현재 right의 요소를 알고 있어야된다.

2, 3, 5, 1, 6, 9, 7, 8
P  L     R           

그래서 다시 이번엔 피벗을 2로 잡고 left는 처음으로 rigth는 왼쪽으로 이동한다. 3은 2보다 크기 때문에 정지 1은 1보다 작기때문에 정지 교환하자

2, 1, 5, 3, 6, 9, 7, 8
P  L     R           

다시 이동하면 left 5는 2보다 크기 때문에 정지 ! right 5는 2보다 크기 때문에 다시 이동 1보다 작기때문에 정지!

2, 1, 5, 3, 6, 9, 7, 8
P  R  L             

이렇게 모양이 나왔다 다시 R은 L보다 앞에 있기때문에 R과 피벗과 교환한다 그리고 다시 돌아온다. right는 위에서 기억하고 있던 4번째 left는 위의 right + 1 즉 배열의요소 2번째가 된다.

1, 2, 5, 3, 6, 9, 7, 8
      L  R           
      P

그리고 다시 작업을 한다. 교환을 한다. 그러면 왼쪽 정렬은 끝났다. 오른쪽도 마찬가지로 정렬을 하면된다.

1, 2, 3, 5, 6, 9, 7, 8
         P     L     R

교환하자

1, 2, 3, 5, 6, 8, 7, 9
               L  R   
               P

1, 2, 3, 5, 6, 7, 8, 9

정렬이 완료 되었다. 그럼 소스를 한번 보자! 요즘 스칼라를 공부중이랑 스칼라로 해봤다. 그래봤자 문법을 잘 몰라서 인지 그냥 자바다... 어차피 뭐 알고리즘이라는게 언어에 종속적인게 아니니까..

def partition(arr: Array[Int], left: Int, right: Int): Int = {
  var high = right
  var low = left
  val pivot = arr(left)

  while (high > low) {

    while (high > low && pivot >= arr(low)) {
      low += 1
    }
    while (pivot < arr(high)) {
      high -= 1
    }
    if (high > low){
      swap(arr, low, high)
    }

  }
  swap(arr, high, left)
  high
}

def swap(arr: Array[Int], left: Int, right: Int) = {
  val temp = arr(left)
  arr(left) = arr(right)
  arr(right) = temp
}

def quick(arr: Array[Int], left: Int, right: Int): Unit = {
  if (right > left) {
    val partitionIndex = partition(arr, left, right)
    quick(arr, left, partitionIndex - 1)
    quick(arr, partitionIndex + 1, right)
  }
}

def main(args: Array[String]) {
  val list = Array(6, 3, 8, 7, 9, 2, 1, 5)
  quick(list, 0, list.length - 1)
}

내 소스가 틀릴수도..있으니..흠