Timsort와 Quicksort의 비교

Timsort와 Quicksort의 비교

---

timsort (wikipedia에 따르면)가 훨씬 더 잘 수행되는 것처럼 보일 때 quicksort가 가장 빠른 전체 정렬 알고리즘에 대해 주로 듣는 이유는 무엇입니까? 구글은 어떤 종류의 비교도하지 않는 것 같았다.

---

TimSort는 고도로 최적화 된 mergesort이며, 이전 mergesort보다 안정적이고 빠릅니다.

Quicksort와 비교할 때 두 가지 장점이 있습니다.

1. 거의 정렬 된 데이터 시퀀스 (역 정렬 된 데이터 포함)의 경우 믿을 수 없을 정도로 빠릅니다.
2. 최악의 경우는 여전히 O (N * LOG (N))입니다.

솔직히 # 1이 장점이라고 생각하지 않지만 인상적 이었어요.

QuickSort의 장점은 다음과 같습니다.

1. QuickSort는 매우 간단하고 고도로 조정 된 구현으로도 20 줄 내에 pseduo 코드를 작성할 수 있습니다.
2. 대부분의 경우 QuickSort가 가장 빠릅니다.
3. 메모리 사용량은 LOG (N)입니다.

현재 Java 7 SDK는 timsort와 새로운 quicksort 변형 인 Dual Pivot QuickSort를 구현합니다.

안정적인 정렬이 필요하면 timsort를 시도하고 그렇지 않으면 quicksort로 시작하십시오.

---

다소간, Timsort 가 하이브리드 정렬 알고리즘 이라는 사실과 관련 이 있습니다. 즉, 사용하는 두 가지 기본 정렬 (Mergesort 및 Insertion 정렬)이 여러 종류의 데이터에 대해 Quicksort 보다 나쁘지만 Timsort는 그렇게하는 것이 유리할 때만 사용합니다.

Patrick87이 말했듯 이 약간 더 깊은 수준에서 quicksort는 최악의 경우 O (n ² ) 알고리즘입니다. 좋은 피벗을 선택하는 것은 어렵지 않지만 O (n log n) 퀵 정렬을 보장하려면 일반적으로 평균적으로 정렬 속도가 느립니다.

Timsort에 대한 자세한 내용은 이 답변 및 링크 된 블로그 게시물을 참조하십시오 . 기본적으로 대부분의 데이터가 이미 부분적으로 정렬되어 있다고 가정하고 mergesort를 사용하여 효율적인 병합을 허용하는 정렬 된 데이터의 "실행"을 구성합니다.

---

일반적으로 빠른 정렬은 기본 배열에 가장 적합한 알고리즘입니다. 이는 메모리 지역 성과 캐시 때문입니다.

JDK7은 객체 배열에 TimSort를 사용합니다. 객체 배열은 객체 참조 만 보유합니다. 개체 자체는 힙에 저장됩니다. 객체를 비교하려면 힙에서 객체를 읽어야합니다. 이것은 한 객체에 대해 힙의 한 부분에서 읽은 다음 힙의 다른 부분에서 무작위로 객체를 읽는 것과 같습니다. 많은 캐시 미스가있을 것입니다. 이런 이유로 메모리 지역 성은 더 이상 중요하지 않습니다. 이것이 JDK가 원시 배열 인 경우 대신 객체 배열에 TimSort 만 사용하는 이유 일 수 있습니다.

이것은 내 추측 일뿐입니다.

---

다음은 내 컴퓨터의 벤치 마크 수치입니다 (i7-6700 CPU, 3.4GHz, Ubuntu 16.04, gcc 5.4.0, 매개 변수 : SIZE = 100000 및 RUNS = 3) :

$ ./demo 
Running tests
stdlib qsort time:                 12246.33 us per iteration
##quick sort time:                  5822.00 us per iteration
merge sort time:                    8244.33 us per iteration
...    
##tim sort time:                    7695.33 us per iteration
in-place merge sort time:           6788.00 us per iteration    
sqrt sort time:                     7289.33 us per iteration    
...
grail sort dyn buffer sort time:    7856.67 us per iteration

벤치 마크는 그가 C에서 여러 정렬 알고리즘을 구현 한 Swenson의 정렬 프로젝트에서 비롯된 것 입니다. 아마도 그의 구현은 대표성이 될만큼 훌륭하지만 조사하지는 않았습니다.

그래서 당신은 정말로 말할 수 없습니다. 벤치 마크 수치는 최대 2 년 동안 만 관련성이 유지되며이를 반복해야합니다. 아마도 timsort는 질문을 받았을 때 2011 년에 qsort waaay를 이겼지 만 시대가 바뀌 었습니다. 또는 qsort는 항상 가장 빠르지 만 timsort는 무작위가 아닌 데이터에서 이겼습니다. 아니면 Swenson의 코드가 그렇게 좋지 않아서 더 나은 프로그래머가 팀 소트에게 유리하게 변화 할 것입니다. 또는 CFLAGS코드를 컴파일 할 때 내가 짜증나고 올바른 것을 사용하지 않았을 수도 있습니다 . 아니면 ... 당신이 요점을 이해합니다.

---

Tim Sort는 순서 보존 정렬이 필요하거나 기본 배열이 아닌 복잡한 배열 (힙 기반 객체 비교)을 정렬하는 경우에 유용합니다. 다른 사람들이 언급했듯이 quicksort는 원시 배열에 대한 데이터 및 프로세서 캐싱의 위치에서 상당한 이점을 얻습니다.

퀵 정렬의 최악의 경우가 O (n ^ 2)라는 사실이 제기되었습니다. 다행히도 퀵 정렬을 사용하면 최악의 경우 O (n log n) 시간을 달성 할 수 있습니다. 퀵 정렬 최악의 경우는 피벗이 이미 정렬 된 배열의 첫 번째 또는 마지막 요소 인 경우와 같이 피벗 지점이 가장 작거나 큰 값일 때 발생합니다.

피벗을 중앙값으로 설정하여 O (n log n) 최악의 경우 빠른 정렬을 달성 할 수 있습니다. 중앙값을 찾는 것은 선형 시간 O (n)에서 수행 될 수 있기 때문입니다. O (n) + O (n log n) = O (n log n)이므로 최악의 경우 시간 복잡도가됩니다.

그러나 실제로 대부분의 구현에서는 임의의 피벗으로 충분하므로 중앙값을 검색하지 마십시오.

참조 URL : https://stackoverflow.com/questions/7770230/comparison-between-timsort-and-quicksort