정렬알고리듬, 실무에서 가장 많이 사용하는 것은?

Together의 이미지
Together의 이미지

여러가지 테스트 해 봤는데 빠르기는 퀵정렬이 진짜 빠르네요.
혹시 이런거 말고 다른 특이한 정렬 알고리듬이 있다면 어떤게 있을까요?

또, 정렬 알고리듬이 아니더라도 가장 기억에 남았든 알고리듬이 있다면 어떤 것이 있으신지요.

개인적으로 힙정렬이 상당히 기발한 알고리듬이라는 생각이 드네요.

- 험한 세계에서 자주국방 없는 경제력은 경비없는 은행이다. -

FrogLamb의 이미지

가장 많이...라고 하면 퀵소트라고 하겠지만...
어디까지나 상황에 따라 적절히 알고리즘을 선택하는게 중요하겠지요.

더 빠른 정렬이라면 기수정렬(radix sort)도 있겠고...

힙정렬 같은경우엔 정렬 방법이 기발한게 아니라 힙이라는 자료구조 자체가 기발한것이라 생각해도 되겠죠

----------------------------------------
Kwonjin Jeong

kkb110의 이미지

Intro Sort라고 퀵소트와 힙소트를 짬뽕시켜놓은게 있습니다.

퀵소트는 어떤 파티션에서는 엄청나게 나쁜성능을 보여주는데

일반 시간복잡도는 퀵소트와 같으면서 최악의 시간복잡도는 힙소트인 알고리즘입니다. 현존하는 정렬알고리즘중에 가장 좋지 않나 싶네요. Scott Douglas Meyers말로는 다음 STL 표준이 제정될때는 퀵소트와 힙소트 두 정렬대신 이걸로 통합될꺼라는데...

일단 자료 첨부합니다.

댓글 첨부 파일: 
첨부파일 크기
파일 194.13 KB
cdpark의 이미지

kkb110 wrote:

일반 시간복잡도는 퀵소트와 같으면서 최악의 시간복잡도는 힙소트인 알고리즘입니다. 현존하는 정렬알고리즘중에 가장 좋지 않나 싶네요. Scott Douglas Meyers말로는 다음 STL 표준이 제정될때는 퀵소트와 힙소트 두 정렬대신 이걸로 통합될꺼라는데...

SGI의 STL에는 이미 intro sort가 구현되어 있습니다. 아마 딩컴웨어(와 Visual Studio)쪽도 intro sort겠죠?

기본은 quick sort입니다. quick sort의 recursion이 2 log n보다 깊어지면 다른 n log n 정렬을 쓰는거죠. heap sort를 쓸 수도 있고, merge sort를 쓸 수도 있고요. (STL 구현에서는 merge sort...)

죠커의 이미지

Intro Sort가 명칭이였군요.

스캇 마이어가 언급한 적이 있는 소팅이 상업적인 솔루션에서 퀵 소트를 대체하고 있다고 들었습니다.