반응형
  • 주어진 배열을 두 개로 분할하고, 정렬하는 알고리즘

  • MergeSort와의 차이점 1
    - MergeSort는 그냥 두 부분으로 나누는 반면에, QuickSort는 분할할 때,
      기준 피봇(pivot item) 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킨다.

  • MergeSort와의 차이점 2
    - 각 부분 정렬이 끝난 후, MergeSort는 "Merge"이란 후처리 작업이 필요하나,
      QuickSort는 필요로 하지 않는다.
    .

  • 시간복잡도 O(n²)
    - MergeSort보다 빠르지 않지만 평균 시간 복잡도가 nlogn이기 때문에 평균적으로 가장 빠르다.

구현코드

package Stack2;

import java.util.Arrays;

public class QuickSort2 {
	
	//퀵소트
	public static int[] a = {69, 10, 30, 2, 16, 8, 31, 22};
	
	public static int hoare(int begin, int end) {
		int P = a[begin];
		int L = begin;
		int R = end;
		while(L<R) {
			while(a[L]<= P && L<end  ) L++;
			while(a[R]>  P && begin<R) R--;
			if(L<R) {
				int T = a[R]; a[R] = a[L]; a[L] = T;
			}
		}
		
		int T = a[R]; a[R] = a[begin]; a[begin] = T;
		return R;
	}
	public static void quick(int begin, int end) {
		if(begin < end) {
			int p = hoare(begin, end);
			quick(begin,p-1);
			quick(p+1,end);
		}
	}
	public static void main(String[] args) {
		System.out.println(Arrays.toString(a));
		quick(0,a.length-1);
		System.out.println(Arrays.toString(a));
	}
}
반응형

'1. 알고리즘 이론 > 3. 정렬' 카테고리의 다른 글

병합정렬(MergeSort)  (0) 2020.03.01
카운팅정렬(CountingSort)  (0) 2020.03.01
삽입정렬(InsertionSort)  (0) 2020.03.01
선택정렬(SelectionSort)  (0) 2020.03.01
버블정렬(BubbleSort)  (0) 2020.03.01

+ Recent posts