정렬 알고리즘은 왜 이렇게 다양할까
- 알고리즘을 공부하면서 가장 궁금했던 점 중 하나는 '왜 정렬 알고리즘에 필요 이상으로 많은 무게가 실려있는가'였다. 어차피 Python의 경우에는
sort메서드나 sorted 함수를 이용하지 굳이 정렬을 직접 구현하여 쓰게 될 일은 거의 없을 것 같았고, 실제로도 그래왔기 때문이다.
- 그래서 조금 검색하며 생각해본 결과 어느 정도는 그 이유를 이해할 수 있었다. 간단하게 요약하자면 문제 해결에 있어서 필요한 여러가지 사고 방식을 익힐 수 있었고, 상대적으로 열위에 있는 방법이라고 하더라도 상황에 따라 좋을 수 있으며, 개발에 있어 고려해야할 여러 사항을 알 수 있다.
문제해결에 필요한 다양한 사고
- 버블소트와 같은 방식에서는 완전탐색 방식을 살펴볼 수 있고, 병합정렬에서는 문제해결에 있어 중요한 사고 방식 중 하나인 분할정복을 학습할 수 있었다. 또한 힙정렬과 같이 여러 자료구조가 활용되기도 한다.
- 이렇게 종류가 다양한만큼 다양한 수단과 사고가 녹아있는 곳이 정렬 알고리즘이 아닐까 생각한다.
상황에 따라 적절한 알고리즘이 다르다
- 일반적으로 학습하는 퀵정렬, 병합정렬, 버블정렬, 삽입정렬 등등 다양한 정렬방식에서 병합정렬은 최선, 평균, 최악의 시간복잡도가 모두
O(N logN)으로 가장 괜찮은 정렬 방식으로 여겨진다.
- 반대로 버블정렬의 경우 이런 정렬을 누가 쓸까 싶을 정도로 단순하지만 비효율적인 정렬방식으로 생각된다. 하지만 버블정렬은 최선의 경우 시간복잡도가
O(N)이 된다(보통 정렬이 되어있는 경우에 그렇다). 이런 사실을 놓고본다면 일반적으로 정렬 알고리즘을 학습할 때 배우는 알고리즘들 중 가장 좋다고 여겨지는 병합정렬보다 어떤 상황에서는 최악이라고 여겨지는 버블정렬이 나은 경우도 있다는 것이다.
- 따라서 주어진 상황을 잘 고려해서 상황에 맞는 알고리즘을 잘 가져다가 사용하는 역량이 중요하다고 할 수 있겠다.
여러 고려사항의 존재
- 윗 문단과 어느정도 통하는 얘기지만 시간복잡도가 고려사항의 전부는 아니라는 것이다. 때로는 정렬 수행시간보다 메모리를 적게 쓰는 것이 중요한 상황이 있을 수도 있고, 주어지는 데이터의 길이가 길지 않아서 시간보다는 코드를 간결하게 작성하는 것이 중요한 경우도 있을 수 있겠다(실무에서 그런 일이 있을지는 잘 모르겠다).
- 이렇듯 일반적으로 알고리즘을 배울 때 시간복잡도를 굉장히 중시하지만 하나의 각도에서만 보지말고 다양한 각도에서 보는 것 또한 중요하다는 생각을 할 수 있었다.
