Cover Image
QR Code

AN ANALYSIS OF THE WORST-CASE PERFORMANCE OF QUICKSORT.

C.A.R. Hoare's quicksort algorithm has become a very popular sorting algorithm due to the average performance of θ(n log n), limited use of extra storage (typically θ(logn) recursive calls) and better performance on average compared to heapsort (another θ(n log n) sorting algorithm). It may be found...

Full description

Published in:InSight: Rivier Academic Journal Vol. 7; no. 1; pp. 1 - 17
Main Author: Marceau, Robert R.
Format: Article
Published: Rivier College (InSight: Rivier Academic Journal) Apr2011
Subjects:
Algorithms
Sorting (Electronic computers)
C++
C (Computer program language)
Java programming language
Permutations
Online Access:View this record in EBSCOhost
fields @attributes:
  recordID: 1
pdfLink:
plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=67414406&site=ehost-live
header:
  @attributes:
    shortDbName: hlh
    uiTerm: 67414406
    longDbName: Humanities International Complete
    uiTag: AN
  controlInfo:
    bkinfo:
    jinfo:
      jid:
        19469233
        B2BS
      jtl: InSight: Rivier Academic Journal
      issn: 19469233
      maglogo: N
    pubinfo:
      dt: Apr2011
      vid: 7
      iid: 1
      pid: 59866
      pub: Rivier College (InSight: Rivier Academic Journal)
    artinfo:
      ui: 67414406
      ppf: 1
      ppct: 16
      formats:
      tig:
        atl: AN ANALYSIS OF THE WORST-CASE PERFORMANCE OF QUICKSORT.
      aug:
        au: Marceau, Robert R.
        affil: M.S. Program in Computer Science, Rivier College
      su:
        Algorithms
        Sorting (Electronic computers)
        C++
        C (Computer program language)
        Java programming language
        Permutations
      sug:
        subj:
          Algorithms
          Sorting (Electronic computers)
          C++
          C (Computer program language)
          Java programming language
          Permutations
      ab: C.A.R. Hoare's quicksort algorithm has become a very popular sorting algorithm due to the average performance of θ(n log n), limited use of extra storage (typically θ(logn) recursive calls) and better performance on average compared to heapsort (another θ(n log n) sorting algorithm). It may be found in several standard libraries supporting C, C++, and Java. The major drawback in the quicksort algorithm is the θ(n²) worse case performance. Unfortunately, this performance is exhibited for some rather common initial permutations. The author intends to look into this performance of the quicksort algorithm, and in particular potential modifications to minimize the probability that the worst-case performance will be exhibited.
      pubtype: Academic Journal
      doctype: Article
      src: R
    language: English
    refInfo:
    copyright:
      @attributes:
        flag: Y
      dt:
        @attributes:
          year: 2011
    holdings:
      @attributes:
        islocal: N