[algorithm/ 선택정렬 ] N개이 숫자가 입력되면 오름차순으로 정렬해라

문제 : N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성

입력 : 정수이다.

새로 배운 것

배열의 구조분해할당, 선택정렬(선택정렬은 아래에서 알아본다.)

• arr[i]와 arr[j]값을 한 줄로 바로 변경할 수 있다.
  [arr[i],arr[j]]=[arr[j],arr[i]];
• 기존에 변수에 담아 값은 바꾸던, 3줄 코드를 대체할 수 있다!
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
  

접근방식 - 선택정렬에 대해 알아보자

• 선택정렬 : 제자리 정렬 알고리즘으로, 모든 요소를 순서대로 비교하여 최솟값을 찾아 정렬해준다.
  1. 주어진 배열(리스트)에서 최솟값을 찾아 맨 첫번째 요소와 바꾼다.
  2. 두번째 요소와 그 다음요소들을 모두 비교하여, 두번째 요소보다 작은값(최솟값)을 찾으면 두번째 요소와 바꾼다.
  3. 세 번째 요소와 4번째 부터 다음요소들 모두를 비교하는 식으로 작은값이 나올때 마다 바꿔준다.
  4. 이 과정을 반복하며 최솟값이 첫번째요소, 그 다음 큰 값이 두번째요소... 오른차 순으로 정렬해주는 것이다.
  

풀이

1. 이중 for문을 사용하여 현재 요소와 나머지 요소를 반복하여 비교해준다.
2. 외부 for문) 0번째 요소부터 마지막 요소를 제외한 모든 요소까지 순서대로 조회한다.
   => 외부 for문은 내부 for문이 다 돈다음 다음 요소를 조회한다.
3. 내부 for문) i+1번째요소(i다음요소)부터 마지막 요소까지 순서대로 조회한다.
4. if문) arr[i]요소보다 arr[j]요소가 더 작은 경우?
   => 현재 arr[i]값이 없어지지 않게, 임시로 담아 줄 temp변수를 선언하여 arr[i]값을 담아준다.
   => arr[i]에는 arr[j]의 값을 담아준다. i번째 요소를 j번째 요소로 바꿔주는 것
   (현재 arr[i]보다 arr[j]가 작은 값인 상태)
   => arr[j]에는 temp 임시로 저장해둔 원래 arr[i]값을 담아준다.
5. 내부 j for문) 모두 돌때 까지 위에 if문을 반복하고, 비교가 끝나면?
6. 외부 i for문) 다음 요소를 조회하며 위에 모든 과정을 반복한다.
7. 모든 비교가 다 끝나면 오름차순으로 정렬된 배열이 출력된다.

      function solution(arr) {
        for (let i = 0; i < arr.length - 1; i++) {
          for (let j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
              let temp = arr[i];
              arr[i] = arr[j];
              arr[j] = temp;
            }
          }
        }
        return arr;
      }

      let arr = [13, 5, 11, 7, 23, 15];
      console.log(solution(arr)); //  [5, 7, 11, 13, 15, 23]

선생님 코드와 내 코드와 다른 점

훨씬 효율적이다!
배열의 구조분해 할당을 쓴 점,
idx 변수를 선언해서 i값을 할당하고 내부 j for문이 끝나고 나서 한 번 두 값의 교환을 하기에,두 값의 교환 횟수를 최소화할 수 있다.

내 코드는 arr[j]<arr[i]가 참일경우 매번 arr[i]와 arr[j]의 값을 교환하기 떄문에,
arr[j]<arr[i]가 참일경우 매번 arr[i]와 arr[j]의 값을 교환한다.

      function solution(arr) {
        for (let i = 0; i < arr.length - 1; i++) {
          idx = i;
          for (let j = i + 1; j < arr.length; j++) {
            if (arr[idx] > arr[j]) idx = j;
          }
          [arr[i], arr[idx]] = [arr[idx], arr[i]];
        }
        return arr;
      }

      let arr = [13, 5, 11, 7, 23, 15];
      console.log(solution(arr)); //  [5, 7, 11, 13, 15, 23]