• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Resilient Quicksort and Selection

Lecture Notes in Computer Science. 2012. No. 7353. P. 6-17.
Babenko M. A., Puzyrevskiy I. V.

We consider the problem of sorting a sequence of n keys in a RAM-like environment where memory faults are possible. An algorithm is said to be δ-resilient if it can tolerate up to δ memory faults during its execution. A resilient sorting algorithm must produce a sequence where every pair of uncorrupted keys is ordered correctly. Finocchi, Grandoni, and Italiano devised a δ-resilient deterministic mergesort algorithm that runs in O(n log n + δ2) time. We present a δ-resilient randomized algorithm (based on quicksort) that runs in O(n log n + δn log n) expected time and its deterministic variation that runs in O(n log n +δn log n) worst-case time. This improves the previous known result for δ >n log n. Our deterministric sorting relies on the notion of an approximate kth order statistic. For this auxiliary problem, we devise a deterministic algorithm that runs in O(n + δn) time and produces a key (either corrupted or not) whose order rank differs from k by at most O(δ).