Quick Sort

시간 복잡도

O(N log n) 최악의 경우 O(N^2)

 

3

9

4

7

5

0

1

6

8

2

 

퀵 솔트 알고리즘 규칙

 

start 와 end로 arr을 나눈후 mid = (start + end)/2 를 정한다. Pivot

 

Pivot을 기준으로 왼쪽은 pivot보다 작은값 오른쪽은 pivot보다 크거나 같은 값으로 한다.

 

1. start는 pivot 보다 작으면 넘어간다. 아니면 잠시 멈춘다.

 

2. end는 pivot 보다 크거나 같으면 그냥 넘어간다.

 

3. swap 한다 그리고 start++ end -- 한다.

 

4. 1~3과정을 start<end 를 만족할 때 까지 반복한다.

 

5. 기준이되는 start의 위치를 반환한다.

 

package sasum;

public class myTest {
	private static void quickSort(int[] arr) {
		quickSort(arr, 0, arr.length - 1);
	}

	private static void quickSort(int[] arr, int start, int end) {
		int part2 = partition(arr, start, end);
		if (start < part2 - 1) {
			quickSort(arr, start, part2 - 1);
		}
		if (part2 < end) {
			quickSort(arr, part2, end);
		}

	}

	private static int partition(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) {
				swap(arr, start, end);
				start++;
				end--;
			}
		}
		return start;
	}

	public static void swap(int[] arr, int start, int end) {
		int tmp = arr[start];
		arr[start] = arr[end];
		arr[end] = tmp;
	}
	
	public static void printArray(int[] arr) {
		for(int data : arr) {
			System.out.print(data + ", ");
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		int[] arr = {3,9,4,7,5,0,1,6,8,2};
		printArray(arr);
		quickSort(arr);
		printArray(arr);
	}
}

 

(start ~ part2-1)     (part2   ~ end) 나누어서 재귀로 실행