정렬의 모든것!

🤓오늘의 공부 주제: 정렬🤓

버블정렬(Bubble Sort)

버블정렬이란?
앞의 숫자와 옆의 숫자를 비교해서 바꾸는 알고리즘.

구현은 쉽지만 성능은 좋지 않음.

마지막 원소는 정렬이 된것이기 때문에 빼고 정렬.

따라서 등차수열의 합만큼 실행됨.
(n-1) + (n-2) +... + 2 + 1 = n(n-1)/2 = n^2-n/2

=> 시간 복잡도는 O(n^2)

💡요약💡
장점: 이해와 구현이 간단함

단점: 성능이 O(n^2)으로 좋지 않음.

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

선택정렬(Selection Sort)

선택정렬이란?
배열의 정렬되지 않은 영역의 첫번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫번째 원소로 가져온다.

구현은 쉽지만 성능은 좋지 않음.

마지막 원소는 정렬이 된것이기 때문에 빼고 정렬.
minValueIndex = 0 이 아니라 정렬되지 않은 인덱스중 가장 작은 값.
이중 for문으로 정렬되지 않은 배열 중 가장 처음꺼부터 다음 원소와 비교하면서 값이 작으면 minValueIndex를 업데이트 해줌. 그리고 가장 작은 minValueIndex번째의 원소를 정렬되지 않은 가장 작은 인덱스인 arr[i] 에 넣고 minValueIndex번째의 원소에 원래 arr[i]에 있던 원소를 넣어줌(바꿔치기)

따라서 등차수열의 합만큼 실행됨.
(n-1) + (n-2) +... + 2 + 1 = n(n-1)/2 = n^2-n/2

=> 시간 복잡도는 O(n^2)

💡요약💡
장점: 이해와 구현이 간단함

단점: 성능이 O(n^2)으로 좋지 않음.

function SelectionSort(arr){
    for(let i = 0; i < arr.length - 1; i++){
        let minValueIndex = i;

        for(let j = i + 1; j < arr.length; j++){
            if(arr[j] < arr[minValueIndex]){
                minValueIndex = j;
            }
        }

        let temp = arr[i];
        arr[i] = arr[minValueIndex];
        arr[minValueIndex] = temp;
    }
}

삽입정렬(Insertion Sort)

삽입정렬이란?
정렬되지 않은 영역의 가장 앞에 있는 숫자를 하나씩 정렬된 영역이 적절한 위치에 삽입을 하며 정렬을 진행.

배열을 두 영역으로 나눠서 진행.

하나는 정렬된 영역이고 하나는 정렬되지 않은 영역.

가장 첫번째 숫자만 정렬되어 있다고 가정. 정렬되지 않은 영역의 첫번째 원소를 정렬된 영역의 가장 마지막 원소부터 역순으로 비교.

첫번째 원소는 정렬되어있다고 가정하기 때문에 i 는 0이 아닌 1부터 시작. 정렬된 영역의 마지막 원소는 정렬되지 않은 영역의 첫번째 원소의 한칸 앞. 역순으로 순회. 순회하는 인덱스의 원소가 삽입할 원소보다 크다면 오른쪽 인덱스에 덮어써주기. j+1의 위치에 삽입.

따라서 등차수열의 합만큼 실행됨.
(n-1) + (n-2) +... + 2 + 1 = n(n-1)/2 = n^2-n/2

=> 시간 복잡도는 O(n^2)

💡요약💡
장점: 이해와 구현이 간단함

단점: 성능이 O(n^2)으로 좋지 않음.

function InsertionSort(arr){
    for(let i = 1; i < arr.length; i++){
        let insertingData = arr[i];
        let j;
        for(j = i - 1; j >= 0; j--){
            if(arr[j] > insertingData){
                arr[j + 1] = arr[j];
            }else{
                break;
            }
        }
        arr[j + 1] = insertingData;
    }
}

병합정렬(Merge Sort)

병합정렬이란?
재귀로 정렬하는 알고리즘.배열의 시작과 끝을 더해서 중간으로 나눠서 각각 정렬해서 합친다.

배열의 시작 = leftIndex, 배열의 가장 마지막 = rightIndex

합치기 위해서 원래의 배열과 크기가 같은 빈 배열을 만들어준다.

leftAreaIndex는 왼쪽 영역의 배열에서 비교할 원소의 인덱스. rightAreaIndex는 오른쪽 영역의 배열에서 비교할 원소의 인덱스. tempArrIndex는 비교를 마치고 값을 넣어줄 인덱스. leftAreaIndex의 원소와 rightAreaIndex의 원소를 비교해서 작은 값을 tempArrIndex에 넣어준다. 둘중 작은 값이 속한 배열의 인덱스와 tempArrIndex를 하나씩 올려준다. 그렇게 반복해서 leftAreaIndex가 rightAreaIndex의 범위까지 올라오면 rightAreaIndex는 이미 다 정렬이 된거니까 그대로 가져와서 tempArr에 넣어주고 tempArr를 복사한다.

따라서 머지 함수 내에서 배열을 합칠때는 비교연산을 두번함. 각 단계를 거칠때마다 영역의 수가 반으로 줄기 때문에 logn. 분할된 배열을 병합할때는 n개의 데이터를 n번 비교하므로 n * logn

=> 시간 복잡도는 O(nlongn)

💡요약💡
장점: 이해와 구현이 어려움

단점: 성능이 O(nlongn)으로 좋음.

function MergeSort(arr, leftIndex, rightIndex){
    if(leftIndex < rightIndex){
        let midIndex = parseInt((leftIndex + rightIndex) / 2);
        MergeSort(arr, leftIndex, midIndex);
        MergeSort(arr, midIndex + 1, rightIndex);
        Merge(arr, leftIndex, midIndex, rightIndex);
    }
}

function Merge(arr, leftIndex, midIndex, rightIndex){
    let leftAreaIndex = leftIndex;
    let rightAreaIndex = midIndex + 1;

    let tempArr = [];
    tempArr.length = rightIndex + 1;
    tempArr.fill(0, 0, rightIndex + 1);

    let tempArrIndex = leftIndex;
    while(leftAreaIndex <= midIndex && rightAreaIndex <= rightIndex){
        if(arr[leftAreaIndex] <= arr[rightAreaIndex]){
            tempArr[tempArrIndex] = arr[leftAreaIndex++];
        }else{
            tempArr[tempArrIndex] = arr[rightAreaIndex++];
        }
        tempArrIndex++;
    }

    if(leftAreaIndex > midIndex){
        for(let i = rightAreaIndex; i <= rightIndex; i++){
            tempArr[tempArrIndex++] = arr[i];
        }
    }else{
        for(let i = leftAreaIndex; i <= midIndex; i++){
            tempArr[tempArrIndex++] = arr[i];
        }
    }

    for(let i = leftIndex; i <= rightIndex; i++){
        arr[i] = tempArr[i];
    }
}

퀵정렬(Quick Sort)

퀵정렬이란?
분할 정복 알고리즘으로 피벗을 활용하여 배열을 좌우로 나눠서 재귀호출 후 정렬.

정렬하기 전에 배열에 있는 숫자 중 하나를 피벗으로 설정.

배열의 가장 왼쪽 값을 피벗으로 설정.

leftStartIndex는 오른쪽으로 이동하다가 피벗보다 큰 값을 만나면 멈춤.rightStartIndex는 왼쪽으로 이동하다가 피벗보다 작은 값을 만나면 멈춤.leftStartIndex와 rightStartIndex가 만나면 둘의 값을 교환. 둘이 서로 지나친다면 더이상 진행하지 않음. 이때 피벗과 rightStartIndex값을 교환.

퀵정렬은 한번 진행될 때마다 피벗이 정렬되고 정렬된 배열을 좌우로 나눠서 같은 방식으로 재귀호출해 모든 배열을 정렬.

따라서 피벗을 기준으로 데이터를 반으로 나누니까 logn. 이렇게 나눠진 단계를 배열의 원소 n만큼 진행하니까 평균적으로는 O(nlongn). 최악의 경우피벗이 한쪽에 치우치면 O(n^2)
=> 병합정렬보다 더 적은 비교와 더 적은 메모리 공간을 차지해서 일반적으로는 더 좋은 알고리즘으로 평가.

💡요약💡
장점: 이해와 구현이 어려움

단점: 성능이 O(nlongn)으로 좋음.

function quickSort(arr, left, right){
    if(left <= right){
        let pivot = divide(arr, left, right);
        console.log(right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }
}

function divide(arr, left, right){
    let pivot = arr[left];
    let leftStartIndex = left + 1;
    let rightStartIndex = right;

    while(leftStartIndex <= rightStartIndex){
        while(leftStartIndex <= right && pivot >= arr[leftStartIndex]){
            leftStartIndex++;
        }

        while(rightStartIndex >= (left + 1) && pivot <= arr[rightStartIndex]){
            rightStartIndex--;
        }

        if(leftStartIndex <= rightStartIndex){
            swap(arr, leftStartIndex, rightStartIndex);
        }
    }

    swap(arr, left, rightStartIndex);
    return rightStartIndex;
}

function swap(arr, index1, index2){
    let temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}