정렬 알고리즘

특정 원소들을 번호 순이나 사전 순서와 같이 일정한 순서대로 열거한 알고리즘 이다

=>컴퓨터 분야에서 중요시 되는 문제 중 하나이고 탐색에 용이하다

정렬 알고리즘 종류

버블정렬

가장 기초적인 알고리즘 으로 인접한 두개의 요소를 비교해가면서 정렬을 진행하는 방식

한번 돌 때마다 마지막 요소가 정렬되는 것이 거품이 올라오는 것처럼 보여 버블 정렬이라고 한다

 

 

function 버블정렬(arr) {
  for (let x = 0; x < arr.length; x++) {
    for (let y = 1; y < arr.length - x; y++) {
      if (arr[y - 1] > arr[y]) {
        [arr[y - 1], arr[y]] = [arr[y], arr[y - 1]];
      }
    }
  }

  return arr;
}

시간 복잡도 :최악,최선,평균 O(n) = n^2 

구현이 매우 간단하고, 소스코드가 직관적

기존 배열 이외의 추가적인 메모리를 거의 사용하지 않는 제자리 정렬(In-place sort)이다.

정렬된 상태에서 새로운 데이터가 추가되면 정렬 효율이 좋지 않다

 

선택 정렬

가장 기초적인 알고리즘

전체 범위에서 차례대로 가장 작은 숫자를 탐색하고 가장 왼쪽부터 차례대로 교환하는 방식

=>비교 횟수는 많지만 실제로 값을 바꾸는 교환 횟수가 적다는 것이 특징

function 선택정렬(arr) {
  let Min;
  for (let x = 0; x < arr.length - 1; x++) {
    Min = x;
    for (let y = x + 1; y < arr.length; y++) {
      if (arr[y] < arr[Min]) {
        Min = y;
      }
    }
    [arr[x], arr[Min]] = [arr[Min], arr[x]];
  }
  return arr;
}

시간 복잡도 :최악,최선,평균 O(n) = n^2 

구현이 매우 간단하고, 소스코드가 직관적

자료 이동 횟수가 미리 결정 된다

기존 배열 이외의 추가적인 메모리를 거의 사용하지 않는 제자리 정렬(In-place sort)이다

값이 같은 요소가 있다면 상대적인 위치가 변경될 수 있다

정렬된 상태에서 새로운 데이터가 추가되면 정렬 효율이 좋지 않다

 

삽입 정렬

가장 기초적인 알고리즘

모든 요소를 앞에서부터 차례대로 이미 정렬된 배열부분과 비교하여 자신의 위치를 찾아 삽입하는 방식

버블정렬은 i번째와 i+1번째를 비교하며 위치를 바꾸었다면, 삽입 정렬은 i번째 원소를 정렬된 상태의 앞부분과 비교하여 적절한 위치에 삽입하는 방식

버블 정렬의 비효율성을 개선하기 위해 등장한 방법

 

 

 

function 삽입정렬 (arr) {
  for (let x = 1; x < arr.length; x++) {
    let value = arr[x];
    let prev = x - 1;
    while (prev >= 0 && arr[prev] > value) {
      arr[prev + 1] = arr[prev];
      prev--;
    }
    arr[prev + 1] = value;
  }

  return arr;
}

시간 복잡도 :최악 ,평균O(n) = n^2 ,최선 = O(n)

입력으로 들어오는 배열의 원소가 정렬되어있을수록 속도가 빠르다

정렬된 값은 교환이 일어나지 않기 때문에 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는 현실적으로 최고의 정렬 알고리즘이다

버블정렬 선택 정렬보다 상대적으로 빠르다

버블정렬 선택 정렬 과 마찬가지로 배열의 길이가 길어질수록 비효율적이다

 

💡선택 정렬은 i+1번째 원소를 찾기 위해 나머지 모든 원소들을 탐색하지만  삽입 정렬은 i+1번째 원소를 배치하는데 필요한 만큼의 원소만 탐색하기 때문에 훨씬 효율적으로 실행된다는 차이가 있습니다.

 

병합 정렬

복잡하지만 효율적인 알고리즘

분할 정복 이라는 알고리즘 디자인 기법에 근거하여 복잡한 문제를 복잡하지 않는 문제로 분할하여 정복하는 방식

병합 과정에서 정렬이 이루어진다

 

분할정복

상단에서 분할하고 중앙에서 정복하고 하단에서 조합(Combine)하는 형태로 도식화 할 수 있다

• 분할: 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다.
• 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.
• 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.
  
  

배열을 왼쪽 절반, 오른쪽 절반으로 분할하며 최소 단위로 쪼갠 후 정렬을 진행 한다

쪼갠 영역들(이미 정렬이 있는)을 차례대로 두개씩 병합(merge)한다

function 병합정렬 (leftArr, rightArr) {
  const sortedArr = [];
  let l = 0;
  let r = 0;

  while (l < leftArr.length && r < rightArr.length) {
    if (leftArr[l] <= rightArr[r]) {
      sortedArr.push(leftArr[l]);
      l++;
    } else {
      sortedArr.push(rightArr[r]);
      r++;
    }
  }
  
  while (l < leftArr.length) {
    sortedArr.push(leftArr[l]);
    l++;
  }

  while (r < rightArr.length) {
    sortedArr.push(rightArr[r]);
    r++;
  }

  return sortedArr;
}

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

  const mid = Math.ceil(arr.length / 2);

  const leftArr = arr.slice(0, mid);
  const rightArr = arr.slice(mid);

  return merge(mergeSort(leftArr), mergeSort(rightArr));
}

시간 복잡도 :최선, 평균, 최악 모두 O(nlogn) =>분할할 때 걸리는 시간은 O(n), 병합에 걸리는 시간은 O(n)레벨의 수가 O(logn)이므로 전체 레벨의 병합에 걸리는 총시간은 O(nlogn)

항상 일정한 시간 복잡도 O(nlogn)를 가진다

정렬을 하는 배열외의 추가적인 임시 배열 (추가적인 메모리)가 필요하다

정렬하고자 하는 배열의 크기만큼의 추가적인 크기가 요구되기 때문에 Not In-place (별도의 추가적인 메모리(임시배열)을 사용)정렬이다

 

퀵 정렬

복잡하지만 효율적인 알고리즘 (전설)

분할 정복(divide and conquer) 방법을 통한 정렬로 특정 요소를 기준점(pivot)으로 잡고 기준점보다 작은 요소는 왼쪽 기준점보다 큰요소는 오른쪽으로 두고 왼쪽과 오른쪽을 가각 정복하는 방식

 

const 퀵정렬 = function (arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] <= pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }

  const lSorted = quickSort(left);
  const rSorted = quickSort(right);
  return [...lSorted, pivot, ...rSorted];
};

시간 복잡도 :최선, 평균=O(nlogn), 최악 =O(n^2) 

평균 실행시간이 다른 알고리즘보다 빠른 편이다

불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환한다

한 번 결정된 축(pivot)들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도 O(nlogn)을 가지는 다른 정렬 알고리즘과 비교했을 때 가장 빠르다

정렬하고자 하는 배열 안에서 교환하는 방식이므로 In-place 정렬

정렬된 배열에 대해서는 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다

축(pivot)따라 성능차이가 심하다=>중간에 가까운 값을 찾을 수록 성능이 좋지만 그게아닐 경우

힙 정렬

힙 정렬은 최대 힙 트리(Max Heap Tree)나 최소 힙 트리(Min Heap Tree)를 구성하여 정렬하는 방식

힙(Heap)은 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조

최대 힙 트리 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

최소 힙 트리 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

힙 정렬은 여러 개의 값중에서 최댓값이나 최솟값을 빠르게 찾기 위해 사용된다

root 노드를 하나씩 꺼내어 배열의 뒤쪽부터 넣고 빈 root 노드 자리에는 힙 트리의 가장 뒤에 있는 원소가 들어가서 자기 자리를 찾아갑니다.

 

시간 복잡도 :최선, 평균=O(nlogn), 최악 =O(n^2) 

가장 크거나 가장 작은 값을 구할 때 유용하다 → 한번의 힙 구성을 통해 구하는 것이 가능하다.

멀리 떨어진 요소들을 정렬할 때 유용하다 → 삽입정렬보다 더욱 개선된 결과를 얻어낼 수 있다

항상 같은 시간 복잡도를 가지기 때문에 성능이 준수하다

주어진 배열 내부에서 위치를 바꾸는 방식으로 하면 in-place 정렬이 가능하다

같은 시간 복잡도를 가지는 다른 정렬 알고리즘과 비교하면 느린 편이다

퀵정렬과 합병정렬의 성능이 좋기 때문에 힙 정렬의 사용빈도가 높지는 않다

Unstable(불안정 정렬의 경우에는 정렬 후에도 원래의 순서가 유지된다는 보장을 할 수 없다) 정렬이다

https://east-star.tistory.com/10