Algorithms
Selection and Insertion Sort

Createhb21·2022년 01월 13일 23:25
Selection Sort
   선택 정렬은 큰 값을 먼저 배열 끝에 위치시키는 게 아니라 최소값을 루프를 돌며 하나씩 맨 앞으로 정렬시킨다.
선택 정렬도 버블 정렬에서 사용한 것처럼 swap을 사용한다.

Selection Sort Pseudocode
최소값을 저장할 변수를 만든다, 이 변수의 최초 할당값은 배열의 첫번째 인덱스 값을 넣어준다.
최소값과 다음 인접 요소를 비교한다.
만약에 인접 요소가 더 작다면 최소값 변수의 값을 그 요소의 인덱스 값으로 설정해주고 두 값의 자리를 바꿔준다. 만약 더 작지 않다면 그냥 지나친다. 이러한 방식으로 배열의 끝까지 이동한다.
배열이 정렬될 때까지 위 과정을 반복함.

function selectionSort(arr) {
    for(let i = 0; i < arr.length; i++){
        let lowest = i;
        for(let j = i + 1; j < arr.length; j++){
            if(arr[j] < arr[lowest]) {
                lowest = j;
            }
        }
        if(i !== lowest) {
            let temp = arr[i];        
            arr[i] = arr[lowest];        
            arr[lowest] = temp;
        }
    }
    return arr;
}

selectionSort([0, 2, 34, 22, 10, 19, 17])


// ES 2015 
function selectionSort(arr) {
    const swap = (arr, idx1, idx2) => {
        ([arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]);
    }
    
    for (let i = 0; i< arr.length; i++) {
        let lowest = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[lowest] > arr[j]) {
                lowest = j;
            }
        }
        if (i !== lowest) swap(arr, i, lowest);
    }
    
    return arr;
}

selectionSort([0, 2, 34, 22, 10, 19, 17]) 


About Bit O 
선택 정렬은 효율이 정말 떨어진다. 시간 복잡도가 n제곱의 값이다. 아주 특정한 상황에서는 버블 정렬보다는 좀 더 나은 선택지일 수는 있다. 



Insertion Sort
   세 번째 초급 정렬 알고리즘으로 넘어가보자. 마지막 초급 정렬 알고리즘이기도 하다. 삽입 정렬은 버블 정렬이나 선택 정렬과 꽤 비슷하다. 그렇지만 몇 가지 중요한 차이점도 있는데, 삽입 정렬이 특히나 좋은 경우도 있다. 

삽입 정렬은 배열의 절반 이상을 두고 조금씩 쌓아가면서 정렬을 한다. 이 절반 이상은 항상 정렬되어 있어야 한다. 하나씩 보면서 가장 큰 값을 찾거나, 하나씩 보면서 가장 작은 값을 찾는 대신에 각 요소를 보면서 이미 정렬되어 있는 절반에서 어디로 가야 하는지 찾고 거기로 보낸다(삽입한다). 예시를 보자 !

Insertion Sort Pseudocode
배열의 두 번째 요소를 집어든다. 맨 처음에는 첫 번째 요소만이 정렬된 부분이라고 생각해야함
두 번째 요소를 취해서 바로 앞에 있는 요소와 비교를 한다. 그리고 필요하다면 자리를 바꿔준다. 
그 다음 요소와도 비교를 해서 정확한 자리에 있는지를 확인한다. 그러니까 정렬된 부분 전체를 순회한다. 
배열이 정렬될 때까지 반복한다.

function insertionSort(arr) {
    for (let i  = 1; i < arr.length; i++) {
        let currentVal = arr[i];
        for(let j = i - 1; j >= 0 && arr[j] > currentVal'; j--) {
            arr[j+1] = arr[j]
        }
        arr[j+1] = currentVal;
    }
    return arr;
}

insertionSort([2, 1, 9, 76, 4]);


About Big O
   삽입 정렬의 시간 복잡도는 앞의 둘과 전체적으로는 꽤 비슷하다. 최악의 경우에는 n제곱이 되어 2차 함수 관계가 되는데, 즉 배열의 길이가 늘어날수록 비교하는 횟수는 n의 제곱이 된다. 그렇지만 만약에 데이터가 거의 다 정렬되어 있다면, 예를 들어 다음과 같은 식의 데이터가 있다면 [1, 2, 3, 4, -1] 삽입 정렬에서 사용하기 베스트 케이스이고, 반대로 [5, 4, 3, 2, 1] 과 같은 데이터는 최악의 경우일 것이다. 

또한 (별로 흔한 상황은 아니지만) 실시간으로 입력받아야 하는 데이터를 정렬해야 할 때에도, 삽입 정렬을 큰 이점이 있다. 예를 들어 실시간으로 사람들이 숫자를 보내고, 그 숫자들을 정렬해야 한다고 할 때, 삽입 정렬은 유용하다. 어떤 숫자가 입력되는지 상관 없이 그 숫자가 가야할 곳으로 보낼 수 있기 때문이다. 즉, 삽입 정렬은 배열의 한 쪽에 정렬된 것들을 넣어두고 요소들의 제자리를 찾아서 삽입해주기 때문에 데이터가 실시간으로 입력되거나 해서 매번 그 데이터들을 삽입해줘야 하는 경우에 유용하다.



버블, 선택, 삽입 정렬 비교
# algorithms# insertion# selection# sorting