Skip to main content

정렬 알고리즘

· 6 min read

아래의 알고리즘은 잘 이해가 가지 않는다..ㅠㅠ

  • merge sort

그리고 시간복잡도?? 성능에 좋지 않다는 의미로 이해가 되는데..

너무 오랫만에 이론적인 부분을 이해하려니 어렵다..ㅠㅠ

다시 보자 또 보자…!! 이해할 때까지…ㅠㅡㅠ

버블 정렬 (Bubble Sort)​

  • 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

선택 정렬(Selection Sort)​

  • 제자리 정렬 알고리즘 중의 하나이다.
  • 주어진 배열에서 최솟값을 찾는다.
  • 최솟값을 맨 앞의 값과 교체한다

해당 과정을 표현하면 아래와 같다.

패스테이블최솟값
0[9,1,6,8,4,3,2,0]0
1[0,1,6,8,4,3,2,9]1
2[0,1,6,8,4,3,2,9]2
3[0,1,2,8,4,3,6,9]3
4[0,1,2,3,4,8,6,9]4
5[0,1,2,3,4,8,6,9]6
6[0,1,2,3,4,6,8,9]8

구현 코드​

Javascript​

function selectionSort(arr) {
  console.log('input: ' + arr);
  for (let i = 0; i < arr.length; i++) {
    let minIdx = i;

    // 최솟값이 위치한 인덱스를 찾는다
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIdx]) minIdx = j;
    }

    // 최솟값과 현재의 인덱스에 위치한 값을 바꿔치기 한다
    let temp = arr[minIdx];
    arr[minIdx] = arr[i];
    arr[i] = temp;
  }
  console.log('output: ' + arr);
}

selectionSort([8, 5, 6, 2, 4]);
selectionSort([3, 7, 2, 5, 1, 4]);

삽입 정렬(Insertion Sort)​

  • 손에 들고 있는 카드의 순서를 정렬하는 방법과 유사하다.
  • 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬 알고리즘
  • 두 번째 요소부터 크기의 비교를 시작한다.

img

특징​

  • 장점
    • 구현이 단순하다
  • 단점
    • 배열이 길수록 효율이 떨어진다

구현 코드​

Javascript​

function insertionSort(arr) {
  console.log('input: ' + arr);
  for (let i = 1; i < arr.length; i++) {
    // 현재 비교할 값을 저장
    let key = arr[i];
    let j = i - 1;

    // key 값의 위치부터 역순으로 조사하며, key 값보다 큰 경우 한 칸 뒤로 이동시킨다
    for (; j >= 0 && key < arr[j]; j--) {
      arr[j + 1] = arr[j];
    }

    arr[j + 1] = key;
  }
  console.log('output: ' + arr);
}

insertionSort([8, 5, 6, 2, 4]);
insertionSort([3, 7, 2, 5, 1, 4]);

합병 or 병합 정렬 (Merge Sort)​

  • 비교 기반 정렬 알고리즘으로 분할 정복 알고리즘 의 하나이다
  • 다음과 같이 동작한다.
    1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
    2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
    3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
    4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

img

퀵 정렬 (Quick Sort)​

  • 분할 정복 알고리즘 의 하나이다

  • 다음과 같이 동작한다.

    1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
    2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
    3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

  • 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

img