[DataStruct] QuickSort

What

동작원리

1. 피봇 기준 정렬

2. 구간 나누기(왼쪽,오른쪽) 다시 1번으로

• Pivot 기준 왼쪽 구간에는 pivot 값보다 큰 값을 찾는다

• Pivot 기준 오른쪽 구간에는 pivot 값보다 작은 값을 찾는다

• 왼쪽구간과 오른쪽 구간이 겹치지 않으면 왼쪽 오른쪽 값을 맞바꾼다!

How

• 피봇의 기준이 왼쪽 또는 오른쪽인 경우는 pivot위치에 있는 값이 적절한 위치로 들어간다.

1. 가장 왼쪽



 

2. 가장 오른쪽

3. 중앙

Why

• Java를 쓰게 되면 Arrays.sort, Collections.sort 라는 메소드의 동작원리의 기반이 되는 정렬(dual-pivot quick sort, 혹은 TimSort(mergeSort + quickSort) )이다. 사용하는데 모르고 있어도 크게 상관 없지만 이처럼 라이브러리를 사용하면서 원리를 안다는 것은 좋은 습관이기 때문이다.

 Code

import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class QuickSort {
	static Scanner sc = new Scanner(System.in);
	
	public static void main(String[] args) {
		int n = Integer.parseInt(sc.nextLine());
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(sc.nextLine());
		}

		// quickSortByMiddlePivot(0, arr.length - 1, arr);
		quickSortByFirstPivot(0, arr.length - 1, arr);
		// quickSortByRightPivot(0, arr.length - 1, arr);
		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}
	}

	public static void quickSortByRightPivot(int s, int e, int[] arr) {
		if (s >= e)
			return;

		int pivotIndex = e;
		int l = s;
		int r = e - 1;

		while (l <= r) {
			while (l < e && arr[l] < arr[pivotIndex]) {
				l++;
			}

			while (r >= s && arr[r] > arr[pivotIndex]) {
				r--;
			}

			if (l < r) {
				swap(arr, l, r);
			} else {
				swap(arr, l, pivotIndex);
			}
		}

		quickSortByRightPivot(s, l - 1, arr);
		quickSortByRightPivot(l + 1, e, arr);
	}

	public static void quickSortByFirstPivot(int s, int e, int[] arr) {
		if (s >= e)
			return;

		int pivotIdx = s;
		int l = s + 1;
		int r = e;

		while (l <= r) {
			while (l <= e && arr[l] < arr[pivotIdx]) {
				l++;
			}

			while (r > s && arr[r] > arr[pivotIdx]) {
				r--;
			}

			if (l < r) {
				swap(arr, l, r);
			} else {
				swap(arr, r, pivotIdx);
			}
		}

		quickSortByFirstPivot(s, r - 1, arr);
		quickSortByFirstPivot(r + 1, e, arr);
	}

	public static void quickSortByMiddlePivot(int s, int e, int[] arr) {
		if (s >= e) {
			return;
		}

		int pivot = arr[(s + e) >> 1];
		int l = s;
		int r = e;

		while (l <= r) {
			while (arr[l] < pivot) {
				l++;
			}

			while (arr[r] > pivot) {
				r--;
			}

			if (l <= r) {
				swap(arr, l, r);
				l++;
				r--;
			}
		}

		quickSortByMiddlePivot(s, l - 1, arr);
		quickSortByMiddlePivot(l, e, arr);
	}

	static void swap(int[] arr, int a, int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
}

Refer

퀵 정렬이란?

1. 퀵 정렬 1-1. 퀵 정렬이란? 1-2. 예시 1-3. 소스코드 1-4. 퀵 정렬의 시간 복잡도 1-5. 퀵 정렬은 얼마나 빠를까? 1. 퀵 정렬 1-1. 퀵 정렬이란? 이름값 하는 정렬 방법이다. 평균적으로 꽤나 빠른 속도를 보여준다. 여기서 평균적으로라고 한 이유는 [목차 1-4]에서 설명할 예정이다. 아무튼 이렇게 빠르게 정렬할 수 있는 이유는 분할 정복 방법을 사용했기 때문이다. 분할 정복 방법이란 큰 문제를 작은 문제로 쪼개어 문제를 해결하는 방식이다. 한 번에 먹기에 너무 큰 음식이 있으면 잘라먹듯이 한 번에 들기에 너무 무거운 짐이 있으면 나눠 들듯이 큰 문제를 해결하기 쉬운 작은 문제로 쪼개자는 것이다. 퀵 정렬은 이 개념을 도입한 방법인데 어떻게 정렬되는 건지 다음 목차에서 알아보자..

https://todaycode.tistory.com/52

2750번: 수 정렬하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

https://www.acmicpc.net/problem/2750