선택정렬

설명:

• 배열에서 최소값을 찾아서 맨앞 요소와 swap
• 정렬이 완료될수록 정렬된 구간과 미정렬 구간이 나뉨
• 비교는 모두 진행된다

최선	평균	최악
O(n²)	O(n²)	O(n²)

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) { // 현재요소 외 모든요소. 탐색 
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) minIdx = j; 
      // 만약 minimum 보다 작다면 swap 
    }
    [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]]; 
  }
  return arr;
}

삽입정렬

설명:

• 인덱스를 1 즉 배열의 두번째 부터 왼쪽으로 한칸씩 옮기며 자신의 위치를 찾아서 삽입

• 최선	평균	최악
  O(n)	O(n²)	O(n²)

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      // while문의 조건 현 arr[j] 가 key 보다  작을때  즉 왼쪽이랑 비교 break 
      arr[j + 1] = arr[j]; //왼쪽이 더크면  swap() 
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

셸정렬

• 삽입 정렬의 개선 버전
• 삽입 정렬의 단점으 (n-1) 인덱스 원소 즉 끝 원소의 자리가 0번째라면 엄청 많은 교환을 해줘야함
• 간격 (gap) 을 정해서 배열을 부분 배열로 나누어서 정렬시키고 해당 간격을 줄여서 정렬시키는걸 반복 대부분 배열의 절반을 간격으로 줌
• 간격만큼 떨어진 원소들 끼리 교환 즉 삽입 정렬 수행
• 이후 간격을 절반으로 줄이면서 정렬

최선	평균	최악
O(nlogn)	O(nlongn)	O(nlogn)

function shellSort(arr) {
  let n = arr.length;
  let gap = Math.floor(n / 2); // 초가 간격(gap)

  while (gap > 0) { //간격이 0 이상일때까지 반복  
    for (let i = gap; i < n; i++) {// 간격이후 배열끝까지 순회 
      let temp = arr[i]; // 요소저장용 
      let j = i;

      // 삽입 정렬 방식으로 gap 간격 비교
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap]; // 더크면 뒤로 
        j -= gap; // 비교인덱스 gap만큼 앞으로 이동  
      }

      arr[j] = temp;// 삽입위치에 temp 저장 
    }
    gap = Math.floor(gap / 2); // 간격 줄이기
  }

  return arr;
}

버블정렬

설명:

• 인접한 두 수를 비교해 교환하면서 큰 수를 뒤로 보냄
• 두개의 요소를 계속 비교해서 교환.

최선	평균	최악
O(n)	O(n²)	O(n²)

function bubbleSort(arr) {
  let n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return arr;
}

병합정렬 (Divide & Conquer)

설명:

• 인접한 두 수를 비교해 교환하면서 큰 수를 뒤로 보냄
• 분할 정복 알고리즘
• 배열의 길이가 1이 될때까지 분활하고, 분활이 완료되면 부분배열을 합병하면서 정렬하여 모든 배열을 합병
• 추가 메모리 또는 재귀함수 비용
• 큰 배열에 성능 우수 하지만 작은 배열에는 비효율적

최선	평균	최악
O(n log n)	O(n log n)	O(n log n)

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid)); // 재귀를 통해서 나누기 
  const right = mergeSort(arr.slice(mid)); // 재귀를 통해서 나누기 

  return merge(left, right);
}

function merge(left, right) {
  let result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    result.push(left[i] < right[j] ? left[i++] : right[j++]);
    // 왼쪽 오른쪽을 비교해서 결과에 정렬된 요소 push 
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

힙정렬

설명:

• 최대 힙(Max Heap)을 구성하여 가장 큰 수를 루트로 꺼냄 오름차순 루트가 가장 큰 수
• 최소 힙을 사용하영 내림차순 루트가 가장 작은 수
• 트리 기반 구조
• heapify : 하나의 노드에 대해서 수행하요 특정 노드의 두자식중 더 큰 자식과 자신의 위치를 바꾸는 알고리즘

최선	평균	최악
O(n log n)	O(n log n)	O(n log n)

function heapSort(arr) {
  const n = arr.length;

  // Max Heap 구성
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // 힙 정렬 하나씩 최대값을 끝으로. 이동 
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];// 루트와 마지막 값 교환
    heapify(arr, i, 0);// 줄어든 힙에서 다시 heapify
  }
  return arr;
}

function heapify(arr, n, i) {
  let largest = i;
  let l = 2 * i + 1; //왼쪽 자식 노드 인덱스 
  let r = 2 * i + 2; //오른쪽 자식 노드 인덱스 

    // 왼쪽 자식이 루트보다 크면 largest 갱신
  if (l < n && arr[l] > arr[largest]) largest = l;
    // 오른쪽 자식이 현재 largest보다 크면 largest 갱신
  if (r < n && arr[r] > arr[largest]) largest = r;
  
  // largest가 루트가 아니라면 swap 후, 아래 서브트리에 대해 재귀 호출
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);  // 변경된 자식 노드에 대해 다시 heapify
  }
}

퀵정렬

설명:

• 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할
• 본활하다보면 왼쪽 작은수들 와 오르쪽 큰값들로 분활됨 이때 왼쪽과 오르쪽이 교차시 즉 1cycle이 끝나면 피봇과 왼쪽을 교환

최선	평균	최악
O(n log n)	O(n log n)	O(n²)

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter(x => x < pivot);
  const middle = arr.filter(x => x === pivot);
  const right = arr.filter(x => x > pivot);

  return [...quickSort(left), ...middle, ...quickSort(right)];
}

알고리즘 츄라이츄라이

https://codepen.io/nowrobin/pen/ByNMJMo

참고한 정렬을 이해하기 쉬웠던 자료들 :
https://www.youtube.com/watch?v=FchRqQSQSuU&t=568s
https://www.youtube.com/watch?time_continue=2&v=kPRA0W1kECg
https://www.youtube.com/watch?v=KGyK-pNvWos
https://velog.io/@pppp0722/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-7%EA%B0%9C-%EC%A0%95%EB%A6%AC-Java