퀵소트(QuickSort) 구현해보기 JAVA(자바)

퀵 소트 같은 경우 재귀적으로 피벗을 나누고 피벗보다 작은 값은 왼쪽 피벗보다 큰 값은 오른쪽으로

 

나누는 분할 정복에 의한 정렬 방법이다. 

 

 

 

 

 

 

 

	public class main {
	public static void main(String[] args) {
	ArrayList<Integer> a = new ArrayList<>();
	a.add(3);
	a.add(2);
	a.add(5);
	a.add(1);
	quickSort(a, 0, a.size() - 1);
	for(int A : a)
	System.out.print(A + " ");
	}
	public static void quickSort(ArrayList<Integer> a, int left, int right) {
	if (left <= right) {
	int mid = (left + right) / 2;
	int pivot = partition(a, left, mid, right);
	quickSort(a, left, mid - 1);
	quickSort(a, mid + 1, right);
	}
	}
	private static int partition(ArrayList<Integer> a, int left, int mid, int right) {
	int pivot = a.get(left);
	int lidx = left + 1;
	int ridx = right;
	while (lidx <= ridx) {
	while (a.get(lidx) <= pivot && lidx <= right) {
	lidx++;
	}
	while (a.get(ridx) >= pivot && ridx >= left + 1) {
	ridx--;
	}
	if (lidx <= ridx)
	swap(a, lidx, ridx);
	}
	swap(a, left, ridx);
	return ridx;
	}
	}

view raw .java hosted with ❤ by GitHub