▲

Go는 다음 릴리즈 부터 pdqsort를 사용할 예정

 (github.com/golang)
14P by xguru 2022-04-22 | favorite | 댓글 1개

"Pattern-defeating QuickSort"

  • 랜덤 퀵소트의 빠른 평균 케이스와 힙 소트의 빠른 최악의 케이스를 합치고, 특정 패턴의 입력에 대해서 리니어 시간을 달성하는 최신 정렬 알고리즘
    → Intro Sort(기본적으로 퀵소트인데, 재귀가 깊어지면 힙 소트를 사용)를 향상시킨 확장
  • 현재 C++ 및 Rust 구현체는 나와 있음