[ ᴀʟɢᴏʀɪᴛʜᴍ ] Selection Sort ( 선택 정렬 )

NewHa·2023년 9월 7일

ᴀʟɢᴏʀɪᴛʜᴍ

목록 보기

3/14

🌱 Selection Sort ( 선택 정렬 )

👉🏻 선택 정렬 (選擇整列, selection sort)은 리스트의 정렬되지 않은 부분에서 최소값을 찾고, 그 값을 정렬된 부분으로 이동﹒교체하면서 하나의 원소만 남을 때까지 반복하는 간단하고 효율적인 정렬 알고리즘입니다. 즉, 현재 위치에 들어갈 데이터를 찾아 선택하는 알고리즘입니다.

선택정렬은 내부 알고리즘으로, 입력 리스트 이외에 다른 추가 메모리를 요구하지 않는 제자리 정렬 알고리즘의 하나입니다.

☀️ Characteristic of Selection Sort( 특징 )

🪴 장 점

간단하고 이해하기가 쉽습니다.
추가적인 메모리 소비가 적어서 사용할 수 있는 메모리가 제한적인 경우에 사용상 이점이 있습니다.
작은 데이터 세트에 적합합니다.
비교 횟수는 많지만 실제로 교환하는 횟수는 적으므로 많은 교환이 필요한 자료상태에서 버블정렬보다 효율적입니다.

🪴 단 점

같은 값의 요소가 있는 경우, 정렬되면서 상대적인 위치가 변경될 수 있어 불안정 정렬 알고리즘에 해당합니다. 코드를 추가해 안정적으로 만들 수 있습니다.

선택정렬 안정화

function stableSelectionSort(arr) {
	const len = arr.length;
	for(let i = 0; i < len; i++) {
		let min = i;
		for(let j = i + 1; j < len; j++) {
			if(arr[min] > arr[j]) min = j;
		}
		let key = a[min];
		while(min > i) {
			a[min] = a[min - 1];
			min --;
		}
		a[i] = key;
	}
	return arr
}

버블정렬보다는 교환횟수가 적어 효율적이지만, 최악과 평균의 경우 O(n²)의 시간복잡도를 가지는 비효율적인 알고리즘입니다.
대규모 데이터 세트에는 제대로 작동하지 않습니다.

☀️ Time and Space Complexity Analysis ( 시·공간 복잡도 )

👓 sudo code

for(let i = 9; i < n; i++) {
  // arr[i] 부터 arr[n - 1]까지 차례로 비교합니다.
  for(let j = i + 1; j < n; j++) {
  	// arr[j]값이 가장 작은 값이라고 가정하고, arr[i]와 arr[j]값을 교체합니다.
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}

두 개의 for문이 있으므로 전체 시간복잡도는 O(n²)입니다.
최악의 경우, 최선의 경우, 평균적으로 모두 O(n²)의 시간복잡도를 가집니다.
내부 ﹒ 제자리 정렬 알고리즘으로, 공간복잡도는 O(1)입니다.

☀️ Implementation of Selection Sort( 구현 )

🕶️ Basic Implementation (기본 구현)

function selectionSort(arr) {
  const len = arr.length;
  let i, j, minIdx; // 👉🏻 반복문을 돌며 계속 선언하지 않도록 선언은 위에서 해주는 것이 좋다!😆
  for(i = 0; i < len - 1; i++) {
    minIdx = i;
    for(j = i + 1; j < len; j++) {
      if(arr[minIdx] > arr[j]) minIdx = j;
    }
    [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
  }
  return arr
}

🕶️ Recursive Implemente (재귀적 구현)

function minIdx(arr, idx, lastIdx) {
  // base case 
  if(idx === lastIdx) return idx;
  // recursive
  let k = minIdx(arr, idx + 1, lastIdx);
  return arr[idx] < arr[k] ? idx : k;
}

function recursiveSelectionSort(arr, idx = 0) {
  const len = arr.length;
  // base case
  if(idx === len) return;
  // recursive
  let min = minIdx(arr, idx, len - 1);
  if(k !== idx) [arr[min], arr[idx]] = [arr[idx], arr[min]];
  recursiveSelectionSort(arr, idx + 1);
}

🕶️ Optimization

최솟값을 찾으면서 최댓값도 찾아서 양쪽 끝에 정렬하는 방식으로 개선할 수 있습니다. 하지만 전체적인 시간복잡도는 여전히 O(n²)입니다.

function SelectionSort(arr) {
  const len = arr.length;
  let i, j, min, max, minIdx, maxIdx;
  for(i = 0, j = len - 1; i < j; i++, j--) {
    min = arr[i];
    max = arr[i];
    minIdx = i;
    maxIdx = i;
    
    for(k = i; k <= j; k++) {
      if(arr[k] > max) {
        max = arr[k];
        maxIdx = k;
      }else if(arr[k] < min) {
        min = arr[k];
        minIdx = k;
      }
    }
    [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
	if(arr[minIdx] === max) [arr[j], arr[minIdx]] = [arr[minIdx], arr[j]];
	else [arr[j], arr[maxIdx]] = [arr[maxIdx], arr[j]];
  }
  return arr
}