Skip to content

7. Sorting Algorithms.md

Latest commit

 

History

History
250 lines (184 loc) · 6.27 KB

7. Sorting Algorithms.md

File metadata and controls

250 lines (184 loc) · 6.27 KB

Sorting Algorithms

What is sorting?

컬랙션(배열)안에서 아이템들이 어떠한 순서로 정렬될 수 있게 재 정렬 하는 것을 Sorting 이라고 한다.

Exmaples

  • 숫자를 작은수부터 큰 순서대로 정렬
  • 알파벳 순서로 이름을 정렬
  • 영화를 발매 연도 순으로 정렬
  • 영화를 수입 순으로 정렬

Why do we need to learn this?

  • Sorting 은 정말 자주 나오는 작업이다. 따라서 어떤 원리인지 이해하는 것이 좋다.
  • 다양한 Sorting 알고리즘이 있다. 따라서 언제 어떤 알고리즘을 사용하는게 좋을지 알아야 한다.

Objectives

  • bubble sort
  • selection sort
  • insertion sort
  • 이 간단한 Sorting 알고리즘이 중요한 이유

자바스크립트 내장 sort 메소드

  • sort()

    ['Steele','Colt', 'Data Structures', 'Algorithms'].sort();
// ['Algorithms','Colt' ,'Data Structures','Steele']
    [6, 4, 15, 10].sort(); 
// [10, 15, 4, 6] string 에서 앞의 글자를 유니코드 순서로 정렬하기 때문에..

JavaScript 에게 어떤 형태로 정렬해야하는지 알려줘야 한다.

  • sort 메소드는 옵션으로 비교하는 함수를 받는다.
  • 이 함수를 통해 어떤 순서로 정렬할 것인지 알려줄 수 있다.
  • a 와 b를 비교 한다고 하면 함수가 어떤 값을 return 하는지에 따라서 정렬 순서를 결정할 수 있다.
    • if return 값이 음수이면 a-b 순서로 와야한다.
    • if return 값이 +이면 b-a (알파벳 역순) 으로 와야한다.
    • if return값이 0 이면
Example
const numberCompare1 = (num1, num2) => {
	return num1 - num2
}
[6, 4, 15, 10].sort(numberCompare1);
// [4, 6, 10, 15]

const numberCompare2 = (num1, num2) => {
	return num1 - num2
}
[6, 4, 15, 10].sort(numberCompare2);
// [15, 10, 6, 4]

BubbleSort

가장 큰 값이 제일 위로 올라가는 알고리즘

swap 함수

많은 sorting 알고리즘은 swapping 알고리즘을 가지고 있다.

// ES5
function swap(arr, idx1, idx2) {
	var temp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = temp;
}

// ES2015
const swap = (arr, idx1, idx2) => {
	[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}

의사코드

  1. 끝에서 시작을 향해서 보는 Index i 를 설정하고 Loop를 만든다
  2. 그안에 Loop를 하나 더 만들고 시작부터 i-1까지 반복하는 index j를 만든다.
  3. if arr[j] > arr[j+1] 이면 두 요소를 swap!
  4. return 정렬된 배열

구현

  • Naive Solution

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

  • Solution

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

  • Solution 최적화 거의 정렬된 배열이 있더라도 기존 Solution 은 불필요한 작업을 반복한다. 불필요한 반복을 하지 않기 위해 swap을 더 이상 하지 않으면 정렬이 완료된 배열이라고 하고 알고리즘을 종료한다.

    const bubbleSort = arr => {
  let noSwaps;
  for (let i = arr.length; i > 0; i--) {
    noSwaps = true;
    for (let j = 0; j < i - 1; j++) {
      console.log(arr, arr[j], arr[j + 1]);
      if (arr[j] > arr[j + 1]) {
        //swap!
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        noSwaps = false;
      }
    }
    if (noSwaps) break;
  }
  return arr;
};

Bubble Sort BIG O

  • O(n^2)

Selection Sort

버블솔트와 비슷하지만 Selection Sort는 최소값을 찾아서 제알 앞에 둔다.

의사코드

  1. 제일 처음 자리에 최소값을 넣는다.
  2. 다음 요소로 넘어가서 또 다시 최소값을 찾고 위치시킨다.
  3. if 더 작은 숫자를 찾으면 minimum 에 그 값을 할당시키고 배열 끝까지 반복한다.
  4. if minimum이 시작한 값이 아니라면 두 값을 교환한다.

구현

const selectionSort = arr => {
  for (let i = 0; i < arr.length; i++) {
    let lowest = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[lowest]) {
        lowest = j;
      }
    }
    // 자기 자리 잘 찾아 있을 때 굳이 swap 안함
    if (i !== lowest) {
      [arr[i], arr[lowest]] = [arr[lowest], arr[i]];
    }
  }
  return arr;
};

Selection Sort BIG O

  • BIG O : O(n^2)
  • Bubble Sort 와 비교하면 swap을 적게하기 때문에 메모리를 조금 더 적게 사용한다.

Insertion Sort

왼쪽부터 오른쪽으로 가면서 하나하나씩 정렬한다.

  • ex)
    1. [5, 3, 4, 1, 2]
    2. [3, 5, 4, 1, 2]
    3. [3, 4, 5, 1, 2]
    4. [1, 3, 4, 5, 2]
    5. [1, 2, 3, 4, 5]

의사코드

  1. 배열에서 두번째 인자를 선택한다.
  2. If 첫번째 두번째 요소를 swap 해야하면 한다.
  3. 계속 오른쪽으로 가면서 각 요소를 정렬된 왼쪽으로 옮긴다.
  4. 모든 배열이 정렬될 때 까지 반복한다.

구현

const insertionSort = arr => {
  let j;
  for (let i = 1; i < arr.length; i++) {
    let currentVal = arr[i];
    for (j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
      arr[j + 1] = arr[j];
      console.log(arr);
    }
    arr[j + 1] = currentVal;
  }

  return arr;
};

Insert sort BIG O

  • BIG O : O(n^2)
  • 거의 정렬된 배열에는 다른 배열보다 빠르게 정렬을 실행할 수 있다.

Big O of Sorting Algorithms

Algorithm Best Case Average Worst Space Complexity
Bubble Sort O(n) O(n^2) O(n^2) O(1)
Insertion Sort O(n) O(n^2) O(n^2) O(1)
Selection Sort O(n^2) O(n^2) O(n^2) O(1)