<Udemy 퀵 정렬> TIL-62

  오늘은 퀵 정렬에 대해서 공부했다. 앞서 배운 합병 정렬에 비해서 코드를 이해하는게 쉽지 않았다. 개념 자체도 조금은 생소하게 느껴졌다. 피벗을 정해서 피벗의 왼편에는 작은 숫자들로 또 오른편에는 큰 숫자들로 정렬하여 피벗 숫자만은 정렬이 되고 피벗 숫자를 중심으로 왼편과 오른편에 새로운 피벗을 정하고 또 큰 수는 오른편에 작은 수는 왼편에 정렬하는 방식으로 계속해서 재귀함수를 사용하여 반복하서 정렬된 배열을 반환하는게 퀵 정렬이었다. 가장 헷갈리게 만들었던 부분은 당연히 재귀를 머릿속으로 그리면서 따라가는게 어려웠다. 아니 따라가지 못했다. 그래서 종이에 하나 하나 대입해가면서 코드를 읽어 나갔다. 또한 스스로 느끼기에 가독성이 그렇게 좋아보이지도 않았다.

 

  효율적인 측면을 따졌을때 정렬 알고리즘 애니메이션 사이트를 통해 합병 정렬과 비교했을때도 속도는 비슷했다. 그래서 의아했다 합병 정렬의 경우에도 배열을 합치는 함수를 만들고 합병 정렬 함수를 만들어 두 개를 활용해야 했고, 퀵 정렬의 경우에도 마찬가지로 피봇이 정렬된 위치의 인덱스 번호를 반환하는 함수를 만들어서 반환해야 했다. 작성해야 할 코드 양도 비슷하고, 처리 속도도 비슷하다면 굳이 퀵 정렬이 존재해야 할 이유에 대해서 의구심이 들었다. 강의를 들을때 모든 알고리즘은 주어진 상황에 따라 장/단점이 다 다르다고 계속해서 말해주고 있다. 그런데 퀵 정렬 만큼은 어떤 상황에 장점이 있는지 의문이 든다. 심지어 피벗을 잘못 결정하게 되는경우(예를 들어 정렬된 배열의 가장 앞 요소를 피벗으로 지정하는 경우)에는 O(n^2) 시간 복잡도를 가지는 위험까지 있다. 그렇다고 가장 좋은 상황에 O(n) 시간 복잡도를 갖는것도 아니다. O(nlogn) 시간 복잡도를 갖게 된다. 반면 합병 정렬의 경우에는 가장 좋은 상황이든 나쁜 상황이든 모두 O(nlogn)시간 복잡도를 갖는다. 그렇다면 결국 합병 정렬이 퀵 정렬보다 더 나은 정렬방식이라고 말할 수 있는것 아닌가 하는 생각이 들었다. 물론 버블 정렬, 선택 정렬, 삽입 정렬(대부분 정렬이 된 배열을 정렬하는 경우 제외)보다는 한 단계 더 나아가 개선된 알고리즘이겠지만 그렇다고 합병 정렬에 비해 특별하게 더 나은 경우가 있는지는 아직 모르겠다. 

 

  물론 아직 알고리즘에 대한 공부를 얼마 하지 않았고 단순히 강의를 듣고 배운 내용들을 토대로 비교하기 때문에 정확한 비교를 한다고 장담할 수 없다. 그래서 이 부분은 더 공부가 이뤄지면 다시 한번 생각해 보아야 겠다. 

 

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

11 퀵 정렬