Jun 개발노트

정렬

February 24, 2020

정렬

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));
    };

Written by Junho You 배운것을 기록하자