Selection Sort

목차

선택 정렬 : 소개
선택 정렬 : 구현
선택 정렬 : 빅오 복잡도

 

1. 선택 정렬 : 소개

선택 정렬 의사코드
1. 첫 번째 요소를 지금까지 본 값 중 가장 작은 값으로 저장한다.
2. 더 작은 숫자를 찾을 때까지 1번 값을 다음 항목과 비교한다.
3. 더 작은 숫자가 발견되면, 더 작은 숫자를 새 "최소값"으로 지정하고 배열의 끝까지 계속 최소값을 찾아나간다.
4. "최소값"이 처음에 시작한 값이 아닌 경우 두 값을 바꿔준다.
5. 배열이 정렬될 때까지 다음 요소를 사용하여 이 작업을 반복한다.

 

2. 선택 정렬 : 구현

// LEGACY VERSION (non ES2015 syntax)
function sselectionSort(arr){
    for(var i = 0; i < arr.length; i++){
        var lowest = i;
        for(var j = i+1; j < arr.length; j++){
            if(arr[j] < arr[lowest]){
                lowest = j;
            }
        }
        if(i !== lowest){
            //SWAP!
            var temp = arr[i];
            arr[i] = arr[lowest];
            arr[lowest] = temp;
        }
    }
    return arr;
}

// ES2015 VERSION
function selectionSort(arr) {
  const swap = (arr, idx1, idx2) =>
    ([arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]);

  for (let i = 0; i < arr.length; i++) {
    let lowest = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[lowest] > arr[j]) {
        lowest = j;
      }
    }
    if (i !== lowest) swap(arr, i, lowest);
  }

  return arr;
}

selectionSort([0,2,34,22,10,19,17]);

 

3. 선택 정렬 : 빅오 복잡도

O( n^2)