[Algorithm] Selection Sort

kich555·2021년 10월 31일
0

Sort Algorithm

목록 보기
1/2

선택정렬은 정렬되지 않은 데이터 중 가장 작은 데이터를 선택해서 맨 앞에서부터 순서대로 정렬해 나가는 알고리즘입니다.
nums라는 정렬되지 않은 숫자 배열을 주면, 선택정렬 알고리즘을 사용하여 오름차순(1,2,3..10) 으로 정렬된 배열을 return해주세요.

💻 Selection Sort

const selectionSort = (nums) => {

  for(i=0; i<nums.length; i++) {
    
    let minIdx = i; // Minimum index를 칭하는 변수 minIdx 선언

    for(j=i+1; j<nums.length; j++) {
   //minIdx가 될 i를 기점으로 나머지 index들을 비교해야하기 때문에 또 한번의 for문을 돌며 이때 j는 i를 제외한 나머지 값들이 될 것이므로 i+1부터 시작하게됨
      if(nums[minIdx] > nums[j]) {
        minIdx = j
      } // nums[minIdx]를 가장 작은 수로 만들기 위해 minIdx와 j를 비교하며 바꿈
    }
    if( minIdx !== i) {
      let swap = nums[minIdx];
      nums[minIdx] = nums[i];
      nums[i] = swap
    }
       // minIdx와 i가 같지 않다면 nums[minIdx]를 하나의 변수로 선언하고 (swap)
       //nums[i]가  nums[minIdx]와 같도록 swap함
    
  }
  return nums
}


Sorting Algorithms_Sebastian De Lima

💡선택 정렬의 장단점

선택정렬은 앞에서부터 차례대로 정렬하며 n개 원소에 대해 n개의 메모리를 사용하기에 정렬을 위한 비교 횟수는 많으나 교환 횟수는 상당히 적다는 것이 장점인 정렬 방식이다.
첫번째 i에서 1 ~ n-1
두번째 i에서 2 ~ n-1
...
n(n-1)/2O(n2)의 시간복잡도를 가진다.

따라서 교환이 많이 이루어져야하는 자료 상태에서 가장 효율적으로 적용될 수 있는 정렬 방식이며,
가장 적합한 자료 상태는 역순 정렬이다. (위 예제와 같은)

반대로 이미 정렬된 상태에서 다른 자료가 추가됨으로 재정렬하게 되는 때에는 최악의 처리 속도를 보여준다는 단점도 있다. 이는 데이터 세트가 이미 정렬되어 있더라도 알고리즘의 모든 반복이 완료될 때까지 여부를 알 수 없기 때문.

profile
const isInChallenge = true; const hasStrongWill = true; (() => { while (isInChallenge) { if(hasStrongWill) {return 'Success' } })();

0개의 댓글