[ TIL 42 ] Code-kata-19

Code Kata 문제 📜

nums라는 정렬되지 않은 숫자 배열을 주면, 오름차순(1,2,3..10) 으로 정렬된 배열을 return해주세요.
선택정렬 알고리즘으로 구현하셔야겠죠??

Code Kata 첫번째 시도 💡

const selectionSort = (nums) => {
  for(let i = 0; i < nums.length; i++){
    for (let j = 0; j < nums.length -1 - i; j++){
      if (nums[j] > nums[j+1]){
        swap = nums[j];
        nums[j] = nums[j+1];
        nums[j+1] = swap;
      }
    }
    if(!swap){
      break;
    }
  }
  return nums;
}

console.log(selectionSort([5, 4, 3, 2, 1]));

첫번째 시도 review ✍️

for문으로 i가 0부터 array.length보다 작을 때까지 돌린다.(배열을 순차적으로 비교할거기때문에)
그 안에 j가 0부터 array.length - 1 - i보다 작을 때까지 돌린다.
왜냐면 array[j]와 array[j + 1]을 비교할 예정이기 때문에
배열의 마지막 데이터를 포함하지 않아도 검색 대상에 포함되므로 1을 빼줘야하고
두번째로 각 회전이 끝날 때마다 마지막 데이터의 정렬이 끝나기 때문에 i를 빼줘야한다.
이제 swap이란 변수를 만들어 array[j]와 array[j + 1]을 비교하여 array[j]가 더 크면 자리를 교환한다.
만약에 각 회전을 끝내고 swap 변수가 undefined상태라면 정렬이 다 된 상태라서 for문을 종료시킨다.

새로운 알게 된 내용 📌

선택정렬

각종 데이터 목록을 정리하고 싶을 때
분포도의 중위값을 알아내고 싶을 때
데이터에서 중복값을 잡아내고 싶을 때
이진 탐색을 하고 싶을 때

선택정렬은 코드가 간단하고 30이하의 작은수를 비교할땐 효과적인 방법이지만,
간단하지만 성능이 안좋은 정렬 방법 중 하나이다.

[5,1,4,7,2,6,8,3] 배열을 처음부터 훑어 가장 작은 1을 앞으로 보냅니다.
[1,5,4,7,2,6,8,3] 다시 훑어 2를 앞으로 보냅니다.
[1,2,4,7,5,6,8,3] 3을 앞으로
[1,2,3,7,5,6,8,4][1,2,3,4,5,6,8,7]
[1,2,3,4,5,6,8,7][1,2,3,4,5,6,7,8] 정렬 끝

참고한 블로그 > 제로초 블로그