퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

Algorithmday_4 정리 (2021.12.01 수요일)

퀵 정렬(Quick Sort)

분할 정복 정렬 방법 중 하나

전체 리스트를 2개의 부분 리스트로 분할하고

각각의 서브 리스트를 다시 퀵 정렬로 정렬 기준 값보다 큰 값들은 오른쪽으로, 작은 값들은 왼쪽으로 재 배열

정렬 방법 전체 리스트에서 한 원소를 기준 값(pivot)으로 선정 피벗을 기준으로 두 개의 서브 리스트로 분할 왼쪽 : 피벗보다 작은 값의 원소들로 구성 오른쪽 : 피벗보다 크거나 같은 값의 원소들로 구성 각각의 파티션(서브 리스트)에 대해 다시 퀵 정렬을 순환 적용 피벗 선정 및 파티션 분할

퀵 정렬 수행 순서

피벗(pivot) : 가장 왼쪽 숫자를 피벗으로 선정

두 개의 변수 : low와 high(이동) low는 왼쪽에 위치 high는 오른쪽에 위치

low : 오른쪽으로 이동하면서 피벗 보다 큰 숫자를 찾음 피벗 보다 작으면 통과, 큰 숫자를 찾으면 정지

high : 왼쪽으로 이동하면서 피벗 보다 작은 숫자를 찾음 피벗 보다 크면 통과, 작은 숫자를 찾으면 정지

정지된 위치의 숫자들 서로 교환

low와 high가 교차하면 종료. high와 pivot 교환

퀵 정렬 예제 코드

QuickSort.java

public class QuickSort { public static void main(String[] args) { int [] arr = {8,5,4,6,3,1,2,7,9}; quickSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } static void quickSort(int[] arr, int low, int high) { if(low >= high) { return; } int pivot = low; int i = low + 1; int j = high; int temp; while(i <= j) { // 교차할 때 까지 반복 j가 i보다 크면 while문 종료 while(i <= high && arr[i] < arr[pivot]) { // 피벗보다 큰 값을 만날 때 까지 반복 i++; } while (j > low && arr[j] >= arr[pivot]) { // 피벗보다 작은 값을 만날 때 까지 반복 j--; } if(i > j) { // 교차한 상태가 되면 피복과 j 교환 temp = arr[j]; arr[j] = arr[pivot]; arr[pivot] = temp; } else { // i와 j값 교환 temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } quickSort(arr, low, j-1); quickSort(arr, j+1, high); } }

from http://5bong2-develop.tistory.com/59 by ccl(A) rewrite - 2021-12-01 13:27:36