[알고리즘] 퀵 정렬

[알고리즘] 퀵 정렬

파티셔닝을 이용한 정렬방법

1. 기준값을 정한다.

2. 첫번째부터 차례로 비교해나가면서

기준값보다 작으면 왼쪽 그룹의 끝자리+1과 위치를 바꾼다.

퀵 정렬 이미지

퀵 정렬의 수도코드

수행시간

Balanced Partitioning : 파티셔닝의 크기가 n/2로 줄어드는 경우

=> 높이 logN * 각 층별 N번의 연산을 수행

=> O(NlogN)

UnBalanced Partitioning : 파티셔닝의 크기가 1과 n-1개로 줄어드는 경우

=> 높이 N-1 * 각 층별 N-1번의 연산을 수행

=> O(N²)

* Unbalanced Partitioning(최악의 경우)를 피하기 위해 파티셔닝의 크기를 랜덤하게 가져가는 Randomized QuickSort가 등장함.

JAVA

package algorithm; import java.util.Arrays; public class QuickSort { static int[] arr; static int[] tmp; public void quickSort(int start, int end) { if(start 가장 끝 값 /*하나씩 돌면서 pivot과 비교 > pivot보다 작으면 위치 바꾸기 */ for(int i = start; i

반응형

from http://hodubab.tistory.com/354 by ccl(S) rewrite - 2021-09-10 05:01:34