Quick Sort [Algorithm]

채상혁·2022년 6월 10일
0

Divide & Conquer , Rekursive 를 이용한 정렬 알고리즘입니다.

분할정복(Divide & Conquer)이란 상단에서 분할하고 중앙에서 정복하고 하단에서 조합(Combine)하는 형태입니다.

자세한 내용은 >> 분할정복 <<

java의 Arrays.sort(), python의 list.sort() 등이 퀵정렬을 기반으로 합니다.

퀵정렬을 이해하기 위해 정렬되지 않은 정수 배열을 보겠습니다.

[5,2,3,4,6,9,7,1,8]

Quick Sort는 병합정렬과 달리 pivot이라는 임의의 기준값을 사용합니다.
피벗값을 설정하는 방법은 여러가지이지만 pivot값을 임의로 6이라고 설정
하겠습니다.

[5,2,3,4,1] < 6 < [9,7,8]

pivot = 6일 떄 pivot을 기준으로 나누어져 있기 때문에 각각 정렬을 하면 됩니다.

[5,2,3,4,1] 의 pivot값=4

[2,3,1] < 4 < [5]

[1,2] < 3 

[1] < 2 

[1,2,3,4] 로 정렬이 됩니다.

우측 정렬

[9,7,8] pivot = 7

7 < [8,9]

[8,9] p=9

8 < 9

[7,8,9]

양쪽 배열을 합쳐주면

[1,2,3,4,5,6,7,8,9]

즉 퀵정렬은 임의의 pivot값을 기준으로 divide하고 정렬한후 합쳐줌으로써
정렬해나가는 방식입니다.

알고리즘 :

  1. 피벗을 설정한다.
  1. 배열의 시작 인덱스를 left, 마지막 인덱스를 right라고 할 때,

    • pl은 left부터 시작하여 피벗보다 크거나 같은 값이 있을 때까지 오른쪽으로 이동한다.

      (단, pl이 right보다 작거나 같을때까지만 이동)

    • pr은 마지막부터 시작하여 피벗보다 작거나 같은 값이 있을 때까지 왼쪽으로 이동한다.

      (단, pr이 left보다 크거나 같을때까지만 이동)

  1. pl과 pr 이 이동을 멈추면, pl<=pr 이면 arr[pl] 과 arr[pr] 을 서로 교환(swap)한다.

    교환이 끝나면 pl은 오른쪽으로 하나 이동, pr은 왼쪽으로 하나 이동한다.

  1. pl과 pr이 교차할 때까지, 즉, pl > pr 일 때까지 2,3번을 반복한다.
  1. pl 과 pr이 교차하면,

    시작 인덱스를 left, 끝 인덱스를 pr로 하는 그룹으로 쪼개어서 1,2,3번 과정을 반복한다.

    (단, left < pr 조건을 만족해야 함)

    마찬가지로, 시작 인덱스를 pl, 끝 인덱스를 right로 하는 그룹으로 쪼깨어서 1,2,3번 과정을 반복한다.

    (단, pl < right 조건을 만족해야 함)

  1. 더 이상 작은 그룹으로 쪼갤 수 없으면 종료한다.

참고링크텍스트

0개의 댓글