정렬 알고리즘: 선택 정렬

오늘은 Selection Sort에 대해 알아보겠습니다! 이 알고리즘이 하는 일은 배열 내부의 항목을 정렬하는 것입니다. 배열을 정렬하는 빠른 방법인 것처럼 들릴 수 있지만 선택 정렬이 틀렸음을 증명합니다.

의사 코드

배열을 인수로 사용하는 selectionSort라는 함수를 작성하십시오.

변수 i를 사용하여 배열을 반복합니다. 첫 번째 요소를 가장 작은 값으로 저장합니다.

i의 다음 인덱스에서 j의 변수를 사용하여 배열을 다시 반복합니다.

arr[j]의 값이 발견된 가장 낮은 변수보다 작은 값을 갖는 경우 해당 값을 가장 낮은 값으로 할당할 수 있습니다.

i의 인덱스에 있는 값이 가장 작은 값이 아닌 경우. 교환 순서를 시작합니다.

배열이 정렬될 때까지 다음 요소에 대해 동일한 단계를 반복합니다.

코드

function selectionSort(arr){
  console.log(arr, 'original')
  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 our current i is not the lowest value, start switching
     if(i !== lowest){
      //create switch here
      var temp = arr[i]
      console.log(arr)
      arr[i] = arr[lowest]
       console.log(arr)
      arr[lowest] = temp
       console.log(arr)
       console.log(temp, 'temp holding at place for a switch')
       console.log(lowest, 'lowest @ index')
       console.log(arr[i], 'arr[i] has now became lowest')
        console.log(arr[lowest], 'arr[lowest]')
    }
  }
  return arr
  } 

selectionSort([7,9,4])

[ 7, 9, 4 ] 'original'
[ 7, 9, 4 ]
[ 4, 9, 4 ]
[ 4, 9, 7 ]
7 'temp holding at place for a switch'
2 'lowest @ index'
4 'arr[i] has now became lowest'
7 'arr[lowest]'
[ 4, 9, 7 ]
[ 4, 7, 7 ]
[ 4, 7, 9 ]
9 'temp holding at place for a switch'
2 'lowest @ index'
7 'arr[i] has now became lowest'
9 'arr[lowest]'
[ 4, 7, 9 ]

설명

이해해야 할 부분은 스왑이 작동하는 방식입니다. 기본적으로 i가 가장 낮은 값이 아니라는 것을 알게 되면 바로 여기서 스와핑의 마법이 발생합니다. i가 place인 값이 가장 작은 값이 아님을 알게 되면 변수 temp를 생성하고 이를 스와핑을 위한 자리 표시자로 arr[i] 대신 할당해야 합니다. 우리는 arr[최저]가 보유하고 있는 값으로 arr[i]를 얇게 할당합니다. 이제 가장 작은 값이 올바른 위치에 배치됩니다. 마지막 스왑은 temp에 arr[lowest]를 할당하여 필요한 위치에 가장 가까운 큰 값을 가장 낮은 값으로 지정하는 것입니다.

시간 및 공간 복잡성

선택 정렬 기능에 중첩 for 루프가 있고 배열의 다른 모든 요소에 대한 모든 비교와 함께 일관된 양의 스와핑이 있다는 점을 감안할 때 시간 복잡도는 O(n^2)입니다. 그러나 이 알고리즘의 공간 복잡도는 O(1)이고 배열 대신 교체하므로 새 배열을 만들거나 기존 배열에 추가 공간을 추가할 필요가 없습니다.

결론

자, 이것으로 Selection Sort에 대한 제 블로그를 마치겠습니다! 이것이 알고리즘을 이해하는 방법에 대한 개인적인 여정에 도움이 되었기를 바랍니다! 삽입 정렬에 대한 다음 주제를 기대해주세요!

행복한 코딩!