Algorithm, JAVA, 퀵정렬

퀵정렬

• 리스트 가운데서 하나의 원소를 고름(pivot 선정)
• pivot 앞에는 pivot보다 작은 값이 오고, pivot 뒤에는 pivot보다 큰 값들이 오도록 리스트를 둘로 분할한다.
• 분할된 두 개의 리스트에 대해 재귀함수를 통해 이 과정을 반복한다.
• 시간복잡도 : 최악 O(n^2), 평균 O(nlogn)

	static void swap(int[] a, int idx1, int idx2) {
		int tmp = a[idx1]; a[idx1] = a [idx2]; a[idx2] = tmp;
	}

	static void quickSort(int[] a, int left, int right) {
		int pl = left;			//왼쪽 커서
		int pr = right;			//오른쪽 커서

		int x = a[ (pl+pr)/2 ];	//피벗

		do {
			while(pl < x) pl++;
			while(pr > x) pr--;
			if(pl <= pr)
				swap(a, pl++, pr--);
		}while( pl<= pr ); 		// pl과 pr이 교차되면 중지.

		// 배열을 반복해서 나눠서 정렬한다.
		if(left < pr)	quickSort(a, left, pr);
		if(right > pl)	quickSort(a, pl, right);
	}

---

Reference

do it 자료구조와 함께 배우는 알고리즘 입문 자바 편

---