쉘 정렬은 버블 정렬보다 3 배 빠릅니다.

C에서 셸 정렬을 구현했으며 Bubble 정렬보다 약 3 배 빠릅니다. 여기 내 정렬 지속 시간은 초 단위 :쉘 정렬은 버블 정렬보다 3 배 빠릅니다.

For list of 100 integers: 
BubbleSort: 0.000333 
ShakeSort: 0.000282 
QuickSort: 0.000048 
QuickSort_Iter: 0.000063 
InsertionSort: 0.000188 
ShellSort: 0.000150 

For list of 1000 integers: 
BubbleSort: 0.028191 
ShakeSort: 0.019354 
QuickSort: 0.000435 
QuickSort_Iter: 0.000528 
InsertionSort: 0.011917 
ShellSort: 0.003664 

For list of 5000 integers: 
BubbleSort: 0.241116 
ShakeSort: 0.222127 
QuickSort: 0.001306 
QuickSort_Iter: 0.001592 
InsertionSort: 0.151656 
ShellSort: 0.091002 

For list of 10000 integers: 
BubbleSort: 0.959580 
ShakeSort: 0.872648 
QuickSort: 0.002877 
QuickSort_Iter: 0.003379 
InsertionSort: 0.601329 
ShellSort: 0.350866

은 일반 IT 또는 가능성이 내 구현에 문제가?

출처

2016-07-23 LynnXe

는 어레이 기반 벡터의 0-999의 의사 랜덤 정수. 나는 모든 조건 하에서 쉘 정렬을위한 모든 합리적인 성능을 가지고 있는지 궁금 할 것입니다. – Jcl

에 상당히 의존 – LynnXe

"모든"조건과 같은 것은 없습니다. 조건은 실제로 중요합니다 ... 첫 번째와 마지막으로 교체 된 숫자를 제외하고는 완전히 정렬 된 숫자 배열을 가지고 있다고 상상해보십시오.이 경우 셸 정렬은 버블 정렬보다 빠를 가능성이 큽니다 (하나의 스왑을 수행 할 수 있기 때문에 버블 정렬은 모든 숫자를 바꿔야 할 것입니다.) ... 그러나 그것은 단 한가지 예입니다. 버블 정렬이 셸 정렬보다 느리거나 빠르다는 것을 의미하지는 않으며, 특정 데이터 세트에 대해서만 의미합니다. 큰 O 문제에서'n'은 많이, :-) – Jcl

필자는 셸 정렬 및 버블 정렬의 4 가지 변형을 사용한 정렬 벤치마킹 프로그램을 가지고 있습니다. 4 가지 변형 중 3 가지는 유사한 타이밍 속성을 가지고 있습니다. 네 번째는 다른 세 가지보다 극적으로 더 나쁩니다. 그러나 정렬 크기가 1000 일 때 3 개의 쉘 정렬은 100μs 미만이고 느린 것은 600μs 미만이며 버블 정렬은 900μs보다 적게 걸리지 만 크기는 10,000에서 1-2ms와 70ms 사이에서 142ms 사이, 크기가 100,000 일 때 시간은 14-30ms vs 8.6s에서 18s 사이에 다양합니다. 따라서 쉘 종류 중 하나는 버블 정렬 속도의 약 절반이지만 다른 것들은 더 나은 방법입니다. - 조나단 레플러

좋아, 쉘 정렬, 그래서 지금은 예상대로 수행하는 동안 서브 벡터를 정렬 삽입 정렬 로직을 사용하여 구현을 변경 - LynnXe을

그것은 당신의 데이터 세트

출처

2016-08-05 06:32:15 Armali

쉘 정렬은 버블 정렬보다 3 배 빠릅니다.

답변

관련 문제