정렬

정렬이란?

• 키를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업
• 정렬을 하면 검색할 때 더 쉽게 찾을 수 있다
  • ex) 가나다 순, 알파벳 순, 오름차순, 내림차순

내부정렬

• 정렬할 모든 데이터를 하나의 배열에 저잗ㅇ할 수 있는 경우 사용함

외부정렬

• 정렬할 데이터가 많아서 하나의 배열에 저장할 수 없는는경우 사용함

버블정렬

이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘
단순 교환 정렬이라고도 함

동작원리

• 이웃한 원소를 비교하고, 필요하면 교환하는 방식으로 동작함 ⇒ 패스
• 제일 마지막 원소부터 정렬을 하게 되고 패스를 한번 수행할 때마다 정렬할 대상은 1개씩 줄어듬

JS로 구현한 버블정렬

function bubbleSort(arr) {
  const n = arr.length;
  let k = 0;

  while (k < n - 1) {
    last = n - 1;
    for (let j = 0; j < n - 1 - k; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        last = j;  // 마지막으로 교환이 발생한 위치 기록
      }
    }
    k = last;  // 마지막으로 교환된 위치까지만 정렬
  }
  return arr;
}

• 마지막 교환한 위치를 last에저장 후 다음 for문 돌 때 마지막 인덱스가 저장되어 있는 last이전 까지만 스캔 범위를 제한하여 정렬하는 방법
  • 제한할 수 있는 이유 : 교환하지 않는다면 이미 정렬 된 상태로 판단하기 때문

단순 선택 정렬

가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하여 정렬하는 알고리즘

동작 원리

• 정렬하지 않은 법위에서 값이 가장 작은 원소를 선택하고, 아직 정렬하지 않은 부분의 맨 앞 원소와 교환 하는 잡업을 반복

단점

• 중복된 값이 있을 때 단순 선택 정렬을 통해 정렬하면 원래 앞에 있던 데이터와 원래 뒤에 있던 데이터의 순서가 변경된다
• 즉 안정적이지 않음
  • 3L과 3R이 변경 됨

    [3L, 4, 2, 3R, 1] --> 3L <-> 1 
    [1, 4, 2, 3R, 3L] -->  4 <-> 2
    [1, 2, 4, 3R, 3L] -->  4 <-> 3R
    [1, 2, 3R, 4, 3L] -->  4 <-> 3L
    [1, 2, 3R, 3L, 4] --> 정렬 완료

JS로 구현한 단순 선택 정렬

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let min = i;
    // j는 i + 1부터 배열 끝까지 비교해야 함
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[min]) {
        min = j;
      }
    }
    // 최솟값을 i번째 요소와 교환
    [arr[i], arr[min]] = [arr[min], arr[i]];
  }
  return arr;
}

단순 삽입 정렬 (셔틀 정렬)

주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘
단순 선택 정렬과 비슷해 보이지만 값이 가장 작은 원소를 선택하지 않는다는 점이 다름
카드를 한 줄로 늘어놓을 때 사용하는 방법과 비슷함

장점 : 이미 정렬을 마쳤거나 정렬이 거의 끝나가는 상태에서는 속도가 아주 빠르다

단점 : 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아짐

동작원리

• 두 번째 인덱스에서부터 진행
• 본인보다 작은 요소를 만날 때 까지 왼쪽 원소를 하나씩 비교
• 본인보다 작은 요소 뒤에 삽입

종료 조건

1. 정렬된 배열의 왼쪽 끝에 도달한 경우
2. temp보다 작거나 키값이 원소 arr[j -1]을 발견한 경우

계산 조건

1. j가 0보다 큰 경우
2. arr[j-1]의 값이 temp보다 큰 경우

JS로 구현한 단순 삽입 정렬

function insertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    let j = i;
    temp = arr[i];  // 현재 삽입할 원소를 임시로 저장
    // j보다 앞에 있는 원소들과 비교하여 적절한 위치를 찾음
    while (j > 0 && arr[j - 1] > temp) {
      arr[j] = arr[j - 1];  // 원소가 크면 한 칸씩 뒤로 이동
      j -= 1;               // 한 칸 앞으로 이동하여 다음 비교
    }
    arr[j] = temp;
  }
  return arr;
}

셸 정렬

먼저 정렬할 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬을 수행한 후
정렬된 그룹을 합치는 작업을 반복하여 정렬하는 방식

동작 방식

• 초기 간격을 배열 크기의 절반으로 설정합니다.
• 간격만큼 떨어진 요소끼리 삽입 정렬 방식으로 정렬합니다.
• 간격을 점점 줄여가며 배열을 더 세밀하게 정렬합니다.
• 간격이 1이 되면, 완전한 삽입 정렬을 수행합니다.

[8, 1, 4, 2, 7, 6, 3, 5]
// 4칸 떨어진 원소 2개 정렬
(8, 7) => (7, 8)
(1, 6) => (1, 6)
(4, 3) => (3, 4)
(2, 5) => (2, 5)
// 결과
[7, 1, 3, 2, 8, 6, 4, 5]
// 2칸 떨어진 원소 4개 정렬
(7, 3, 8 ,4) => (3, 4, 7, 8)
(1, 2, 6, 5) => (1, 2, 5, 6)
// 결과
[3, 1, 4, 2, 7, 5, 8, 6]
// 1칸 떨어진 원소 8개 정렬
(3, 1, 4, 2, 7, 5, 8, 6) => (1, 2, 3, 4, 5, 6, 7, 8)

• 단순 삽입정렬의 장점은 살리고 단점을 보완하기 위해 사용됨
• 정렬 회수는 늘어나지만 전체적으로 원소의 이동 횟수가 줄어들어 효율적임

JS로 구현한 쉘 정렬

function shellSort(arr) {
  const n = arr.length;
  h = Math.floor(n / 2);  // 초기 gap을 배열 크기의 절반으로 설정
  while (h > 0) {
    for (let i = h; i < n; i++) {
      let j = i - h;
      let temp = arr[i];  // 현재 비교할 원소 저장

      while (j >= 0 && arr[j] > temp) {
        arr[j + h] = arr[j];  // 값을 오른쪽으로 이동
        j -= h;
      }
      arr[j + h] = temp;  // temp 값을 올바른 위치에 삽입
    }
    h = Math.floor(h / 2);  // gap을 줄임
  }
  return arr;
}

퀵 정렬

가장 빠른 정렬 알고리즘

요소를 선택하여 기준으로 삼고 그 기준을 바탕으로 오버, 언더로 그룹을 나눔
다시 각 그룹에서 피벗을 선택하여 나누기를 반복하며 모든 그룹이 1명씩 남으면 정렬이 완료

• 피벗(중심축) : 기준으로 삼은 요소
  • 2개로 나눈 그룹 어디에 넣어도 상관 없다

배열 두 그룹으로 나누는 방법

• pl : 피벗을 기준으로 맨 왼쪽에 오는 요소
• pr : 피벗을 기준으로 맨 오른쪽에 오는 요소

---

• pl ≥ x 가 성립되는 요소를 찾을 때 까지 오른쪽으로 이동
• pr ≤ x 가 성립되는 요소를 찾을 때 까지 왼쪽으로 이동

---

• 위 조건에 맞는 위치에 있는 요소 pl(피벗 보다 큰 요소), pr(피벗 보다 작은 요소)을 교환
• pl과 pr이 서로 교차하면 그룹을 나누는 과정 종료
• 무조건 요소가 1개가 남을 때까지 나눠야함

---

• 결과
  • 피벗 이하인 그룹 : arr[0] … arr[pl - 1]
  • 피벗 이상인 그룹 : arr[pr + 1] … arr[n - 1]
  • 피벗과 일치하는 그룸 : arr[pr + 1] … arr[pl -1]

JS로 구현한 피벗 나누기

  while (pl <= pr) {
    while (arr[pl] < x) {
      pl += 1;
    }
    while (arr[pr] > x) {
      pr -= 1;
    }
    if (pl <= pr) {
      [arr[pl], arr[pr]] = [arr[pr], arr[pl]];
      pl += 1;
      pr -= 1;
    }

JS로 구현한 퀵 소트

function dividePivot(arr, left, right) {
  let pl = left;
  let pr = right;
  x = arr[Math.floor((left + right) / 2)];

  while (pl <= pr) {
    while (arr[pl] < x) {
      pl += 1;
    }
    while (arr[pr] > x) {
      pr -= 1;
    }
    if (pl <= pr) {
      [arr[pl], arr[pr]] = [arr[pr], arr[pl]];
      pl += 1;
      pr -= 1;
    }
  }

	// 좌우 각그룹을 다시 나누기 위해 재귀 호출
  if (left < pr) dividePivot(arr, left, pr);
  if (right > pl) dividePivot(arr, pl, right);

  return arr;
}

function quickSort(array) {
  const a = dividePivot(array, 0, array.length - 1);
  console.log(a);
}

피벗 잘 선택하기

1. 나누어야 할 배열의 원소 수가 3 이상이면, 배열에서 임의의 원소 3개를 꺼내 중앙값인 원소를 피벗으로 선택
2. 나누어야 할 배열의 맨 앞, 가운데, 맨 끝 요소를 정렬합니다 → 맨 끝에서 두 번쨰 요소를 피벗으로 선택
   • 장점 : 그룹이 한쪽으로 치우치는 것을 피할 수 있고 스캔할 원소를 3개 줄일 수 있음