[Algorithm] Quick Sort(퀵 정렬)
[무료] 알고리즘의 개요와 실습 환경 구축 - 인프런 | 강의
알고리즘을 배우며, 실무에서는 알고리즘이 어떻게 활용되는지 알아봅니다., [임베딩 영상] 알고리즘의 개요와 실습 환경 구축 알고리즘은 문제를 해결하는 절차입니다.입력, 출력, 유한성, 명
www.inflearn.com
위 강의의 5, 6강 퀵 정렬에 대한 리뷰이다.
재귀 함수를 이용해서 그런가 돌아가는 원리가 마치 플라나리아 재생실험 보는 느낌이었다.
쪼개지면서 정렬의 반복
#include <stdio.h>
int number = 10;
int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
//int array[10] = {3, 7, 8, 1, 5, 9, 6, 10, 2, 4}
void show() {
int i;
for (i = 0; i < 10; i++) {
printf("%d ", array[i]);
}
}
void quickSort(int *data, int start, int end) {
if (start >= end) { // 원소가 1개인 경우 그대로 두기
return;
}
int key = start; // 키는 첫번째 원소
int i = start + 1;
int j = end;
int temp;
while (i <= j) { // 엇갈릴 때까지 반복
while(data[i] <= data[key]) { // 내림차순은 while(data[i] >= data[key])
i++; // 큰값 만날 때까지 우측 이동
}
while(data[j] >= data[key] && j > start) { // 내림차순은 while(data[j] <= data[key] && j > start)
j--; // 작은값 만날 때까지 좌측 이동
}
if (i > j) {
// 엇갈린 경우(순서가 잡힌 경우) 키값교체
temp = data[j];
data[j] = data[key];
data[key] = temp;
} else {
// 그 외는 swap
temp = data[j];
data[j] = data[i];
data[i] = temp;
}
}
// 재귀를 이용하여 각각 정렬 (분할 정복!)
quickSort(data, start, j - 1);
quickSort(data, j + 1, end);
}
int main(void) {
quickSort(array, 0, number - 1);
show();
return 0;
}
처음에 강의만 들었을 때는 왜 퀵정렬의 시간복잡도가 일반적으로 N * logN 인지 이해가 안 갔다. 구글링하다가 아래 블로그를 보고 얼추 이해하게 되었다.
https://zeddios.tistory.com/35
정렬 알고리즘 - Quick Sort (평균- nlogn, 최악- n^2)
안녕하세요 정렬 알고리즘1 글을 써놓고 2는 바빠서 못썼네요ㅎㅎ.. 오늘은 퀵정렬만 정리해보려고 합니다. 퀵정렬은 개념을 아예 모르시는 분들이 보면 이해하기가 처음엔 힘들어요. 그래서
zeddios.tistory.com
특히 이 설명이 너무나도 압권이었음
최악의 경우에 시간복잡도가 n^2 이 나오는데 그 경우는 정렬할 샘플이 오름차순 혹은 내림차순으로 이미 정렬이 되어 있는 경우다.
분할 없이 숫자를 모두 훑으며 (다시) 정렬하기 때문에 n^2 가 나오는 것 같다.
이해해보려고 위 gif만 계속 들여다 봤다.
C++ 소스를 Java로 바꾸면
public class Sort
{
private static void quickSort(int[] data, int start, int end) {
if (start >= end) {
return;
}
int key = start;
int i = start + 1;
int j = end;
int temp;
while (i < j) {
while (i < data.length && data[i] < data[key]) {
// index 에러나서 i < data.length 추가함
i++;
}
while (data[j] > data[key] && j > start) {
j--;
}
if (i > j) {
temp = data[j];
data[j] = data[key];
data[key] = temp;
} else {
temp = data[j];
data[j] = data[i];
data[i] = temp;
}
}
quickSort(data, start, j - 1);
quickSort(data, j + 1, end);
}
public static void main(String[] args) {
int[] array = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
quickSort(array, 0, array.length - 1);
for (int i = 0; i < array.length; i++) {
System.out.printf("%d ", array[i]);
}
}
}
이렇게 된다.
javascript 로 바꾼다면
function quickSort(data, start, end) {
if (start >= end) return;
let key = start;
let i = start + 1;
let j = end;
let temp;
while (i < j) {
while (i < data.length && data[i] < data[key]) {
i++;
}
while (data[j] > data[key] && j > start) {
j--;
}
if (i > j) {
temp = data[j];
data[j] = data[key];
data[key] = temp;
} else {
temp = data[j];
data[j] = data[i];
data[i] = temp;
}
}
quickSort(data, start, j - 1);
quickSort(data, j + 1, end);
}
function sort() {
let array = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9];
quickSort(array, 0, array.length - 1);
console.log(array.join(", "));
}
sort();
이렇게 바꿀 수 있다.
아래 코드의 경우 중간값을 피벗값으로 정한 뒤 그 값을 기준으로 분할 정렬한다.
참고를 위해 들고와 봄
function quickSort (array, left = 0, right = array.length - 1) {
if (left >= right) {
return;
}
const mid = Math.floor((left + right) / 2);
const pivot = array[mid];
const partition = divide(array, left, right, pivot);
quickSort(array, left, partition - 1);
quickSort(array, partition, right);
function divide (array, left, right, pivot) {
console.log(`array: ${array}, left: ${array[left]}, pivot: ${pivot}, right: ${array[right]}`)
while (left <= right) {
while (array[left] < pivot) {
left++;
}
while (array[right] > pivot) {
right--;
}
if (left <= right) {
let swap = array[left];
array[left] = array[right];
array[right] = swap;
left++;
right--;
}
}
return left;
}
return array;
}출처: https://im-developer.tistory.com/135 [Code Playground]