I've finished the uni - there is no way in hell I would still need data structures and algorithms, right? (that's what I thought, I forgot almost everything to make more room in my brain for football trivia and stupid memes :)) Until I quite embarrassed myself on one interview, and because of that I spent quite some time re-learning this stuff, which landed me a better job than the one I had. (YEAAH!) Again, check my blog if you wish! This is second part in our (cue the SSSR music) JavaScript Algorithm Series.

소개

완료 후 다음 Javascript 정렬 알고리즘인 선택 정렬로 이동합니다.

선택 정렬은 버블 정렬과 다소 유사하지만 더 높은 값을 올바른 위치에 배치하여 먼저 정렬하는 대신 더 작은 값을 올바른 위치에 먼저 배치합니다. 우리는 여전히 (대부분) 같은 방식으로 전체 배열을 반복합니다.

문제는 어떻게? 현재 가장 작은 값을 일종의 컨테이너 변수에 저장해야 합니다. 그런 다음 다른 요소의 값에 따라 해당 값을 다시 선언할 수 있습니다(일부 요소가 배열에서 이미 가장 작은 요소보다 작은 경우).

의사 코드

배열의 첫 번째 요소를 '가장 작은 컨테이너 변수' 안에 저장합니다.

알고리즘은 각 반복에서 현재 요소와 현재 가장 작은 변수를 비교하여 배열을 반복합니다

.

현재 요소가 가장 작은 컨테이너 변수

보다 작은 경우 알고리즘이 가장 작은 변수의 값을 업데이트합니다.

그렇지 않은 경우 알고리즘은 어레이 끝에 도달할 때까지 계속됩니다

.

그러면 알고리즘이 현재 요소와 가장 작은 변수를 교체합니다

.

알고리즘이 1단계부터 5단계까지 과정을 반복합니다.

심상

입력[11, 17, 5, 28, 3, 6, 15]을 사용하여 이 알고리즘을 시각화해 보겠습니다. 시각화는 visualgo이라는 놀라운 무료 도구를 사용하여 수행되었습니다.



처음에는 배열의 첫 번째 값(빨간색 요소)에 가장 작은 값이 할당됩니다. 그런 다음 알고리즘은 요소를 반복하고 가장 작은 값과 현재 요소(녹색)를 비교하고 더 작은 값을 찾으면 해당 값을 다시 선언합니다. 각 반복이 끝날 때마다 알고리즘은 현재 가장 작은 요소를 반복의 첫 번째 요소로 교체하므로 현재 가장 작은 요소가 적절한 위치에 정렬됩니다(색상이 주황색으로 변경됨).

구현

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

selectionSort([11, 17, 5, 28, 3, 6, 15]);

각 외부 반복이 시작될 때 가장 작은 값을 배열의 첫 번째 값으로 설정합니다. 동일한 블록에서(ES6 let 선언을 사용하기 때문에) 값 j를 i + 1로 선언합니다. 그런 다음 배열의 모든 요소를 ​​통과합니다. 현재 가장 작은 값보다 작은 값을 찾으면 가장 작은 인덱스를 j로 다시 선언합니다. 각 반복의 끝에서 더 작은 값이 있고 우리가 사용하여 시작한 값과 같지 않은 경우 값을 교환합니다. - [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] - 감사합니다 ES6.

빅오 복잡성

버블 정렬과 유사하게 선택 정렬의 평균 Big O는 (다시) 배열의 모든 요소를 ​​다른 모든 요소와 비교하기 때문에 O(n2)입니다. 요소 수가 증가하면 런타임이 기하급수적으로 증가합니다. 선택 정렬은 스와핑을 줄이는 알고리즘을 사용하려는 경우 버블 정렬보다 더 유용할 수 있습니다. 왜냐하면 알고리즘은 모든 루프의 끝에서 한 번만 스와핑되기 때문입니다.

결론

그게 다야! 다음으로 이야기할 것은 삽입 정렬이므로 계속 지켜봐 주시기 바랍니다. 행복한 코딩되세요 :).