퀵정렬

기준이 되는 원소 하나를 고르고 이것보다 작은 앤 왼쪽 큰건 오른쪽에 옮겨 파티션을 쪼개고, 각각의 파티션을 정렬시켜 결국엔 정렬된 전체 배열을 얻게 하는 소팅방법.

• 평균 시간복잡도 : O(nlogn)

• 파티션을 나누고 나누다 보면 결국 N번 쪼개야 된다는 것을 알수 있다.

• 파티션을 나눌때마다 검색해야할 데이터의 양이 절반씩 줄어듦으로 logn

• 최악의 시간복잡도 : O(n^2)

• pivot을 뽑을때마다 제일작은 값을 뽑는다면 한쪽만 큰 배열을 갖는 비대칭적인 구조를 가지게 되어 결국 sort하는 과정에서 n번 탐색하게되어 n^2을 갖는다.

public class Main {
public static void quickSort(int[] arr) {
	quickSort(arr,0,arr.length-1);
}
public static void quickSort(int[] arr,int start,int end) {
	int part2=partion(arr,start,end); // 파티션을 쪼개 오른쪽파티션 첫번째인덱스값을 받음
	
	if(start<part2-1) //오른쪽파티션이 시작점바로 다음에서 시작한다면 왼쪽 파티션의 데이타가 하나뿐이라면 더이상 정렬할 필요가 없다.
		quickSort(arr,start,part2-1);
	if(part2<end) 
		quickSort(arr,part2,end);	
}
private static int partion(int[] arr,int start,int end) {
	int pivot=arr[(start+end)/2];
	
	while(start<=end) {
		while(arr[start]<pivot)start++; //왼쪽파티션의 원소가 기준값보다 작다면 있어야할자리니 다음인덱스를 검토
		while(arr[end]>pivot)end--; //오른쪽파티션의 원소가 기준값보다 크다면 있어야할 자리이니 다음인덱스(<-)를 검토
		if(start<=end) { //start가 end의 영역을 침범했거나 end가 start영역을 침범한경우가 아니라면 정상
			swap(arr,start,end); //둘의 위치를 바꿔준다(있어야할 원소들이 아니니까)
			start++; //그리고 그다음원소가 담아있다면 아직검토를 안했으니 start와 end의 인덱스를 항방향씩 가준다.
			end--;
		}
	}
	return start; // 위 반복문이 끝났다면 start<=end 조건문에 부합되지 않으므로 start는 pivot보다 1값이 더큰값을가진다.
}

private static void swap(int[] arr,int start,int end) {
	int tmp=arr[start];
	arr[start]=arr[end];
	arr[end]=tmp;
}
	public static void main(String[] args) {
		
	}
}