[JavaScript 알고리즘] 정렬(sorting) - 2. Selection Sort

https://visualgo.net/en/sorting

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

여기에서 Selection sort의 작동방식을 눈으로 보고 오세요

 

[19,44,38,5,47,15] 라는 배열이 있습니다.

본 것 중에서 가장 작은 값을 최솟값으로 정합니다.

처음에는 19밖에 본 게 없으니 본 것 중에서 가장 작겠죠?

최솟값을 19로 만들어줍시다.

이제 최솟값과 44를 비교해요.

44가 최솟값인 19보다 작지 않죠? 넘어갑니다.

38도 마찬가지고요,

그런데 5라는 친구가 나왔습니다. 

19보다 작아요. 그럼 5가 최솟값이됩니다.

그리고 다음으로 47과 5를 비교, 15와 5를 비교합니다.

최솟값이 5지요? 이걸 맨 첫번째 요소로 SWAP합니다.

이제 두번째 요소부터 우리가 한 것을 반복하면 됩니다. 

 

의사코드를 살펴봅시다.

 

의사코드

첫 번째 요소를 본 것 중에서 최소인 값으로 정합니다.

더 작은 요소가 발견될 때까지 그 다음 요소들을 순회하며 첫 번째 요소와 비교합니다.

만약 그 다음요소들 중에서 더 작은 요소가 발견된다면 그걸 "new최솟값"으로 지정합니다.

배열이 끝날때까지 반복합니다.

만약 "그 최솟값"이 처음 시작한 최솟값이 아니라면 두 요소를 SWAP합니다.

다음 요소부터 위 동작들을 배열이 정렬될 때까지 반복합니다.

 

어렵네요. 코드로 한번 봐야겠습니다 ^^

 

function selectionSort(arr) {
  for(let i = 0; i < arr.length; i++) {
    let lowest = i;
    for(let j = i + 1; j < arr.length; j++) {
      if(arr[j] < arr[lowest])  {
        lowest = j;
      }
    }
    
    // SWAP합니다!!
    let temp = arr[i];
    arr[i] = arr[lowest];
    arr[lowest] = temp;
  }

  return arr;
}

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

 

자, 다 됐습니다! 수고하셨습니다 ^^

 

??? : "어리석구나"

나니?!

자! 여러분! 최적화합시다!!

생각해봅시다. 만약 이렇게 된다면 어떨까요?

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

for문이 돌면서 첫 번째로 lowest에 0이 저장됩니다.

그런데 inner loop에서 arr[j]가 lowest보다 작을 때가 없죠?

그럼 그냥 넘어가야되죠? 근데 웬걸?

SWAP을 해버려요. 

lowest는 그대로 i, 즉 0이에요 

그러니까

// i : 0, lowest : 0인 상태
let temp = arr[0];
arr[0] = arr[0];
arr[0] = temp;

이런 쓰잘데기없는 짓을 해버린다는거죠..

 

어서 조건을 추가해봅시다.

function selectionSort() {
  for(let i = 0; i < arr.length; i++) {
    let lowest = i;
    for(j < i + 1; j < arr.length; j++) {
      if(arr[j] < arr[lowest]) {
        lowest = j;
      }      
    }
    if(lowest !== i) {
      // SWAP
      let temp = arr[j]
      arr[j] = arr[lowest];
      arr[lowest] = temp;
    }
  }
  
  return arr;
}

 

자, 이렇게 하면 lowest가 그대로 i일때 저런 멍청한 짓을 하는 불상사를 막을 수 있게 됩니다.

ES2015 문법으로 산뜻하게 마무리해봅시다.

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[j] < arr[lowest]) {
        lowest = j;
      }
    }
    
    if(lowest !== i) swap(arr, i, lowest);
  }
  
  return arr;
}

 

Selection Sort의 Big O Notation은 n^2입니다. ^^

다른 정렬법을 배워보아요 ㅎㅎ