ALCOMFT-TR-03-50

Conrado Mart\'\inez
Partial Quicksort
Barcelona. Work package 4. September 2003.

Abstract: This short note considers the following common problem: given an array with n elements, rearrange it so that its first m components contain the m smallest elements in the array in ascending order. We propose here a simple variation of quicksort that efficiently solves the problem, and show and quantify how it outperforms other straightforward alternatives.

Postscript file: ALCOMFT-TR-03-50.ps.gz (72 kb).