알고리즘 [퀵정렬]

🔎 퀵정렬

• 퀵정렬은 분할통치법에 기초한 정렬알고리즘이다.
• 분할, 재귀, 통치의 3단계로 이루어 진다.

분할
기준원소 p를 택하여(보통 마지막 원소) l을 세부분으로 분활
LT: p보다 작은 원소들 EQ: p와 같은 원소들 GT: p보다 큰 원소들

재귀
LT와 GT를 정렬

통치
LT,EQ,GT를 결합

합병정렬과 차이점은 통치에 시간을 많이 쓰기 보다 분할에 조금더 정성?이 많이 들어간 알고리즘이다.

Alg quickSort(L)
  input list L with n elements
  output sorted list L

1. if(l.size() > 1)
  k <- a position in L
  LT, EQ, GT <- partition(L,K)
  quickSort(LT)
  quickSort(GT)
  L <- merge(LT,EQ,GT)
2. return

Alg partition(L, K)
  input list L with n elements,
    position k of pivot
  output sublists LT, EQ, GT of the
  elements of L, less than, equal to, or greater than pivot, resp

1. p <- L.get(k) {pivot}
2. LT, EQ, GT <- empty list
3. while (!L.isEmpty())
    e <- L.removefirst()
    if(e < p)
      LT.addLast(e)
    elseif(e = p)
      EQ.addLast(e)
    else{e>p}
      GT.addLast(e)
4. return LT,EQ,GT  

의사코드의 형태를 보면 크게 partition, quicksort(재귀), merge의 형태로 이루어 진다.

이때 가장 중요한 부분인 분할 부분은 기준 p를 정하여 각각의 리스트에 다시 삽입하여 반환한다.

기준원소가 되는 p를 선택하는 여러가지 방법이 있다.

• 맨 앞 원소, 맨 뒤 원소, 중간 원소
• 맨 앞, 중간, 맨 뒤의 중앙값
• 0/4, 1/4, 2/4, 3/4, 4/4 위치의 다섯 원소의 중앙값
• 전체 원소의 중앙값
• 무작위 방식으로 원소 선택

위 처럼 다양한 방법이 있는 이유는 원소의 값들이 각각 다르기 때문에 이 기준을 정하는 부분이 매우 중요하다.

결론 적으로 이 기준원소를 선택하는 부분이 퀵 정렬의 전체적인 수행 성능에 영향을 미친다.

🔎 최악실행시간

퀵정렬의 경우 최악의 경우의 수는 기준 원소가 항상 유일한 최소,최대 원소일 경우 O(n²)를 가진다. n + (n - 1) + … + 1

그렇다면 알고리즘을 설계할 때 가장 최악으 경우의 수가 그 알고리즘의 우의 실행시간으로 표기하기 때문에.. 위의 경우는 이루어 지지 않는다고 생각하면 된다.

퀵 정렬에선 좋은 호출과 나쁜 호출이 있는데 좋은 호출은 LT : GT의 비율이 25 : 75 보다 작거나 같으면 좋은 호출로 본다 ex) 30 : 70 등등..

나쁜 호출은 25 : 75 크기가 커진다면 안좋은 호출이다. ex) 20 : 80

🔎 기대실행시간

그렇다면 경우의 수가 두가지로 나뉘게 되는데 좋은 호출을 부를 경우가 2/1이고 나쁜 호출을 부르는 경우도 2/1이다.

즉, i/2개가 좋은 호출이라고 일반화할 수 있는데 그에 따른 기대 실행 시간은 O(n log n)이다.

🔎 제자리 퀵 정렬

Alg inplaceQuickSort(L,l,r)
  input list L, position l,r
  Output list L, with elements of
    position from l to r rearranged in increasing order

1. if(l >= r)
  return
2. k <- a position between l and r
3. a, b <- inplacepartition(L,l,r,k)
4. inPlaceQuickSort(L,l,a - 1) {LT}
5. inPlaceQuickSort(L,b+1,r) {GT}

Alg inplacePartition(A,l,r,k)
  input array A[l,r] of distinct
    elements, index l,r,k
  output final index of the pivot
    resulting from partitioning
    A[l..r] into LT, pivot, GT

1. p <- A[k]
2. A[k] <-> A[k]
3. i <- l
4. j <- r - 1
5. while(i <= j)
  while(i <= j & A[i] <= p>)
    i <- i + 1
  while(j >= i & A[j] >= p)
    j <- j - 1
  if(i <= j)
    A[i] <-> A[j]
6. A[i] <-> A[r]
7. return i;

제자리 퀵 정렬일 때 크게 다른점은 대체작업을 사용한다는 것인데 LT, EQ, GT에서 피봇을 숨긴 뒤 i,j를 인덱스로 저장한뒤 pivot과 비교하며 큰 값 작은값을 분리한뒤 돌려준다.