알고리즘 서론 의 자바 실현 - 7. 빠 른 정렬

1. 빠 른 정렬

/*
 *      
 */
import java.util.Comparator;
public class QuickSort {

	public static  int partition(T[] a, Comparator super T> c, int p,int r)
	{ 
		T t = a[r-1];
		int i = p-1;
		for(int j=p;j void quickSort(T[] a, Comparator super T> c)
	{
		quickSort(a,c,0,a.length);
	}
	public static  void quickSort(T[] a, Comparator super T> c,int p, int r)
	{
		int q = 0;
		if(p()
		{
			public int compare(Integer o1,Integer o2)
			{
				return o1-o2;
			}
		});
		
		for(int i:temp)
		{
			System.out.print(i + " ");
		}
	}

}

출력 결과: 2445 6 7 8 
2. 빠 른 정렬 의 에 세이 버 전

/*
 *            
 */
import java.util.Comparator;
import java.util.Random;
public class Randomized_quicksort {

	/**
	 * @param args
	 */
	public static  int partition(T[] a, Comparator super T> c, int p,int r)
	{ 
		T t = a[r-1];
		int i = p-1;
		for(int j=p;j int randomizedPartition(T[] a, Comparator super T> c, int p, int r)
	{
		int i = new Random().nextInt(r-p)+p;
		T temp = a[i];
		a[i] = a[r-1];
		a[r-1] = temp;
		
		return partition(a,c,p,r);
	}
	
	public static  void randomized_QuickSort(T[] a, Comparator super T> c)
	{
		randomized_QuickSort(a,c,0,a.length);
	}
	public static  void randomized_QuickSort(T[] a, Comparator super T> c, int p,int r)
	{
		if(p()
		{
			public int compare(Integer o1, Integer o2)
			{
				return o1-o2;
			}
		});
		
		for(int i:temp)
		{
			System.out.print(i + " ");
		}
	}

}

출력 결과: 1, 3, 5, 12, 23, 34, 689 
3.  복잡 도 분석
(1) 가장 좋 은 상황 에서 파 티 션 은 매번 고 르 게 나 뉜 다.
 
   이때: T (n) = 2 T (n / 2) + (n - 1) ; // 필기 1 에서 우 리 는 이 해 가 nlog (n) 라 는 것 을 안다.
  그래서 빠 른 정렬 의 가장 좋 은 상황 은? nlog(n)
 
(2) 최 악의 경우 partiation 은 매번 이러한 [x] [n - 1 개 요소] 를 구분 하 는 것 과 유사 하 다.
 
이때: T (n) = T (n - 1) + (n - 1) ;   //  이것 은 n^2 
 
(3) 일반적인 상황 에서 파 티 션 은 편 파 적 으로 나 뉘 더 라 도 예 를 들 어 1 / 10 위치 로 나 뉜 다.
 
  이때 T (n) = T (1 / 10) + T (9 / n) + n - 1,  이것 도 nlog (n)
 
(4) 그래서 평균 상황 에서 빠 른 정렬 의 복잡 도 는? nlog(n)