24.03.18 TIL - 정렬 for Javascript

이번 프로젝트에서 정렬을 하게 될 일이 생겼는데, 이번 기회에 정렬에 대한 알고리즘을 공부하고 정리하는 시간을 가졌다.

컴퓨터 자료구조에는 많은 정렬이 있지만 간단하게 3개만 정리해보겠다.

 

1. 선택정렬

• 매 단계에서 가장 작은 원소를 선택해서 앞으로 보내는 정렬
• 앞으로 보낸 원소는 더이상 위치가 변경되지 않는다.
• 시간 복잡도 O(N^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. 버블정렬

• 단순히 인접한 두 원소를 확인하여, 정렬이 안 되어 있다면 위치를 서로 변경
• 서로 인접한 두 원소를 비교하는 형태가 거품과 같다 하여서 붙힌 이름
• 시간 복잡도 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. 삽입정렬

•  각 숫자를 적절한 위치에 삽입
• O(N^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;
      }
    }
  }
}

 

4. 병합 정렬

• 정형적인 분할 정복 알고리즘. 큰 문제를 작은 문제로 분할하고 각각 해결하여 해결된 작은 문제를 이용하여 큰 문제 해결하는 방법
• 일반적으로 재귀함수를 이용해 구현
• 더이상 쪼갤수 없는 크기가 될 때까지 계속하여 분할한다.
• 단점 : 재귀함수를 사용하니 호출횟수가 많아지고, 오버헤드로 이어질 수 있다.
• 동작방식
  • 정렬할 배열(큰 문제)을 같은 크기의 부분배열(작은문제) 2개로 분할
  • 부분 배열을 정렬(작은 문제를 해결) : 첫째 원소부터 하나씩 확인하여 정렬, 총 원소 개수가 N개일 때, O(N)의 시간 복잡도
  • 조합: 정렬된 부분배열을 하나로 병합
• 시간복잡도는 최악의 경우에도 O(NlogN)이 보장되므로 효율적

// 병합(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)
  }
}

 

 

출처 : https://yoonsoo-space.tistory.com/120

JavaScript 정렬(sorting) 알고리즘