JavaScript 정렬(sorting) 알고리즘

1. 선택 정렬

• 매 단계에서 가장 작은 원소를 선택해서 앞으로 보내는 정렬 방법
• 앞으로 보내진 원소는 더 이상 위치가 변경되지 않는다.
• 시간 복잡도 O(N^2)로 비효율적인 정렬 알고리즘 중 하나
• 동작 방식
  1. 각 단계에서 가장 작은 원소를 선택
  2. 현재까지 처리되지 않은 원소들 중 가장 앞의 원소와 위치를 교체한다.

// 선택 정렬 함수
function selectionSort(arr) {
	for (let i = 0; i < arr.length; i++) {
    	let minIndex = i;
        for (let j = i; j < arr.length; j++) {
        	if (arr[minIndex] > arr[j] {
            min Index = j
            }
        }
		// 스와프(swap)
        let temp = arr[i]
        arr[i] = arr[minIndex]
        arr[mindex] = temp
    }
}

 

2. 버블 정렬(Bubble Sort)

• 단순히 인접한 두 원소를 확인하여, 정렬이 안 되어 있다면 위치를 서로 변경
• 서로 인접한 두 원소를 비교하는 형태가 거품과 같다고 하여 붙여진 이름
• 시간 복잡도 O(N^2)로 비효율적인 정렬 알고리즘
• 각 단계에서는 인접한 두 개의 원소를 비교하여, 필요시 위치를 변경
• 한 번의 단계가 수행되면, 가장 큰 원소가 맨 뒤로 이동
• 그 다음 단계에서는 맨 뒤로 이동한 데이터는 정렬에서 제외

// 버블 정렬 함수
function bubbleSort(arr) {
	for (let i = arr.length - 1; i > 0; i--) {
    	for (let j = 0; j < i; j++) {
    		if (arr[j] < arr[j + 1]) {
            	let temp = arr[j];
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
		}    
    }
}

3. 삽입 정렬(Insertion Sort)

• 삽입 정렬이란 각 숫자를 적절한 위치에 삽입하는 정렬 기법
• 동작 방식
  1. 각 단계에서 현재 원소가 삽입될 위치를 찾는다.
  2. 적절한 위치에 도달할 때까지 반복적으로 왼쪽으로 이동한다.

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j > 0; j--) {
      // 인덱스 j부터 1까지 1씩 감소하며 반복
      if (arr[j] < arr[j - 1]) {
        // 한 칸씩 왼쪽으로 이동
        // 스와프(swap)
        let temp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
      } else {
        // 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
        break;
      }
    }
  }
}

• 시간 복잡도
  • 삽입 정렬이란 각 원소를 적절한 위치에 삽입하는 정렬 기법
  • 매 단계에서 현재 처리 중인 원소가 삽입될 위치를 찾기 위해 약 N번의 연산이 필요하다.
  • 결과적으로 약 N개의 단계를 거친다는 점에서 최악의 경우 O(N^2)의 시간 복잡도를 가진다.

4. 병합 정렬(Merge Sort)

• 전형적인 분할 정복(divide and conquer) 알고리즘
• 분할 정복(divide and conquer)
  1. 분할(divide): 큰 문제를 작은 부분 문제(쉬운 문제)로 분할한다.
  2. 정복(conquer): 작은 부분 문제를 각각 해결한다.
  3. 조합(combine): 해결한 부분 문제의 답을 이용하여 다시 큰 문제를 해결한다.
• 분할 정복은 일반적으로 재귀 함수를 이용해 구현한다.
• 더 이상 쪼갤 수 없는 크기가 될 때까지 계속하여 분할한다.
• 분할 정복의 단점
  • 일반적으로 재귀 함수를 사용한다는 점에서 함수 호출 횟수가 많이 발생한다.
  • 이는 오버헤드(overhead)로 이어진다.
• 병합 정렬의 특징
  • 시간 복잡도 O(NlogN)을 보장하는 빠른 정렬 알고리즘 중 하나
• 병합 정렬의 동작 방식
  1. 분할(divide): 정렬할 배열(큰 문제)을 같은 크기의 부분 배열(작은 문제) 2개로 분할한다.
  2. 정복(conquer): 부분 배열을 정렬한다. (작은 문제를 해결)
     ==> 각 부분 배열은 이미 정렬된 상태로 본다. 첫째 원소부터 시작하여 하나씩 확인
     ==> 총 원소의 개수가 N개일 때, O(N)의 시간 복잡도가 요구된다.
  3. 조합(combine): 정렬된 부분 배열을 하나의 배열로 다시 병합한다.
• 시간 복잡도
  • 직관적으로 생각했을 때, 높이가 O(logN)이고, 너비가 O(N)인 정사각형과 유사하다.
  • 따라서 최악의 경우 시간 복잡도는 O(NlogN)이다.
  • 장점: 최악의 경우에도 O(NlogN)을 보장할 수 있다는 점에서 효율적
  • 단점: 일반적인 경우, 정복(conquer) 과정에서 임시 배열이 필요하다.

// 병합(merge) 수행 함수
function merge(arr, left, mid, right) {
  let i = left;
  let j = mid + 1;
  let k = left; // 결과 배열의 인덱스
  while (i <= mid && j <= right) {
    if (arr[i] <= arr[j]) sorted[k++] = arr[i++];
    else sorted[k++] = arr[j++];
  }
  // 왼쪽 배열에 대한 처리가 다 끝난 경우
  if (i > mid) {
    for (; j <= right; j++) sorted[k++] = arr[j];
  }
  // 오른쪽 배열에 대한 처리가 다 끝난 경우
  else {
    for (; i <= mid; i++) sorted[k++] = arr[i];
  }
  // 정렬된 배열 결과를 원본 배열에 반영하기
  for (let x = left; x <= right; x++) {
    arr[x] = sorted[x];
  }
}

// 병합 정렬(merge sort) 함수
function mergeSort(arr, left, right) {
  // 원소가 1개인 경우, 해당 배열은 정렬이 된 상태로 이해 가능
  if (left < right) {
    // 원소가 2개 이상이라면
    let mid = parseInt((left + right) / 2); // 2개의 부분 배열로 분할(divide)
    mergeSort(arr, left, mid); // 왼쪽 부분 배열 정렬 수행(conquer)
    mergeSort(arr, mid + 1, right); // 오른쪽 부분 배열 정렬 수행(conquer)
    merge(arr, left, mid, right); // 정렬된 2개의 배열을 하나로 병합(combine)
  }
}

 

5. JavaScript 정렬 라이브러리

• JavaScript에서는 배열에 포함된 데이터를 정렬하는 sort() 함수를 제공한다.
• 최악의 경우 시간 복잡도 O(NlogN)을 보장한다.
• 정렬 기능이 필요하다면, 단순히 sort()함수를 사용하는 것을 권장
• But, sort() 함수의 사용이 제한된다면, 직접 구현을 하면 된다.

arr.sort(compareFunction);

==> compareFunction은 정렬 기준을 정해주는 함수

==> 내림차순, 오름차순 등 구체적인 정렬 기준을 설정할 수 있다.

• JavaScript의 정렬 함수에서는 정렬 기준 함수가 사용된다.
• 두 개의 원소 a, b를 입력으로 받는다.
  1. 반환 값이 0보다 작은 경우 => a가 우선순위가 높아, 앞에 위치한다.
  2. 반환 값이 0보다 큰 경우 => b가 우선순위가 높아, 앞에 위치한다.
  3. 반환 값이 0인 경우 => a와 b의 순서를 변경하지 않는다.
• compareFunction을 사용하지 않으면 각 원소는 문자열로 취급된다.
• 유니코드 값 순서대로 정렬된다.
• 따라서, 항상 compareFunction을 명시하는 습관을 들일 필요가 있다.