(JS 알고리즘)정렬 알고리즘

• 정렬 알고리즘 : 항목을 재정렬 하여 항목이 일종의 순서로 정렬되도록 하는 과정을 의미한다.

버블정렬

• 각 요소를 루프로 돌면서, 다음 요소가 비교하는 값보다 큰 지 작은 지를 확인하고 자리를 바꾸는 과정(swap)을 반복한다. 즉, 바로 옆에 있는 것과 비교해서 크면 자리를 바꾼다.
• 값들이 차례로 버블을 타고 본인의 크기에 맞는 가장 위로 올라가는 방식으로 리스트가 재배열된다.
  • 즉, 가장 큰 값이 위로 버블링되는 정렬 알고리즘이다.
• 많은 정렬 알고리즘에는 일부 유형의 SWAP 기능이 포함되어 있다.

function swap(arr,idx1,idx2){
  let temp = arr[idx1] //값이 바뀌기전에 미리 저장해 둠
  arr[idx1] = arr[idx2];
  arr[idx2] = temp;
}

function swap(arr,idx1,idx2){
  [arr[idx1],arr[idx2]] = [arr[idx2],arr[idx1]];
}

버블정렬 의사코드

• 배열의 끝까지 루프 시작
• j와 j+1 을 비교하는 반복을 i번 한다
  • 루프를 반복할때마다 배열 끝에 가장 큰 값이 정렬됨

버블정렬 코드

function bubbleSort(arr) {
  //한번 루프를 돌면 가장 큰 값부터 하나씩 차례대로 정렬됨
  for (let i = arr.length; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      console.log(arr, arr[j], arr[j + 1]);
      if (arr[j] > arr[j + 1]) [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
    }
    console.log('one pass complete');
  }
  return arr;
}

const array = [5, 3, 12, 7, 14, 2];
console.log(bubbleSort(array));

/* 
[ 5, 3, 12, 7, 14, 2 ] 5 3
[ 3, 5, 12, 7, 14, 2 ] 5 12
[ 3, 5, 12, 7, 14, 2 ] 12 7
[ 3, 5, 7, 12, 14, 2 ] 12 14
[ 3, 5, 7, 12, 14, 2 ] 14 2
one pass complete
[ 3, 5, 7, 12, 2, 14 ] 3 5
[ 3, 5, 7, 12, 2, 14 ] 5 7
[ 3, 5, 7, 12, 2, 14 ] 7 12
[ 3, 5, 7, 12, 2, 14 ] 12 2
one pass complete
[ 3, 5, 7, 2, 12, 14 ] 3 5
[ 3, 5, 7, 2, 12, 14 ] 5 7
[ 3, 5, 7, 2, 12, 14 ] 7 2
one pass complete
[ 3, 5, 2, 7, 12, 14 ] 3 5
[ 3, 5, 2, 7, 12, 14 ] 5 2
one pass complete
[ 3, 2, 5, 7, 12, 14 ] 3 2
one pass complete
one pass complete
[ 2, 3, 5, 7, 12, 14 ] 
*/

코드 최적화

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

const array = [5, 3, 12, 7, 14, 2];

버블정렬의 빅오복잡도

• Best Case : O(n)
  • noSwap기능을 추가하여 데이터가 거의 정렬되어 있는 배열에 버블정렬을 사용할 경우
• O(n^2)

선택정렬

• 버블 정렬과 유사하지만, 큰 값이 아닌 작은 값부터 찾아서 정렬
• 루프를 돌면서 가장 작은 값을 찾고 최소값을 루프 시작점에 둔다.

선택정렬 의사코드

• 첫번째 요소를 가장 작은 값으로 설정
  • 루프를 돌며 더 작은 값을 찾으면 그 숫자를 최소값으로 업데이트
  • 배열의 끝에서, 최소값이 처음 시작한 값이 아니면 두 값을 바꾼다.
• 배열이 모두 정렬될 때까지 반복

선택정렬 코드

function selectsort(arr){
    for(let i=0; i<arr.length; i++){
        let min = i;
        for(let j=i+1; j<arr.length; j++){
            if(arr[min] > arr[j]){
                min = j;
            }
        }
        if(i !== min){
            [arr[i],arr[min]] = [arr[min],arr[i]];
        }
    }
    return arr;
}

선택정렬 빅오 복잡도

• O(n^2)
  • 선택 정렬을 효율이 좋지 않다
  • 최소값을 찾기위해 모든 요소를 확인해야만 하기 때문에 거의 정렬된 경우에도 모든 반복을 수행한다

삽입정렬

• 한 번에 하나의 항목을 올바른 위치에 삽입하여 배열의 정렬된 부분을 점진적으로 구축해 나간다.

삽입정렬 의사코드

• 배열에서 두 번째 요소를 선택하여 시작(첫 번째 요소는 정렬된 요소로 구분)
• 두 번째 값을 취해 앞에 있는 값과 비교
• 필요하다며 값을 스왑해주고 옆의 요소로 이동하여 올바른 위치에 있는지 확인
• 다 정렬될 때까지 위 작업 반복

삽입정렬 코드

function insertsort(arr){
    for(let i=1; i<arr.length; i++){
        let currentVal = arr[i];
        let j;
        for(j=i-1; j>=0 && arr[j] > currentVal; j--){ //arr[j]가 cur보다 클때 루프 실행
            arr[j+1] = arr[j];    
        }
        arr[j+1] = currentVal;
    }
    return arr;
}

삽입정렬 빅오복잡도

• 삽입정렬은 무작위 배열보다 거의 정렬된 배열에서 빠르다
  Best : O(n)
  Avg,Worst : O(n^2)

기본 정렬알고리즘 비교

• 평균적인 시간 복잡도는 O(n^2)이지만 Best case에서 버블과 삽입정렬은 O(n)으로 선택정렬 보다 빠르다.
• 작은 데이터를 정렬할 때는 유용하게 쓸 수 있다.