정렬 알고리즘이 다양한 이유

위와 같이 알려진 정렬 알고리즘은 무수히 많다. 이 정렬 알고리즘을 모두 알면 좋겠지만, 나눠진 이유와 이에 맞춰 사용해야할 정렬 알고리즘을 적절히 판단해야만 한다

 

1) 정렬이 수행되는 시간복잡도가 다르다. 시간복잡도가 매번 평균 시간복잡도로 나오진 않지만 대체적으로 빠른 것과 느린 것이 있다. 데이터 양이 작다면 시간복잡도를 크게 고려할 필요가 없기 때문에, 코드가 짧은 bubble sort, selection sort, insertion sort가 있다. 반대로 데이터 양이 크다면 시간복잡도를 고려해야하기 때문에 코드가 길지만 merge sort, quick sort를 구현해야만 한다

 

2) 속도가 아닌 공간복잡도를 고려해야할 수 있다. merge sort는 NlogN의 빠른 알고리즘이지만 분할 정렬된 배열을 매번 저장해야므로 메모리를 많이 차지하게 된다

 

3) stable, unstable을 고려해야 하는 상황이 있을 수 있다. stable을 고려해야한다면, 메모리를 많이 잡아먹음에도 빠른 알고리즘인 merge sort를 고려해야 한다