..

Quick Sort

Concept

정렬이 안된 배열이 있을때 아무 값이나 잡고 해당 값보다 작은 값들은 왼쪽(Smaller), 큰 값들은 오른쪽(Bigger)으로 옯긴다. 이렇게 하면 배열이 partition 두개로 나뉘게 된다.

작은쪽(smaller)에서 아무 값이나 잡는다. 그 기준값으로 작은 값들은 왼쪽, 큰 값들은 오른쪽 으로 옮긴다.

작은쪽(smaller)와 큰쪽(bigger)가 정렬이 되었다면 최종 적으로도 모든 배열의 값들이 정렬이 되어 있을 것이다.

계속 쪼개다보면 partition의 배열방이 딱 2개만 남는 경우가 생긴다 두개중에 하나를 기준 값으로 정렬

Time Complexity (시간 복잡도)

  • O(n log n)
    • n - partition을 나누는 횟수
    • log n - 한번 나눌때 마다 검색할 데이터가 절반씩 줄어 든다
  • Worst - O(n^2)

Worst-case

적용

Partitioning

  • Pivot을 정한다 (값이 중간에 가까울 수록 좋지만 이것은 랜덤..)
  • 배열의 양 끝에 start 와 end 포인터를 지정한다
    • start pointer - pivot 값보다 작은 값들을 무시하면서 뒤로 이동, 작지 않으면 잠시 멈춘다
    • end pointer - pivot 값보다 큰 값들을 무시하면서 앞으로 이동, 크지 않으면 잠시 멈춘다

  • start는 pivot(5)보다 큰수를 만나 잠시 멈추고 end를 움직여준다. 현재는 end의 값이 pivot(5)보다 작음으로 멈춘다.

  • Start와 end의 값을 Swap 해준다.
  • 그 후 각 포인터를 한개씩 옮겨준다

  • start의 값이 pivot 값보다 크니 start는 여기서 기다린다.

  • end도 같은 방식으로 움직여 준다

  • end가 pivot 값 보다 작은 시점에서 start와 end의 값을 Swap 해준다. 그리고 포인터를 하나씩 움직여 준다.

  • start와 end값을 Swap 해준다

  • 포인터를 한칸 씩 옮겨준다
  • 이때 start와 end가 서로 정한 범위를 벗어나게 된다 -> 반복문의 조건에 맞지 않다
  • 현재 start가 가리키는 배열 방이 두번째 partition의 첫번째 배열방이다. 해당 index를 함수의 값으로 반환해준다

  • partition이 진행된 이후에는 pivot(5)보다 작은 그룹, 큰 그룹으로 나뉘게 된다

partitioning 이 안일어나는 경우

  • 양쪽 partition의 데이터가 1개 이상 있는 경우는 또 정렬을 해야하니 양쪽 배열방의 range를 가지고 반복적으로 quicksort함수를 재귀적으로 호출해준다.
  • 만약 2가 pivot이라면 왼쪽 partition의 경우는 데이터가 1개 이므로 재귀호출을 진행하지 않는다.

Recursion

  • 기준값(pivot)을 세우고 그 값을 기준으로 partition을 작은수(smaller)와 큰수(bigger)로 나눈다.
  • 계속 나누다가 partition방이 1개인 경우가 되면 모든 값들이 정렬이 되게 된다.

Quick Sort 구현




public class Test {
	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);  // partition을 나누고 오른쪽 방의 첫번째 값(index)을 받아온다
		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;
	}

	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){
		int[] arr = {3,9,4,7,5,0,1,6,8,2};
		printArray(arr);
		quickSort(arr);
		printArray(arr);
	}
}

출력 로그

3, 9, 4, 7, 5, 0, 1, 6, 8, 2,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,