Some Applications in Algorithmics

Jean-François Mari and René Schott
Additional contact information
Jean-François Mari: LORIA and Université Nancy 2
René Schott: Université Henri Poincaré-Nancy 1

Chapter Chapter 3 in Probabilistic and Statistical Methods in Computer Science, 2001, pp 57-151 from Springer

Abstract: Abstract Quicksort is a fast sorting algorithm, widely used for internal sorting. The basic idea is the choice of a partitioning element K. For example, let us consider the integer sequence [Régnier, 1989]: 45, 677, 98, 43, 42, 41, 60, 130, 32, 67 and choose K = 67 as the partitioning element. Scanning the left sublist from left to right, one exchanges any key greater than K with a key of the right sublist, scanned from right to left. This builds a list where K has its final position, all the keys to its left (resp. to its right) being smaller (resp. larger) than K.The intermediate stages are: 45 32 677 67 45 32 60 98 130 677 67 45 32 60 43 42 41 98 130 677 67 45 32 60 43 42 41 98 130 677 67

Keywords: Markov Chain; Voronoi Diagram; Priority Queue; Binary Search Tree; Conflict Graph (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4757-6280-8_3

Ordering information: This item can be ordered from
http://www.springer.com/9781475762808

DOI: 10.1007/978-1-4757-6280-8_3

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().