정렬 알고리즘 (javascript)

• 정렬 알고리즘으로 버블, 선택, 삽입, 퀵, 합병 정렬을 배웠었다.
• 하지만, C언어로만 이 코드들을 작성했었기에 자바스크립트로도 정렬 알고리즘을 기록하기로 하였다.
• 물론, 자바스크립트에서는 arr.sort((a, b) => a - b) 알고리즘으로 손쉽게 배열을 정렬할 수 있다.

🍇 버블 정렬

• 가장 쉽게 생각할 수 있는 정렬 방법으로 앞뒤의 숫자를 비교하여 정렬이 필요하다면, 앞뒤의 숫자를 바꾼다.

• 이미 정렬된 상태라면, 중간에 반복문을 중단할 수 있다.

• 평균적으로 O(N^2) 시간복잡도를 가진다.

const bubbleSort = function (arr) {
  let sorted;
  for(let i = 0; i < arr.length; i++){
    sorted = false;
    for(let j = 0; j < arr.length - i; j++){
      if(arr[j + 1] < arr[j]){
        sorted = true;
        [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]] // 위치 변경
      }
    }
    if(sorted === false) // 이미 모두 정렬된 상태
      return arr;
  }
  return arr;
};

🍉 선택 정렬

• 배열에서 가장 큰 원소를 찾아내어 뒤로 보내거나, 가장 작은 원소를 찾아내어 앞으로 보내는 방식으로 정렬한다.

• 평균적으로 O(N^2) 시간복잡도를 가진다.

const selectionSort = (arr) => {
	let i;
	for(i = arr.length - 1; i >= 0; i--) {
		// 가장 큰 것을 찾아내 가장 뒤로 보낸다.
		let maxIndex = 0;
		for (let j = 1; j <= i; j++) {
			// 가장 큰 것 찾기
			if (arr[maxIndex] < arr[j])
				maxIndex = j;
		}
		// 교체
		if (maxIndex != i) {
        	[arr[i], arr[maxIndex]] = [arr[maxIndex], arr[i]];
		}
	}
    return arr;
}

🥬 삽입 정렬

• 앞에서 부터 하나씩 삽입하는 느낌으로 정렬을 하는 알고리즘이다.

• 새로 정렬 배열에 삽입되는 원소는 차례대로 비교를 하여 위치를 찾아간다.

• 평균적으로 O(N^2) 시간복잡도를 가진다.

• 이미 정렬이 많이 된 배열이라면, 빠르게 정렬할 수 있다.

• 하지만, 최악의 경우에는 모든 배열을 뒤집어야 할 수도 있다.

const insertionSort = function (arr) {
  for(let i = 1; i < arr.length; i++){
    let j = i - 1;
    let save = arr[i]; // 새로 삽입되는 원소
    while(j >= 0 && arr[j] > save){
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = save; // 자신의 위치를 찾았다.
  }
  return arr;
};

🍄 퀵 정렬

• 현재 알려진 가장 빠른 정렬 알고리즘이다.

• 임의의 피봇을 하나 정한 뒤 그 원소를 기준으로 큰 원소를 지닌 배열, 작은 원소를 지닌 배열, 피봇과 값이 같은 원소를 가진 배열을 나눈다.

• 그리고 그 나뉜 배열을 대상으로 다시 피봇을 정하고 값의 크기에 따라 배열을 나누는 것을 반복한다.

• 그리고 정리된 배열들을 순서대로 합치면 결과적으로 정렬이 완료된 배열을 얻을 수 있다.

• 평균적으로 O(NlogN) 시간복잡도를 가진다.

const quickSort = (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 leftArr = quickSort(left);
    const rightArr = quickSort(right);

    return leftArr.concat(pivot, rightArr); // 정렬된 값들을 모두 합쳐 리턴
}

🧀 합병 정렬

• 배열을 쪼갠 뒤, 이 배열들을 합치면서 정렬을 해나가는 알고리즘이다.

• 원소를 하나만 가지는 배열부터 시작하여 점점 배열을 합쳐나간다.

• 평균적으로 O(NlogN) 시간복잡도를 가진다.

const mergeSort = function (arr) {
    let mergeArr = arr.map(el => [el]); // 원소가 하나인 정렬된 부분 리스트가 된다.
    while (mergeArr.length !== 1) {
        // 하나의 배열이 남을 때 까지 병합을 반복한다.
        let tmp = [];
        while(mergeArr.length !== 0){
            let first = mergeArr.pop();
            if(mergeArr.length === 0){
                tmp.push(first); // 원소의 개수가 홀수, 마지막 하나 남음
                break;
            }
            let second = mergeArr.pop();
            tmp.push(merge(first, second));
        }
        mergeArr = tmp; // 갱신
    }
    return mergeArr[0];
};

function merge(arr1, arr2) {
    let arr = [];
    let i = 0,
        j = 0;
    while (i !== arr1.length && j !== arr2.length) {
        if (arr1[i] > arr2[j]) {
            arr.push(arr2[j]);
            j++;
        } else {
            arr.push(arr1[i]);
            i++;
        }
    }
    // 남은 배열 붙이기
    while (i !== arr1.length) {
        arr.push(arr1[i]);
        i++;
    }
    while (j !== arr2.length) {
        arr.push(arr2[j]);
        j++;
    }
    return arr;
}