TIL(20.04.04) 정렬

2일정도 포스팅을 안했는데 포스팅을 하려하니 굉장히 오랜만에 하는거 같습니다. 앞으로 하루도 빠지지 않고 해야겠습니다 ㅎㅎ

오늘은 자료구조 시간에 집고 넘어가지 못했던 정렬에 대해 포스팅 해보려 합니다.

1. What is Sort ??

정렬이란 항목들을 체계적으로 정리하는 과정입니다. 정렬을 알고리즘에 적용을 하면 n개의 숫자가 입력으로 주어졌을 경우에 이를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘입니다.

정렬의 알고리즘에는 다양하게 있지만 가장 많이 사용되고 인기가 있는 정렬 알고리즘에 대해 알아보고 코드까지 작성해 보겠습니다.

2. Sort algorithm

• Bubble sort

• select sort

• insertion sort

• merge sort

• quick sort

• heap sort

인기 있는 정렬은 위의 5가지의 sort 알고리즘입니다. 하나 하나 어떤식으로 정렬을 하고 어떻게 구현이 되는지 알아보겠습니다.

3. Bubble sort (거품 정렬)

버블정렬은 거품이 생길때를 형상화 해서 지었습니다. 거품이 일어날때 양옆으로 거품이 생기면서 커지게 됩니다. 이를 연상하면 버블정렬이 어떤식으로 정렬이 될지 약간의 감이 잡힐거 같습니다 😄

위의 그림이 버블정렬의 예시 그림입니다. 그림을 보면 바로 전 인덱스와 다음 인덱스의 크기 비교를 해 전 인덱스가 다음 인덱스 보다 더 크다면 전 인덱스가 다음인덱스와 swap이 되는 것을 볼 수 있습니다. 이 과정을 배열의 길이 만큼 반복을 해주어 모든 방이 정렬이 되게 끔 해줍니다.

이러한 과정을 보았을때 시간 복잡도를 예상 할 수 있을거 같습니다.

Time Complexity

Average: O(N^2)
Worst: O(N^2)

Psedo code

• 첫번째 인덱스와 그 다음 인덱스를 정해 준다.

• 첫번째 인덱스와 다음 인덱스의 크기를 비교한다.

• 만약 첫번째 인덱스의 값이 그 다음 인덱스의 값 보다 크다면 두 개의 인덱스를 바꾸어준다. (swap)

• 이 과정을 배열의 길이만큼 반복 해 준다.

• 마지막으로 정렬이 끝난 배열을 반환한다.

Bubble sort implementation

위의 의사코드를 통해 알고리즘을 작성 해 보겠습니다.

const bubbleSort = function(array) {
  let length = array.length; // 배열의 길이 

  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length - 1; j++) {
      if (array[j] > array[j + 1]) { // 이전 인덱스와 다음 인덱스 값을 비교 
        swap(array, j, j + 1);  // 이전 인덱스의 값이 크다면 두개를 swap
      }
    }
  }
  return array; // 정렬이 끝난 배열을 반환 
};

// 바꿔주는 함수

function swap(array, index1, index2) { // 배열, 이전 인덱스 , 다음 인덱스 
  let temp = array[index2]; // 인덱스의 값을 임시로 저장 해준다.
  array[index2] = array[index1];
  array[index1] = temp;
}

4. Selection sort (선택 정렬)

선택 정렬은 위의 그림으로 설명 할 수 있을거 같습니다. 선택 정렬은 배열 내부에서 가장 작은 값을 찾아서 배열을 가장 앞에 놓아주는 정렬이 끝난 맨 앞의 값을 고정하고 그 다음 인덱스부터 다시 반복해서 정렬을 하는 알고리즘입니다.

Time Complexity

Average: O(N^2)
Worst: O(N^2)

Psedo code

• 최소값을 넣어줄 변수를 배열의 인덱스로 해준다.

• 최소값을 배열의 첫번째 요소의 값으로 정하고 배열 내부에서 비교해 나가면서 작은 값을 찾아준다.

• 배열 내부에서 최소 값을 찾았다면 배열의 맨 앞 인덱스에 넣어준다.

• 맨앞에 있는 배열의 값은 정렬이 끝났기 때문에 최소값의 변수 인덱스를 하나 늘려 준 후 위의 과정을 반복해 준다.

Selection sort implementation

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

function swap(array,index1, index2) {
 let temp = array[index1]
 array[index1] = array[index2];
 array[index2] = temp
}

5. Insertion sort(삽입 정렬)

새로운 숫자가 삽입 되면 정렬된 배열 안에서 자기의 자리를 찾아가며 정렬 하는 것

Time Complexity

Average: O(N^2)
Worst: O(N^2)

Psedo code

• 삽입 정렬은 첫번째 요소가 이미 정렬이 되어 있다 가정을 하고 정렬을 시작 합니다.

• 그리고 나서 두번째 아이템을 첫번째 아이템과 비교합니다.

• 두번째 아이템이 그대로 자리에 있을 지 아니면 첫번째 자리로 삽입을 할지 확인 해 줍니다.

• 그 후 세번째 아이템을 첫번째 아이템, 두번째 아이템과 비교를 합니다.

• 계속해서 반복 해 줍니다.

Selection sort implementation

function insertionSort(array) {
  let length = array.length;
  let j;
  let temp;
  for (let i = 1; i < length; i++) {
    j = i;
    temp = array[i];
    while (j > 0 && array[j - 1] > temp) {
      array[j] = array[j - 1];
      j--;
    }
    array[j] = temp;
  }
  return array;
}