대학원이든 회사이든 데이터 구조 문제는 어디에서도 빠지지 않는 질문인 것 같다. 데이터 구조에서 Sorting관련 알고리즘도 많이 묻는 질문 중 하나인데, 지난 번에 퀵소트(Quick Sort)에 대해 알아본 적 있다. https://aistudy9314.tistory.com/2?category=977992 [데이터 구조] 퀵소트(Quick Sort) 오늘은 정렬 알고리즘 중에서 퀵소트(Quick Sort)에 대해 공부해보았다. 실제 많은 곳에서 사용된다는 퀵소트는 무엇이고, 어떠한 방식으로 구현이 되는지를 알아보았고, 시간복잡도와 최악의 경 aistudy9314.tistory.com 이번 게시글에서는 퀵소트와 비슷하게 "분할 정복 방식"을 이용하는 합병 정렬(Merge Sort)에 대해 알아보겠다. 1..

오늘은 정렬 알고리즘 중에서 퀵소트(Quick Sort)에 대해 공부해보았다. 실제 많은 곳에서 사용된다는 퀵소트는 무엇이고, 어떠한 방식으로 구현이 되는지를 알아보았고, 시간복잡도와 최악의 경우, 또 그 해결법을 살펴보았다. 퀵소트(Quick Sort)란 무엇일까? - 출처 : https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC 퀵소트는 분할 정복 방식을 이용한 정렬 알고리즘으로, 하나의 큰 문제를 여러 개의 작은 문제로 쪼개어 풀어나가는 것이 특징이다. 퀵소트는 아이러니하게도 시간복잡도가 최악의 경우 O(n^2)라는 매우 느린 값을 가지면서도 빠른 정렬 알고리즘이라고 알려져 있다. 또한, 특이하게 BIG-O Notation을 최악의 경우가 아닌 평..