JS 정렬 알고리즘

- 선택 정렬

: 매 단계 중 처리되지 않은 가장 적은 원소를 선택해서 앞으로 보내는 정렬 방법

  매 단계에서 가장 작은 것을 선택하는 데에 약 N번의 연산이 필요. 이러한 연산을 N번 하므로 시간 복잡도는 N*N

 

시간복잡도 : O(N^2)

 

동작 방식:

1. 각 단계에서 가장 작은 원소 선택

2. 현재까지 처리되지 않은 원소들 중 가장 앞의 원소와 위치를 교체

function selectionSort(arr){
    for (let i=0 ; i<arr.length ; i++){
        let minIndex = i;
        for (let j = i+1 ; j>arr.length ; j++){
            if (arr[minIndex] > arr[j]){
                minIndex = j;
            }
        }
    // swap
    let temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
}

 

- 버블 정렬

: 단순히 인접한 두 원소를 확인하여, 정렬이 안 되어 있다면 위치를 서로 변경

 

시간복잡도 : O(N^2)

 

 이미 정렬된 배열에 대해서 모든 비교가 필요하므로, 굉장히 비효율적인 알고리즘

 

동작 방식:

1. 한 번의 단계가 수행되면, 가장 큰 원소가 맨 뒤로 이동

2. 그 다음 단계에서는 맨 뒤로 이동한 데이터는 정렬에서 제외. 즉 각 단계를 거칠 때마다 가장 큰 값을 하나씩 확실하게 결정

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

 

- 삽입 정렬

: 각 숫자를 적절한 위치에 삽입하는 정렬

  매 단계에서 현재 처리 중인 원소가 삽입될 위치를 찾기 위해 N번의 연산 필요

  따라서 최악의 경우 시간 복잡도 : O(N^2)

 

동작 방식:

1. 각 단계에서 현재 원소가 삽입될 위치를 찾음

2. 적절한 위치에 도달할 때까지 반복적으로 왼쪽으로 이동 (처음에 첫 번째 원소는 정렬 되어 있다고 가정.)

 

function insertSort(arr){
    for (let i =1 ; i<arr.length; i++) {
        for (let j = i ; j>0 ; j--) {
            // 인덱스 j부터 1까지 1씩 감소
            if (arr[j-1]) > arr[j]) {
                // 한 칸 씩 왼쪽으로 이동
                // swap
                let tmp = =arr[j]
                arr[j] = arr[j-1]
                arr[j-1] = tmp
            }
            else {
                // 자기보다 작은 데이터 만나면
                break
            } 
        }  
    }
}

 

* 분할 정복

1. 분할: 큰 문제를 작은 부분 문제로 분할한다.

2. 정복: 작은 부분 문제를 각각 해결한다.

3. 조합: 해결한 부분 문제의 답을 이용하여 다시 큰 문제를 해결한다.

 

분할 정복은 일반적으로 재귀 함수를 이용하여 구현.(큰 문제를 작은 문제로 분할하는 방식이 동일한 경우가 많기 때문)

더 이상 쪼갤 수 없는 크기가 될 때까지 계속 분할

* 단점: 재귀 함수를 사용한다는 점에서 overhead 발생 가능

 

 

- 병합 정렬:

전형적인 분할 정복 알고리즘

시간 복잡도: O(NlogN)

장점: 최악의 경우에도 NlogN을 보장할 수 있음

단점: 일반적인 경우, 정복 과정에서 임시 배열이 필요

 

~~~

 

 

- 정렬 라이브러리:

sort() 함수 제공. -> 최악의 경우에도 O(NlogN) 보장

arr.sort(compareFunction)

여기서 compareFunction은 정렬 기준을 정해주는 함수(ex 내림차순, 오름차순 등)

compareFunction을 사용하지 않으면, 각 원소는 문자열로 취급된다.