# 퀵 정렬 ## 목차 --- 1. 무엇? 2. 특징? 3. 알고리즘 ## 1. 무엇? --- 분할 정복 알고리즘의 하나. 1. 리스트 가운데 하나를 고름(피벗) 2. 분할 - 피벗 앞에는 이보다 작은 리스트를 만들고, 뒤에는 이보다 큰 리스트를 만듬 3. 분할을 마친 피벗은 위치 고정 4. 분할 된 두 리스트에 대해 위 과정(1-3)을 재귀적으로 반복 ## 2. 특징? --- - 빠름, 시간 복잡도 O(n log n) - 메모리 지역화(localization) 효과로, 상당히 빠르게 동작 - 추가 메모리 필요, 공간 복잡도 O(log n) ## 3. 알고리즘 ---  ### 소스코드 ``` public void quickSort(int[] arr, int left, int right) { int i, j, pivot, tmp; if (left < right) { i = left; j = right; pivot = arr[(left+right)/2]; //분할 과정 while (i < j) { while (arr[j] > pivot) j--; // 이 부분에서 arr[j-1]에 접근해서 익셉션 발생가능함. while (i < j && arr[i] < pivot) i++; tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } //정렬 과정 quickSort(arr, left, i - 1); quickSort(arr, i + 1, right); } } ```