<Udemy 삽입 정렬/합병 정렬> TIL-61

  오늘은 정렬 알고리즘을 이어서 공부했다. 삽입 정렬과 한 단계 효율이 올라가는 합병 정렬에 대해서 공부했다. 우선 삽입 정렬의 경우에는 버블 정렬과 선택 정렬과 마찬가지로 효율이 좋은 쪽에 속하는 정렬 알고리즘은 아니었다. 일반적으로 O(n^2)시간 복잡도를 갖는 정렬 방식이다. 하지만 정렬 알고리즘 에니메이션을 통해 보았을때 거의 정렬이 되어 있는 배열을 정렬하는 것은 다른 알고리즘들에 비해 굉장히 빠르다는 것을 알 수 있었다. 즉 삽입 정렬의 경우에는 거의 정렬이 되어 있는 배열을 정렬해야 하는 상황에서 사용하기에 아주 알맞은 정렬 알고리즘이라는 것이다. 

https://www.toptal.com/developers/sorting-algorithms

Sorting Algorithms Animations

  삽입 정렬은 배열의 첫 번째 요소는 정렬이 되어 있는 것으로 간주하고, 그 외의 요소들을 하나씩 반복하여 정렬된 요소들과 비교해서 알맞은 위치에 삽입하는 정렬이다. 이 또한 굉장히 직관적이었다.

 

  그 다음 이어서 배운 합병 정렬의 경우에는 배열의 요소들을 다 분할해서 0개 또는 1개의 요소를 가지는 배열로 분할하고, 0개 또는 1개의 요소를 가지는 배열은 정렬이 되어있는 배열임을 이용하여 정렬이 된 배열을 합병하는 함수를 구현하고 이를 이용해서 다시 합병을 통해 정렬하는 방식이었다. 우선 정렬 방식이 너무 독특해서 개념적인 부분은 빠르게 이해할 수 있었다. 또한 한 단계 더 업그레이드 된 배열 답게 항상 O(nlogn)시간 복잡도를 갖는 정렬 알고리즘이다. O(n^2)과 O(nlogn) 시간 복잡도의 차이는 시각적으로 확인이 가능했다.( 10만 개의 배열을 랜덤 숫자를 가지고 각각의 정렬 알고리즘을 이용해서 정렬을 하면 시간 차이가 명확했다.) 하지만 공부하는 입장에서 단점이 있다면 코드를 작성하기가 앞서 배운 버블, 선택, 삽입 정렬들에 비해 까다롭다는 것이다. 정렬된 배열을 합병하는 함수를 따로 구현해야 했고 이를 이용해서 재귀적으로 코드를 구현해야 하기 때문이다. 재귀에 대한 개념을 어느 정도 알고 이해했음에도 재귀를 머릿속으로 그리면서 따라가기가 매우 힘들어 종이와 펜으로 하나 하나 적어가면서 비교를 했던 것 같다. 하지만 중요한 점은 이 어려움을 극복하고 합병 정렬을 완벽하게 구현하고 이를 응용하면서 활용할 수 있다면, 굉장히 효율적인 정렬방식을 하나 구현할 수 있게 된다는 큰 장점이 있는것 같다. 그럼에도 불구하고 삽입정렬이 합병 정렬보다 좋은 경우는!! 정렬이 거의 이뤄진 배열은 합병 정렬보다 월등히 빠르다는 점이고 이 점은 꼭 따로 기억해 둘 필요가 있을 것 같다.

 

2022.08.07 - [언어 공부 및 정리/자바스크립트 알고리즘 & 자료구조[Udemy강의]] - 09 삽입 정렬

09 삽입 정렬

2022.08.07 - [언어 공부 및 정리/자바스크립트 알고리즘 & 자료구조[Udemy강의]] - 10 합병 정렬

10 합병 정렬