[자료구조] 퀵정렬(quick sort), 합병정렬(merge sort)

이번에는 js로 퀵 정렬과 합병정렬을 짜보았습니다.

개인적으로 C로 짰을때는 배열의 인덱스라든지 배열의 크기라든지 구현하는데 불편했었는데, js로는 고민없이 생각대로 짜는게 쉬웠습니다. (맞습니다. 저 배열의 인덱스 그런게 참 복잡해서 잘 못하고 싫어합니다.)

우선 합병 정렬은 배열을 계속해서 두 그룹으로 분할하고, 분할이 완료되면 두 그룹을 합칠 때 순서대로 합치는 방식 입니다.

코드를 보면,

	const input = [3, 7, 2, 4, 1, 0, -4, 9, 0, 8, 5, 6, -1, -5];
	let d = [...input];
	const divide = (array) => {
	// console.log(`divide ${array}`);
	let divider = {
	arrayLeft: [],
	arrayRight: []
	};
	const centerIdx = Math.round(array.length / 2);
	array.forEach((item, index) => {
	if (index < centerIdx) {
	divider.arrayLeft.push(item);
	} else {
	divider.arrayRight.push(item);
	}
	});
	return divider;
	}
	const merge = (arrayL, arrayR) => {
	// console.log(`merge ${arrayL} , ${arrayR}`);
	let merged = [];
	let left = arrayL.shift();
	let right = arrayR.shift();
	while(left !== undefined && right !== undefined) {
	if(left < right) {
	merged.push(left);
	left = arrayL.shift();
	} else {
	merged.push(right);
	right = arrayR.shift();
	}
	}
	left === undefined ? merged.push(right) : merged.push(left);
	merged = merged.concat(arrayL).concat(arrayR);
	// console.log(`merged ${merged}`);
	return merged;
	}
	const mergeSort = (array) => {
	if (array.length == 1) {
	return array;
	} else {
	const divider = divide(array);
	return merge(mergeSort(divider.arrayLeft), mergeSort(divider.arrayRight));
	}
	}
	console.log(mergeSort(d));

view raw mergeSort.js hosted with ❤ by GitHub

조금은 복잡하게 느껴질 수도 있겠네요.  두 함수가 있습니다. 하나는 하나의 배열을 두 그룹으로 분할하는 함수고,

또 하나는 두 배열을 정렬된 하나의 배열로 만드는 함수 입니다. 

두 그룹으로 나눌때, 짝수라면 정확히 반반 나뉘겠지만, 홀수 일 때는 다른 크기의 그룹으로 나뉩니다. 그 처리를 위해 Math의 반올림 함수를 사용했습니다.

합병할 때는 지금 보니 조금 복잡하지만,, 두 개의 그룹에서 하나씩 꺼내서 비교하여 작은 값을 먼저 넣고 한쪽 배열을 모두 넣었다면, 나머지 배열의 값들을 모두 집어 넣습니다.

이 합병 정렬을 재귀호출을 하기 때문에 콜스택이 깊어지는 경향이 있습니다. 그리고 생각하기도 bubble이나, select 정렬에 비해 조금 복잡합니다.

다음 살펴볼 정렬을 퀵 정렬 입니다.

코드를 보면,

	const input = [3, 7, 2, 4, 1, 0, -4, 9, 0, 8, 5, 6, -1, -5];
	let d = [...input];
	const partitionate = function(arr) {
	const pivot = arr.shift();
	let partition = {
	pivot: pivot,
	left: [],
	right: []
	}
	for (let item of arr) {
	item > pivot ? partition.right.push(item) : partition.left.push(item);
	}
	// console.log('partition :', partition);
	return partition;
	}
	const merge = function(partition) {
	let merged = [];
	merged = partition.left ? merged.concat(partition.left) : merged;
	merged.push(partition.pivot);
	merged = partition.right ? merged.concat(partition.right) : merged;
	// console.log('merged : ', merged);
	return merged;
	}
	const quickSort = function(arr) {
	if(arr.length == 0) return;
	const partition = partitionate(arr);
	partition.left = quickSort(partition.left);
	partition.right = quickSort(partition.right);
	return merge(partition);
	};
	console.log(quickSort(d));

view raw quickSort.js hosted with ❤ by GitHub

합병 정렬과 유사하게 피벗을 기준으로 두 개의 그룹으로 나누는 partitionate와, 두 그룹과 피벗 값을 하나로 합치는 mege 함수가 있습니다.

코드가 합병 정렬보다 더 깔끔하게 짜여 진 것 같습니다... 이해는 쉽게 할 수 있을 것 같아서... 

for ... of 는 es6 문법으로  배열의 아이템을 도는 문법입니다.

다음 번엔 계수정렬(counting sort)로 찾아뵙겠습니다.