Sorting Algorithms

slaslaya·2019년 8월 1일
Bubble SortInsertion SortMerge sortQuick SortSelection SortSorting Algorithms바닐라코딩
1

Sorting Algorithms

목록 보기
1/1

where sorting algorithms help us?

  • 사람들을 정렬할 때 - Sorting a list of people
  • 중간값을 찾을 때 - Find the median
  • 중복을 제거할 때 - Find duplicates in some date
  • 이진탐색

왜 공부하는가?

  • 정렬에 따른 성능의 차이 - 성능제약에 맞추기 위해서다.
  • 큰 자료나 적은 자료냐 상황에 따라서 달라질 수 있다.

차이를 비교하고 이해해야 한다.

What does "stable" mean?

  • 상대적인 그 위치를 최종결과에서 유지 되는가 ?
    • 같은 값이 있을때 처음의 상대적 위치가 정렬된 순서랑 같이 위치하여 있는가
  • bubble sort, insertion sort, merge sort (selection sort 빼고)

What does "in place" mean?

bubble sort, insertion sort, selection sort (merge sort 빼고)

Bubble Sort

점진적으로 본인의 위치를 찾아간다. 위로 뽀글뽀글 🧼

  1. 리스트가 있다.
  2. 왼쪽에서 오른쪽으로 순회한다.
  3. 이동하면서 왼쪽과 오른쪽을 비교한다.
  4. 왼쪽이 더 크다면 왼쪽과 오른쪽을 바꾼다.
  5. 오른쪽 끝까지 이동했다면 가장 큰 숫자가 제일 먼저 픽스 된다.

반복 순회하면서 왼쪽과 오른쪽을 바꿔간다.

length - 1 만큼 순회한다. 그치만 장담할 수 없다.

Big O

Time ComplexitySpace Complexity
AverageBestWorstWorst
O(n^2)O(n)O(n^2)O(1)

(셀병합도 html도 먹히지 않는다.. 😢)

Average, Worth O(n^2): 왼쪽에서 오른쪽으로 순회 하면서 총 횟수는 n번이다.
n번 순회가 끝나기전에 sorting이 완료 되었다 하여도 한번도 순회를 해야 순회를 끝내야하는지를 파악한다.

장점

  • Memory: "in place" algorithm
    • In place - 리스트가 주어짐, 추가적인 다른 공간에 저장된 후 사용되는게 아니다. 추가적인 장소가 필요없다.
  • stable
  • 쉬운로직이다.
  • 어떤리스트가 정렬이 되어있는지 안되어있는지 알 수 있다.

단점

  • 성능적으로 별로다 - 자료가 많은 경우

javascript 구현

function bubbleSort (arr) {
  for (let i = 0; i < arr.length; i++) {
    let isSwap = false;

    for (let j = 1; j < arr.length; j++) {
      if (arr[j - 1] > arr[j]) {
        [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
        isSwap = true;
      }
    }
    if (!isSwap) return arr;
  }
  return arr;
}

console.log(bubbleSort([2,4,6,1,2,5]));

isSwap으로 Best케이스일때의 O(n)을 구현
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]; es6 Destructuring Assignment 사용

Insertion Sort

  • index 1부터 비교를 시작하며 비교는 index - 1 이하로 위치한 요소(쉽게 말해 왼쪽 요소)와 비교한다.
  • index - 1 이하 위치한 영역에서 자신의 상대적 위치를 찾아나간다.

Big O

Time ComplexitySpace Complexity
AverageBestWorstWorst
O(n^2)O(n)O(n^2)O(1)

장점

  • In place
  • stable

단점

  • 성능적으로 별로다.
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j;

    for (j = i - 1; j >= 0 && arr[j] > key; j--) {
      arr[j+1] = arr[j];
    }
    arr[j+1] = key;
  }
  return arr;
}

console.log(insertionSort([1,5,6,2,6,7]));

Selection Sort

왼쪽 -> 오른쪽까지 순회한다.
가장 작은 수를 찾는 순회이다.

자리를 기준으로 정렬한다.

  • 0번째 인덱스에 있어야 하는 수를 찾는다. (가장 작은 수)
  • 1번째 인덱스를 찾는다. (두번째로 작은 수)
  • 2번째 인덱스를 찾는다. (세번째로 작은 수)

Big O

Time ComplexitySpace Complexity
AverageBestWorstWorst
O(n^2)O(n^2)O(n^2)O(1)
  • 시간 복잡도는 전부 Best와 Worst가 차이가 없다. 오직 절대적 위치를 찾기 위해 전체를 n번 돌기 때문이다.

Stable 하지 않는다.

  • 상단 그림을 본다면 처음 파란색 4와 초록색 4가 있다. 마지막 최종에선 두 자리가 바뀌었다. 절대적 위치만 찾아가기 때문이다.

장점

  • In place이다.

단점

  • 퍼포먼스가 최악이다.

javascript로 구현하기

function selectionSort (arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let min = i;
    for (let j = i + 1; j < arr.length; j++) {
      if(arr[min] > arr[j]) min = j;
    }
    if(min !== i) [arr[min], arr[i]] = [arr[i], arr[min]];
  }
  return arr;
}

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

Quick Sort


1. 범위를 잡는다.
2. 기준이 되는 원소(pivot)를 선택한다.
첫번째 원소
 중간 원소
랜덤 원소
 마지막 원소
3. 범위 내에서 pivot보다 작은 수와 큰 수를 정렬한다.
4. pivot은 중간으로 위치한다.
5. 모두 정렬될 때까지 반복된다.

Big O

Time ComplexitySpace Complexity
AverageBestWorstWorst
O(nlog(n))O(nlog(n))O(n^2)O(log(n))

Best: 항상 중간값을 계속 pivot으로 선택할 때가 best case다.
Worst: 최악의 경우는 항상 최대, 최소의 pivot을 선택 할 때이다.

stable하고 in place다

javascript로 구현하기 (범위의 첫번째 원소가 pivot이다)

function quickSort(arr, pivotIndex, endIndex) {
  let storeIndex = pivotIndex + 1;

  for(let i = storeIndex; i <= endIndex; i++) {
    if(arr[i] < arr[pivotIndex]) {
      if(storeIndex !== i) {
        [arr[storeIndex], arr[i]] = [arr[i], arr[storeIndex]];
      }
      storeIndex += 1;
    }
  }

  if(storeIndex -1 !== pivotIndex) {
    [arr[pivotIndex], arr[storeIndex - 1]] = [arr[storeIndex - 1], arr[pivotIndex]];
  }

  if(pivotIndex < storeIndex - 2) quickSort(arr, pivotIndex, storeIndex - 2);
  if(storeIndex < endIndex) quickSort(arr, storeIndex, endIndex);

  return arr;
}

console.log(quickSort([5,4,8,6,1,8], 0, 5));

Merge Sort


이미지 출처

합쳐나가는 sorting 이다.

  • 개별적으로 자른다.
  • 두개를 비교한다. 비교 후 정렬한 후 통합한다.
  • 두개 + 두개를 합칠때 맨앞에 자리를 두개 비교 뒷자리 두개를 비교한다.
  • 네개 + 네개를 합칠때는 자리수로 또 비교한다.

Big O

Time ComplexitySpace Complexity
AverageBestWorstWorst
O(nlog(n))O(nlog(n))O(nlog(n))O(n)

Average, Best, Worst: 최대한 세세하게 나눈후 합쳐가는 뒤집어진 트리와 유사하다. 그래서 logn인데 여기다 원소의 갯수를 총 곱해서 n(logn)이다.

장점

  • 평균적으로 보장이 되어있다.
  • 자료가 많을 때 사용하기 좋다.
  • stable 하다.

단점

  • 한개가 하나의 배열이다. - in place로 할 수 없다. 공간적인 필요도가 o(n)
  • 자료가 적을 때는 별로다.

Divide and Conquer

  • Divide: 최대한 세세하게 작은 문제로 쪼갠다.
  • Conquer: 재귀적으로 정렬한다.
  • Combine
  • Quicksort
  • BST가 해당된다.

Divide and Conquer Algorithm Link

추가 알아볼 사항

  • Dynamic Programming
profile
slaslaya
안녕하새요

0개의 댓글