알고리즘 - Quick sort

quick sort에 대해서

Posted by Yan on March 11, 2021

퀵정렬

  • 배열을 절반으로 나누어서 왼쪽, 오른쪽을 따로 정렬. 다시 그 나눈 부분을 같은 방식으로 재귀적인 정렬.

  • 파티션을 기준으로 계속해서 두 파트로 나누고 결국에는 배열을 하나하나 쪼갤 때까지 가는 것임.

  • 평균 속도 O(nlogn)

  • 최악의 속도 O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Sort {
	static void quickSort(int[] arr) {
		//get array and set parameter as arr, starting index, ending index
		quickSort(arr, 0, arr.length-1);
	}

	static void quickSort(int[] arr, int start, int end) {
		int part2 = partition(arr, start, end);
		//make a partition index by using pivot

		if(start < part2 -1) {
			// if part1 have only one index, there's no need to sort it
			quickSort(arr, start, part2-1);
			// if part1 is more than one index, set ending index to part2-1
			// and recursively call quickSort
		}

		if(part2 < end) {
			// if part2 starting index is larger than ending index, there's nothing to sort
			quickSort(arr, part2, end);
		}
	}

	static int partition(int[] arr, int start, int end) {
		int pivot = arr[(start+end)/2];
		//make pivot in the center of index

		while(start <= end) {
			while (arr[start] < pivot) start++;
			// while quickSort is keep calling, keep changing starting index indeed
			while (arr[end] > pivot) end--;
			// while ending index is exceeding the range, ending point need to be smaller
			if (start <= end) {
				swap(arr, start, end);
				start++;
				end--;
			}
		}
		return start;
	}

	static void swap(int[] arr, int start, int end) {
		int tmp = arr[start];
		// make a variable for swap value
		arr[start] = arr[end];
		arr[end] = tmp;
	}

	static void printArray(int[] arr) {
		System.out.println(arr);
	}
}