[알고리즘] 퀵정렬 - 피봇 중심으로 왼쪽, 오른쪽 정리

퀵 정렬

기준 값을 중심으로 왼쪽과 오른쪽 부분집합으로 정렬

기준 값을 피봇(Pivot)이라고 함

첫번째 가운데 혹은 마지막에 위치한 원소 선택

 

분할

기준값(피봇) 중심으로 2개의 부분집합으로 분할

 

정복

기준값 기준 작은 원소 왼쪽, 큰 원소 오른쪽으로

부분집합의 크기가 1일 될때까지 반복

 

규칙

Left는 피봇보다 작으면 통과, 크면 정지

Right는 피봇보다 크면 통과, 작으면 정지

 

예시

첫 번째 원소 52를 피봇이라고 하자

• 52(피봇), 33, 87, 47, 99, 4, 65, 26, 77
• 33을 Left로 표시, 77은 Right로 표시
• 52와 33(Left) 비교해보니 33이 작다 그러니 Left를 87로
• 52와 77(Right) 비교해보니 77이 크다 그러니 Right을 26으로 이동

 

현재 상황

52(피봇), 33, 87(Left), 47, 99, 4, 65, 26(Right), 77

다시

피봇인 52와 87(Left)을 비교, 87이 크다

피봇인 52와 26(Right)을 비교, 26이 작다

어떻게 할까?

87과 26 둘 자리를 바꿔준다.

 

다시 현재 상황을 알아보자

52(피봇), 33, 26, 47(Left), 99, 4, 65(Right), 87, 77

그럼 다시 시작

52와 47을 비교, Left인 47이 작다

52와 65를 비교, Right인 65가 크다

그럼 통과(다음 Left와 Right)로 넘어간다

 

현재 상황

52(피봇), 33, 26, 47, 99(Left), 4(Right), 65, 87, 77

다시 비교 시작

피봇인 52와 Left인 99를 비교, Left가 크다 그럼 기다려

피봇과 Right를 비교 해보니, Right가 작다 그럼 잘됐다 둘이 바꾸자

 

바꾸고 나니

52(피봇), 33, 26, 47, 4(Left), 99(Right), 65, 87, 77

이렇게 Left와 Right가 만나면 정지된다.

그리고 피봇과 Left의 값을 바꿔준다.

 

정리하자면 이런 상황

4, 33, 26, 47, 52, 99, 65, 87, 77

피봇인 52를 기준으로 작은 왼쪽 4개로 이루어진 부분집합, 큰 오른쪽 4개의 부분집합이 된다.

 

부분집합이 1개가 될때까지 반복한다

 

효율성

자리 교환 횟수가 줄어들어

실행 시간 성능이 좋은 정렬 방법중 하나