거품, 선택, 삽입 정렬

https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html 참고

거품 정렬(Bubble Sort) | 👨🏻‍💻 Tech Interview

// ctrl, alt, n -> 자바스크립트 실행

let arr =[2,4,50,1,8,12,11,9,5,23,55,41,33,93,26,7]
console.log("not sorted " + arr)

/* 
버블정렬(Bubble Sort)
- 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘
- 여기서는 인접한 두 수를 비교해서 작은수를 앞에, 큰수를 뒤에 놓는다.
#장점
구현이 매우 간단하고, 소스코드가 직관적이다.
정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않다. => 제자리 정렬(in-place sorting)
안정 정렬(Stable Sort) 이다.

#단점
시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적이다.
정렬 돼있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 된다
*/

function bubbleSort(arr){
    let temp = 0; // swap 용의 임시변수
    for(let i=0; i<arr.length; ++i){ // 받아온 arr의 길이만큼, for loop을 돌아준다
        for(let j=1; j<arr.length-i; ++j){ // 원소를 비교할 index를 뽑을 반복문이다. j는 현재 원소를 가리키고, j-1은 이전 원소를 가리키게 되므로, j는 1부터 시작하게 된다.
            if(arr[j-1] > arr[j]){ // swap
                temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    
}

//bubbleSort(arr);
//console.log("bubble sorted " + arr)

/*
선택 정렬(Selection Sort)
- 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
- 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것
- 배열의 최소값을 찾고, 그 값이랑 제일 앞의 갚을 교체
#장점
Bubble sort와 마찬가지로 알고리즘이 단순하다.
정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.
Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)

#단점
시간복잡도가 O(n^2)으로, 비효율적이다.
불안정 정렬(Unstable Sort) 이다.
*/ 

function selectionSort(arr) {
    let temp;
    let indexMin;
    for(let i=0; i<arr.length-1; ++i){
        indexMin = i; // 배열의 최소값을 선택
        for(let j=i+1; j<arr.length; ++j){ // i+1번째 원소부터 선택한 위치(index)의 값과 비교를 시작한다.
            if(arr[j] < arr[indexMin]){ // 만약에 i+1번째의 원소가 선택한 위치보다 값이 작으면 넘어감
                indexMin = j;
            }
        }
        // swap
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
    }
}

// selectionSort(arr);
// console.log("selection sorted " + arr)


/*
삽입 정렬(Insertion Sort)
- 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입
- 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있다.
#장점
알고리즘이 단순하다.
대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있다.
정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)
안정 정렬(Stable Sort) 이다.
Selection Sort나 Bubble Sort과 같은 O(n^2) 알고리즘에 비교하여 상대적으로 빠르다.

#단점
평균과 최악의 시간복잡도가 O(n^2)으로 비효율적이다.
Bubble Sort와 Selection Sort와 마찬가지로, 배열의 길이가 길어질수록 비효율적이다.
*/

function insertionSort(arr)
{// 1.첫 번째 원소 앞(왼쪽)에는 어떤 원소도 갖고 있지 않기 때문에, 두 번째 위치(index)부터 탐색을 시작한다.
// temp에 임시로 해당 위치(index) 값을 저장하고, prev에는 해당 위치(index)의 이전 위치(index)를 저장한다.
   for(let index = 1 ; index < arr.length ; index++){ 
      let temp = arr[index];
      let prev = index - 1;
      //이전 위치(index)를 가리키는 prev가 음수가 되지 않고, 이전 위치(index)의 값이 '1'번에서 선택한 값보다 크다면, 서로 값을 교환해주고 prev를 더 이전 위치(index)를 가리키도록 한다.
      while( (prev >= 0) && (arr[prev] > temp) ) {    
         arr[prev+1] = arr[prev];
         prev--;
      }
      //반복문이 끝나고 난 뒤, prev에는 현재 temp 값보다 작은 값들 중 제일 큰 값의 위치(index) 를 가리키게 된다. 따라서, (prev+1)에 temp 값을 삽입해준다.
      arr[prev + 1] = temp;                       
   }
}
// insertionSort(arr);
// console.log("insertion sorted " + arr)