TIL 7 | 알고리즘 - 정렬

grighth12·2021년 8월 10일
1

TIL

목록 보기
7/15
post-thumbnail

정렬

  • 요소들을 일정한 순서대로 열거하는 알고리즘이다.
  • 정렬 기준은 사용자가 정할 수 있다. ex) 오름차순, 내림차순
  • 비교식과 분산식 정렬로 나눌 수 있다.
  • 삽입, 선택, 머지, 힙, 퀵 정렬 등 다양한 정렬 방식이 존재함

어떤 정렬이 가장 빠를까?
보통 힙이나 합병 정렬이 가장 빠르다고 생각한다. 하지만 각각의 정렬 방식에 유리한 상황과 불리한 상황이 있어 무엇이 더 빠른지 정해져 있지는 않다.
여기에서 특정한 상황에서의 정렬 속도를 시각적으로 비교해 볼 수 있다.

비교식 정렬

  • 다른 요소와 비교를 통해 정렬하는 방식이다.

1. 버블 정렬

  • 서로 인접한 요소를 검사하여 정렬하는 알고리즘이다.
  • O(n^2)
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) { // 배열의 길이만큼
    for (let j = 0; j < arr.length; j++) { // (0, 1) , (1, 2), (2, 3)... 비교하여 정렬
      if (arr[j] > arr[j + 1]) {
        [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
      }
    }
  }
  return arr;
}

console.log(bubbleSort([7, 4, 5, 1, 3])); // [1, 3, 4, 5, 7]

2. 선택 정렬

  • 선택한 요소와 가장 우선순위가 높은 요소를 교환하는 알고리즘
  • O(n^2)
function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let min = i;

    // i 이후 인덱스에서 가장 작은 수의 인덱스를 찾음
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[min] > arr[j]) {
        min = j; 
      }
    }

    if (i !== min) {
      [arr[min], arr[i]] = [arr[i], arr[min]];
    }
  }
  return arr;
}

console.log(selectionSort([7, 4, 5, 1, 3])); // [1, 3, 4, 5, 7]

3. 삽입 정렬

  • 선택한 요소를 삽입할 수 있는 위치를 찾아 삽입하는 방식의 알고리즘
  • O(n^2)
  • 어느 정도 정렬되어있는 배열에 사용하면 퀵 정렬보다도 빠른 성능을 보여줌

    실제로 선택 정렬의 최선 시간 복잡도는 O(n)이다. 정렬되어 있는 배열에서 삽입 정렬을 하면, 삽입 위치를 찾는 비교 연산을 각 한 번씩만 하게 된다.

function insertionSort(arr) {
  	for (let i = 1; i < arr.length; i++) {
    	const currentValue = arr[i]; // 삽입할 값
    	let j = i - 1;
    	// 삽입할 값의 위치를 찾으면서, 삽입 위치가 나올 때까지 값을 뒤로 한 칸씩 밀어줌
    	while (j !== -1 && arr[j] > currentValue) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = currentValue;
  }

  return arr;
}
console.log(isnertionSort([7, 4, 5, 1, 3])); // [1, 3, 4, 5, 7]

기존과 같이 단순한 swap으로 구현되지 않는다는 사실을 깨닫지 못하고 한참 헤맸다.

  1. 삽입할 값을 currentValue로 저장해 놓는다.
  2. 비교할 인덱스를 currentValueindex - 1로 하여 1씩 감소시키며 currentValue의 값과 비교한다.
    2-1. 비교 결과 더 크면 j에 있던 값을 한 칸(j + 1로) 밀어낸다.
    2-2. 이 전 값이 더 작으면 비교를 종료한다.
  3. 삽입 위치에 값을 넣는다.

분산식 정렬

  • 요소를 분산하여 정렬하는 방식이다.

    분할 정복 : 문제를 작은 두개의 문제로 분리하고, 더이상 분리가 불가능 할 때 처리한 후 합치는 전략

1. 합병 정렬

  • 분할 정복 알고리즘을 통한 가장 정직한 알고리즘이다.
  • 정직하게 요소를 이분하여 정렬하기 때문에 최선과 최악이 항상 O(nlogn)이다.

2. 퀵 정렬

  • 피봇을 기준으로 좌측과 우측으로 나누어 정렬한다.
  • O(nlogn) 시간 복잡도를 가진다.
  • 매우 빠르지만 피봇을 잘못 잡을 경우 O(n^2)이 소요된다.

Javascript - sort 메소드

Javascript에서 정렬은 내장된 sort 메소드를 사용하면 된다. 단, 아스키 코드 값을 이용하여 비교하기 때문에 숫자를 정렬할 경우에는 비교 함수를 반드시 넘겨야 한다.

const arr = [7, 4, 5, 1, 3];
arr.sort((a, b) => a - b); // 오름차순 정렬, 배열 원본에 영향을 미침

const arr = [1, 3, 4, 5, 2];
arr.sort((a, b) => a - b);
console.log(arr); // [ 1, 2, 3, 4, 5 ]

정렬 기준을 여러 개로 둘 수도 있다. 객체를 담고 있는 배열의 경우 정렬 기준이 여러 개가 될 수 있다.

// 점수가 높은 사람 순으로 정렬하고, 점수가 같을경우 이름 순으로 정렬해보자.
const grades = [
  { name: "Bob", score: 90 },
  { name: "Hanna", score: 10 },
  { name: "Joy", score: 70 },
  { name: "Alice", score: 90 },
  { name: "Kate", score: 60 },
];

grades.sort((a, b) => {
  if (a.score !== b.score) return b.score - a.score; // 점수로 내림차순 정렬
  return a.name.localeCompare(b.name); // 이름으로 오름차순 정렬
});

console.log(grades);
/*
[
  { name: 'Alice', score: 90 },
  { name: 'Bob', score: 90 },
  { name: 'Joy', score: 70 },
  { name: 'Kate', score: 60 },
  { name: 'Hanna', score: 10 }
]
*/

마치며

역시 들으며 고개를 끄덕이는 것과 내 것으로 만드는 것은 완전히 다른 과정을 거치는 것 같다. 버블 정렬부터 정확히 이해가 안가서 손으로 써가며 이해하고, 코드 작성까지 해보았다.😂 이제 정렬에 대해서 잊을 일이 없기를 바란다... 합병 정렬과 퀵 정렬은 동작까지는 이해했는데, 구현하기에는 아직 머리가 안 돌아가는 것 같아 추후에 해보려고 한다.

출처

프로그래머스 프론트엔드 데브코스 Day 4 [강의] 정렬
profile
데굴데굴 굴러가고 있습니다

0개의 댓글