Javascript Python 셀렉션 정렬 (Selection Sort)

셀렉션 정렬(선택 정렬, Selection Sort)은 버블 정렬과 함께 가장 간단한 정렬 알고리즘 입니다. 시간 복잡도는 O(n²)입니다.

Javascript 셀렉션 정렬

기본적인 오름차순 정렬입니다.

function selectionSort(ar) {
  var len = ar.length;
  for (var i = 0; i < len - 1; i++) {
    var idx = i;
    for (var j = i + 1; j < len; j++) {
      if (ar[idx] > ar[j]) idx = j;
    }
    [ar[i], ar[idx]] = [ar[idx], ar[i]];
  }
}

var ar = [24, 55, -2, 100, 0, 1, 7];
selectionSort(ar);
console.log(ar);

[-2, 0, 1, 7, 24, 55, 100]

Javascript 셀렉션 정렬 - 비교함수 사용

비교함수를 인수로 전달하는 방식입니다. 내림차순으로 해봤습니다.

function selectionSort(ar, compare) {
  var len = ar.length;
  for (var i = 0; i < len - 1; i++) {
    var idx = i;
    for (var j = i + 1; j < len; j++) {
      if (compare(ar[idx], ar[j]) > 0) idx = j;
    }
    [ar[i], ar[idx]] = [ar[idx], ar[i]];
  }
}

var ar = [24, 55, -2, 100, 0, 1, 7];
selectionSort(ar, (a, b) => b - a);
console.log(ar);

[100, 55, 24, 7, 1, 0, -2]

Python 셀렉션 정렬

오름차순 정렬입니다.

def selectionSort(ar):
  length = len(ar)
  for i in range(length-1):
    idx = i
    for j in range(i+1, length):      
      if ar[idx] > ar[j]: idx = j
    ar[i], ar[idx] = ar[idx], ar[i]

ar = [24, 55, -2, 100, 0, 1, 7]
selectionSort(ar)
print(ar)

[-2, 0, 1, 7, 24, 55, 100]

Python 셀렉션 정렬 - reverse 인수 사용

reverse 인수를 사용해서 내림차순으로 정렬했습니다.

def selectionSort(ar, reverse=False):
  length = len(ar)
  for i in range(length-1):
    idx = i
    for j in range(i+1, length):
      cond = (ar[idx] < ar[j]) if reverse else (ar[idx] > ar[j])
      if cond: idx = j
    ar[i], ar[idx] = ar[idx], ar[i]

ar = [24, 55, -2, 100, 0, 1, 7]
selectionSort(ar, reverse=True)
print(ar)

[100, 55, 24, 7, 1, 0, -2]

Sort