퀵 정렬(Quick Sort)

배열을 2개의 문제로 쪼갠 후 정렬하고 다시 더하는데 이것을 반복하여 정렬된 배열을 만든다.

그냥 일반적인 2중 for문의 정렬(선택 정렬)보다 평균적으로 훨씬 더 빠르다.

2중 반복문 사용 오름 차순 정렬(선택 정렬)

let arr = [4,6,1,3,7,9,2,5,8];
let count = 0;

function sort () {
	let result = [...arr];
	for(let i = 0; i < result.length; i++){
		for(let j = i+1; j < result.length; j++){
			count++;
			let temp = result[i]
			result[i] >= result[j] 
			? (temp = result[i], result[i] = result[j], result[j] = temp)
			: undefined;;
		}
	}
	return result;
}

console.log(sort(arr));     //[1,2,3,4,5,6,7,8,9]
console.log(count);			//36; 

퀵 정렬 사용 오름 차순 정렬

let arr = [4,6,1,3,7,9,2,5,8];
let count = 0;

function quick(arr) {
	if(arr.length <= 1) return arr;
	let left = [];
	let right = [];
	let comp = arr[0];
	for(let i = 1; i < arr.length; i++){
		count++;
		comp <= arr[i] ? right.push(arr[i]) : left.push(arr[i]);
	}
	return [...quick(left),comp,...quick(right)];
}

console.log(quick(arr));    //[1,2,3,4,5,6,8,9]
console.log(count);			//18

위 두 가지의 경우를 비교해 보면

첫 번째 2중 for문 사용 시 맨 처음의 배열의 요소와 그 다음 배열의 요소부터 끝 까지 전부 비교하여 가장 작은 값을 차곡차곡 쌓아간다.

즉 맨 처음부터 9개, 8개, 7개… 이런 식으로 비교해 가며 가장 작은 값들을 찾아내어 쌓는 방식이다.

두 번째 퀵 정렬 알고리즘은 comp 라는 변수를 입력 받은 배열의 첫 번째 인자로 받아 그 값을 기준으로 comp 보다 작으면 left 에, 크면 right 에 저장하여 다시 그 값들을 재귀 적으로 quick함수에 넣어 주는 방식이다.

사실 첫 번째 정렬도 선택 정렬이라는 알고리즘이다. 안정적인 정렬에 속하지만 속도가 매우 느리다.

최선의 시간, 평균적인 시간, 최악의 시간 모두 입력 받은 배열의 길이 즉 시간 복잡도 O(N^2)을 가진다.

두 번째 퀵 정렬 알고리즘은 최선의 시간, 평균의 시간 모두 O(N x log N)이라는 빠른 속도를 가지고 있지만, 최악의 경우 버블 정렬과 같은 O(N^2)이라는 시간을 가질 수 도 있다.

하지만 퀵 정렬의 단점이 존재하는데 위에서 최악의 경우 일단 O(N^2)이라는 것과 불안정 정렬에 속한다.

불안정 정렬이란 같은 값을 가진 배열 안 요소들이 비교 되어서 정렬 될 때 그 순서가 보장되지 않는다.

좀 더 쉽게 말하면 위 에서 의 경우 배열 안에 숫자만 입력되었기 때문에 같은 값이 여러 개 존재하더라도 그 순서가 바뀌어도 상관은 없다.

하지만 배열의 원소들이 각각 의 정보를 가지고 있는 객체라고 가정하고 price라는 key값을 가지고 정렬을 했을 경우 같은 price 값을 가진 요소들 끼리 의 순서를 보장 할 수 없다는 것이다.