정렬

코딩덕·2022년 11월 18일

CodingTest

알고리즘

목록 보기

2/5

정렬

데이터를 특정한 기준에 따라서 순섣대로 나열하는 것으로 버블정렬, 선택정렬, 삽입정렬, 퀵정렬, 계수정렬 등이 있다.

1. 버블 정렬

데이터가 무작위로 여러개가 있을 때, 서로 인접해 있는 요소 간의 대소 비교를 통해 정렬한다.
버블 정렬은 정렬 알고리즘 중 가장 단순한 알고리즘으로, 단순한 만큼 비효율적이다.

✔ 버블정렬코드

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

2. 선택 정렬

데이터가 무작위로 여러개가 있을 때, 이중에서 가장 작은 데이터를 선택해 맨앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복한다.
선택정렬은 다른 알고리즘에 비해 매우 비효율적이지만 특정리스트에서 가장작은 데이터를 찾는데에는 용이하다.

✔ 선택정렬코드

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    const swap = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = swap;
  }
  return arr;
}

3. 삽입 정렬

데이터가 이미 정렬되어있다고 생각하고 두번째 데이터부터 시작하여 적절한 위치를 찾아 삽입하는 방식이다. 따라서 삽입정렬은 입력값이 거의정렬이 되어있는 상태로 주어지는 문제라면 아주 효율적이다.

✔ 삽입정렬코드

function insertionSort(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 + 1] = arr[j];
    }
    arr[j + 1] = currentVal;
  }
  return arr;
}

4. 퀵 정렬

데이터가 무작위로 여러개있을 때, 첫번째 데이터를 기준(피벗)으로 잡고 왼쪽에서부터 피벗보다 큰 데이터를 찾고 오른쪽에서부터 작은 데이터를 찾은 뒤 서로 교환해준다. 이렇게 계속 교환해주다가, 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 엊갈린다면 작은데이터와 피벗을 교체한다. 그 뒤, 피벗기준으로 나뉜 양쪽의 리스트들을 방금의 방식으로 개별 정렬시킨다.
따라서 퀵정렬은 입력값이 무작위로 주어지는 상태의 경우 아주 효율적이지만 입력값이 거의 정렬되어있는 상태라면 비효율적이다.

✔ 퀵정렬코드

function quickSort(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]);
    }
  }

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

4. 계수 정렬

특정한 조건(데이터의 크기 범위가 제한되어 정수형태로 표현할수 있는경우)에서 매우 효율적이다. 이전의 정렬 알고리즘처럼 직접 데이터값들을 비교한 후, 위치를 변경하면서 정렬하는 것이 아니라 별도의 리스트를 선언하고 그 안에 데이터들의 정보를 저장하는 식으로 정렬한다.
따라서 계수정렬은 데이터의 크기가 한정되어있고, 데이터의 크기가 많이 중복되어 있을경우 아주 효율적이지만 항상 사용할 수는 없다. 그러므로 데이터의 특성을 파악하기 어렵다면 퀵정렬을 이용한다.