[자료구조] 정렬 - 버블, 선택, 삽입

js로 자료구조를 간단히 짜보려 한다. 그냥 단순히 리마인딩하기 위해 짜보는 거라 좋은 코드가 아닐 수 있다...

버블, 선택, 삽입 정렬은 빅오가 n^2이고, 간단하게 코드로 짤 수 있기 때문에 기본적인 정렬 아이디에서 자주 등장한다.

물론 자료가 많아지면, 매우 느린 단점이 있다. ( 어느정도 정렬된 형태면 그렇게 느리지 않지만,,)

버블 정렬

	const input = [3, 7, 2, 4, 1, 0, 9, 8, 5, 6];
	let d = [...input];
	const bubble = (array, index) => {
	if (index < 0 && index + 1 >= array.length ) {
	return;
	}
	if(array[index] > array[index + 1]) {
	let tmp = array[index];
	array[index] = array[index + 1];
	array[index + 1] = tmp;
	}
	}
	d.forEach(() => {
	d.forEach((item, index) => {
	bubble(d, index);
	});
	});
	console.log(d);

view raw bubble_sort.js hosted with ❤ by GitHub

버블 정렬은 이웃한 아이템들을 비교하며 왼쪽 값이 더 크다면 자리 변경을 하는데, 이러한 동작은 계속적으로 반복 하여 정렬하는 방식이다. 최악의 상황은

완전 반대로 값이 정렬되어 있을 때인데, 엄청 많이 반복해서 비효율이다.

선택 정렬

	const input = [3, 7, 2, 4, 1, 0, 9, 8, 5, 6];
	let d = [...input];
	const select = (array, index) => {
	if (array.length <= index || index < 0) {
	console.error('index error');
	console.log(index);
	return;
	}
	let minIdx = index;
	for (let i = index + 1; i < array.length; i++) {
	minIdx = array[i] < array[minIdx] ? i : minIdx;
	}
	return minIdx;
	}
	let selectIdx, tmpNumber;
	d.forEach((item, index, array) => {
	selectIdx = select(array, index);
	tmpNumber = array[index];
	array[index] = array[selectIdx];
	array[selectIdx] = tmpNumber;
	});
	console.log(d);

view raw select_sort.js hosted with ❤ by GitHub

맨 왼쪽부터 시작해서 이후의 남은 값중 가장 작은 값을 골라 변경하는 정렬. 뭔가 인간이 사용하는 직관적인 정렬 방식

삽입 정렬

	const input = [3, 7, 2, 4, 1, 0, 9, 8, 5, 6];
	let d = [...input];
	const chnage = (array, left, right) => {
	if(array[left] > array[right]) {
	let tmp = array[left];
	array[left] = array[right];
	array[right] = tmp;
	return true;
	} else {
	return false;
	}
	}
	const insert = (array, index) => {
	for (let i = index; i > 0; i--) {
	if(!chnage(array, i - 1, i)) {
	break;
	}
	}
	}
	d.forEach((item, index, array) => {
	insert(array, index);
	});
	console.log(d);

view raw insert_sort.js hosted with ❤ by GitHub

아이템을 정렬된 배열과 정렬안된 배열로 구분하여 아이템을 하나씩 가져오면서 정렬하는 방식,