Sorting 알고리즘

코드를 짜는 과정에서 데이터를 일정한 기준에 맞춰 나열하는 '정렬(Sort)'은 가장 기초적이면서도 필수적인 개념이다.

이번 기회에 다양한 정렬 알고리즘의 핵심 원리와 작동 방식을 공부해보고 각 알고리즘을 코드로 하나씩 직접 구현해 보았다.

Big O 표기법

• 알고리즘의 퍼포먼스 나타내는 표기법
• Big O 표기법은 시간 복잡도를 다룸
  • 시간 복잡도 : 알고리즘 실행 속도
  • 공간 복잡도 : 알고리즘을 수행할 때 필요한 공간 (리소스)
• 데이터 입력 n
• (faster) O(1) < O(logn) < O(n) < O(n log n) < O(n²) < O(2ⁿ) (slower)

이 글에서 다루는 정렬을 시간 복잡도 순으로 나열하면 아래와 같다.

1. 버블 정렬 – O(n²)
2. 선택 정렬 – O(n²)
3. 삽입 정렬 – O(n²) 
4. 퀵 정렬 – O(n log n)
5. 합병 정렬 – O(n log n)

선택 정렬 (Selection sort)

• 첫번째 인덱스부터 시작해 전체 배열에서 현 인덱스 값보다 작은 값과 위치를 바꿈
• for문을 두 번 사용함으로 시간 복잡도는 O(n²)

const arr = [1,2,3,4,5,6,7,8,9,10];
const test =  arr.sort(() => Math.random() - 0.5);
const length = test.length;
document.write('origin data : ', test)

let curNum, curIdx, changeIdx, maxGap;

for(let i = 0; i < length; i++){  
  if(i === (length - 1)) break; // 마지막 값일 경우 제외
  
  curNum = test[i]; // 현재 값
  curIdx = i; // 현재 인덱스 
  changeIdx = null; // 바꿀 인덱스
  maxGap = 0; // 현재 값과 차이가 많이 나는 값 갱신
  
  for(let j = curIdx + 1; j < length; j++){ // 현재 인덱스 다음 값부터 루프
    const gap = curNum - test[j];
  
    if(gap > 0 && maxGap < gap){
      changeIdx = j;
      maxGap = gap;
    }
  }
  
  if(changeIdx !== null){
    const num = test[curIdx];
    test[curIdx] = test[changeIdx];
    test[changeIdx] = num;
  }
}

document.write('<br />----<br />')
document.write('result data : ', test)

 

삽입정렬 (Insertion sort)

• 두번째 인덱스 부터 시작하여 i번째 원소를 1부터 i-1까지 비교해 적절한 위치에 삽입하는 방식
• for문을 두 번 사용함으로 시간 복잡도는 O(n²)

const arr = [1,2,3,4,5,6,7,8,9,10];
const test =  arr.sort(() => Math.random() - 0.5);

const length = test.length;
document.write('origin data : ', test)

let curIdx, insertIdx;

for (let i = 1; i < length; i++) { // 두번째 위치부터 시작
  curIdx = i; // 현재 인덱스
  insertIdx = null; // 삽입할 인덱스

  for (let j = curIdx - 1; j > -1; j--) { // 현재 인덱스 이전값 부터 작아지게 루프
    if (test[curIdx] < test[j]) {
      insertIdx = j;
    }
  }

  if(insertIdx !== null){
  	test.splice(insertIdx, 0, test[curIdx]); // 
  	test.splice(curIdx+1, 1);
  }
}

document.write('<br />----<br />')
document.write('result data : ', test)

 

버블 정렬 (Bubble sort)

• 첫번째 인덱스부터 시작해 연속된 두 인덱스를 비교하여 더 작은 수가 왼쪽에 위치하도록 함으로 제일 큰 수부터 정렬하는 방식
• for문을 두 번 사용함으로 시간 복잡도는 O(n²)

const arr = [1,2,3,4,5,6,7,8,9,10];
const test =  arr.sort(() => Math.random() - 0.5);
 
const length = test.length;
document.write('origin data : ', test)

let idx1, idx2;

for (let i = 0; i < length; i++) {
  for (let j = 0; j < length-i; j++) {
    idx1 = j;
    idx2 = j+1;
    if (test[idx2] < test[idx1]) {
      const num = test[idx2];
      test[idx2] = test[idx1];
      test[idx1] = num;
    }
  }
}

document.write('<br />----<br />')
document.write('result data : ', test)

 

4. 퀵 정렬

• 배열 내에 임의 기준 pivot 값을 정하고 pivot을 기준으로 두 개의 부분 집합으로 나눈다.
  왼쪽에는 pivot 보다 작은 값을 오른쪽에는 큰 값을 이동시키고 또 나눈 부분에서 임의 pivot을 정하는 등으로 반복하며 정렬하다 나눈 집합의 개수가 1이 될 때 멈추도록 한다.
• 시간 복잡도는 O(n log n)

// 맨끝 숫자를 pivot으로 했을때
const swap = (array, front, back) => {
	const tmp = array[front];
	array[front] = array[back];
	array[back] = tmp;
}

const lomutoPartition = (array, start, end) => {
	const pivot = array[end]; // 맨끝이 pivot
	let idx = start;

	for (let i = start; i < end; i++) {
  
		if (array[i] < pivot) { // pivot보다 작으면 
			swap(array, i, idx);	
			idx++; // idx 증가
		}
  }

	swap(array, idx, end); // pivot을 중간에 오게하기 위해서
	return idx;
}

const quickSort = (array, start = 0, end = array.length - 1) => { // 초기값: 배열의 시작과 끝
	if (start >= end) return; // end	

	let pivotIndex = lomutoPartition(array, start, end);
	quickSort(array, start, pivotIndex - 1); // left
	quickSort(array, pivotIndex + 1, end); // right
	
	return array;
}

const arr = [1,2,3,4,5,6,7,8,9,10];
const test =  arr.sort(() => Math.random() - 0.5);
document.write('origin data : ', test)
document.write('<br />----<br />')
document.write('result data : ', quickSort(test))

// 중간 숫자를 pivot으로 했을때
const quickSort = function (arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] <= pivot) {
    	left.push(arr[i]);
    } else { 
    	right.push(arr[i]);
    }
  }

  const lSorted = quickSort(left);
  const rSorted = quickSort(right);
  return [...lSorted, pivot, ...rSorted];
};

const arr = [1,2,3,4,5,6,7,8,9,10];
const test =  arr.sort(() => Math.random() - 0.5);
document.write('origin data : ', test)
document.write('<br />----<br />')
document.write('result data : ', quickSort(test))

5. 합병 정렬 (Merge sort)

• 리스트를 반으로 나눈 뒤 각각을 정렬하고 다시 합치는 과정을 반복해 정렬을 수행
• 시간 복잡도는 O(n log n)

function merge(left, right) {
  const sortedArr = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      sortedArr.push(left.shift());
    } else {
      sortedArr.push(right.shift());
    }
  } 
  
  return [...sortedArr, ...left, ...right];
}

function mergeSort(arr) {
  if (arr.length === 1) return arr;
  const boundary = Math.ceil(arr.length / 2);
  const left = arr.slice(0, boundary);
  const right = arr.slice(boundary);
  
  return merge(mergeSort(left), mergeSort(right));
}

const arr = [1,2,3,4,5,6,7,8,9,10];
const randomArr =  arr.sort(() => Math.random() - 0.5);
const sortedArray = mergeSort(randomArr);

document.write('origin data : ', randomArr)
document.write('<br />----<br />')
document.write('result data : ', sortedArray)