정렬

1. 선택정렬

• index를 증가시키면서 index 오른쪽에 있는 원소들중에서 제일 작은원소와 자리를 교환한다.

• 시간효율성 : 최악의 경우를 생각해서 모든 원소를 n개의 원소를 1, 2, 3, … n-1까지 다 돌아야 하므로 (n)(n-1)/2 ===n이 무한대라고 가정했을떄=====> n^2

   const select = arr => {
       // 맨앞을 기준으로 오른쪽에서 제일 작은걸 찾아서 위치를 교환한다.
       const len = arr.length;
       for (let i = 0; i < len; i++) {
           let target = i;
           // 요소를 변수에 담아 오른쪽에 있는 원소들중에서 제일 작은것이랑 비교한다.
           for (let j = i + 1; j < len; j++) {
               // 범위는 처음 선택한 요소의 오른쪽부터 끝까지 돈다.
               if (arr[target] > arr[j]) {
                   // 오른쪽 요소가 첫 요소보다 작다면
                   // target의 J를 업데이트 한다.
                   target = j;
               }
           }
           // 비교하는 요소를 임시변수에 담고
           // 제일 작은 원소를 비교 원소에 넣은 다음
           // 임시 변수에 들어 있는 값을 제일 작은 원소 자리에 넣는다.
           let temp = arr[i];
           arr[i] = arr[target];
           arr[target] = temp;
       }
       return arr;
   };
   ```

2. 삽입정렬

• index를 증가시기면서 오른쪽에 있는 원소를 왼쪽에 원소중에 내림차순을 정렬되게 교환한다.

• 시간 효율성 : 최악의 경우를 생각해서 모든 원소를 n개의 원소를 1, 2, 3, … n-1까지 비교 반목하므로 (n)(n-1)/2 ===n이 무한대라고 가정했을떄=====> n^2

  const insert = arr => {
      // 바로 오른쪽에 있는것을 왼쪽에서 위치는 찾아서 들어간다.
      const len = arr.length;
      let i, j;
      for (i = 1; i < len; i++) {
          let target = arr[i];
          // 정렬할 요소를 변수에 담는다.
          for (j = i - 1; j >= 0; j--) {
              // 정렬한 요소로 부터 왼쪽으로 비교하면서 작은 자리를 찾는다.
              if (arr[j] > target) {
                  // 왼쪽에 요소가 타켓보다 크다면 타켓의 자리에 왼쪽 요소의 값을 넣어라
                  // 4 5 6 3
                  // 4 5 6 6 << 3 자리에 6이 들어감
                  // 4 5 5 6 << 6 자리에 5가 들어감
                  arr[j + 1] = arr[j];
              } else {
                  // 왼쪽 요소가 타켓보다 작다면 더 이상 감소하지 말고 반복문을 스탑
                  break;
              }
          }
          // j의 위치가 타켓의 값
          arr[j + 1] = target;
      }
      return arr;
  };

3. 버블정렬

• index를 증가시키면서 오른쪽 정렬과 비교해서 작은것을 왼쪽으로 이동 큰것을 오른쪽으로 이동하여 모두다 정렬이 될때까지 처음부터 계속 돈다.

• 시간 효율성 : 최악의 경우를 생각해서 모든 원소를 n개의 원소를 n-1번 돌아야 하는데 n(n-1)===n이 무한대라고 가정했을떄=====> n^2

  const bubble = arr => {
      const len = arr.length;
      let temp = 0;
      // 값을 이동할 변수를 선언
      let count = 0;
      // 제한조건을 위해 변수 선언
      for (let i = 0; i < len; i++) {
          if (arr[i] > arr[i + 1]) {
              // 오른쪽에 있는 원소가 왼쪽 보다 작다면 자리를 변경
              temp = arr[i];
              arr[i] = arr[i + 1];
              arr[i + 1] = temp;
              // 제한조건을 위해 카운터를 올린다. 만약 정렬이 됬다면 카운트는 0
              count++;
          }
      }
      if (count === 0) return arr; // 제한조건
      return bubble(arr);
  };

4. 퀵정렬

• 기준값을 선정하여 기준값 보다 크면 오른쪽 배열, 작으면 왼쪽 배열의 추가 시키고 이 오른쪽/왼쪽 정렬을 다시 앞에 말한것처럼 정렬을 하여 정렬시키는 것이다.

• 시간 효율성 : n^2

  const quick = arr => {
      // 원소가 2개이면, 나눌수 없기 때문에 제한조건
      if (arr.length < 2) {
          return arr;
      }
      let len = arr.length;
      let left = [];
      let right = [];
      let pivot = [arr[0]];
      // 피벗에 첫번째 원소를 넣어 좌/우쯕 배열에 정렬한다.
      for (let i = 1; i < len; i++) {
          if (pivot < arr[i]) right.push(arr[i]);
          else if (pivot > arr[i]) left.push(arr[i]);
          else pivot.push(arr[i]);
      }
      // 재귀호출로 왼쪽 오른쪽 배열을 퀵정렬 시켜주고
      // 그값을 concat을 통하여 원래 배열을 만들어준다.
      return quick(left).concat(pivot, quick(right));
  };