World Library  
Flag as Inappropriate
Email this Article

Qsort

Article Id: WHEBN0033675095
Reproduction Date:

Title: Qsort  
Author: World Heritage Encyclopedia
Language: English
Subject: Sort, C standard library, C (programming language)
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Qsort

qsort is a C standard library function that implements a polymorphic sorting algorithm for arrays of arbitrary objects according to a user-provided comparison function. It is named after the "quicker sort" algorithm (a quicksort variant due to R. S. Scowen), which was originally used to implement it in the Unix C library, although the C standard does not require it to implement quicksort.[1]

Implementations of the qsort function achieve polymorphism by taking a function pointer to a three-way comparison function, as well as a parameter that specifies the size of its individual input objects. The C standard requires the comparison function to implement a total order on the items in the input array.[2]

A qsort function was in place in Version 3 Unix of 1973, but was then an assembler subroutine.[3] A C version, with roughly the interface of the standard C version, was in-place in Version 6 Unix.[4] It was rewritten in 1983 at Berkeley.[1] The function was standardized in ANSI C (1989).

Example

The following piece of C code shows how to sort a list of integers using qsort.

#include 

/* Comparison function. Receives two generic (void) pointers. */
int compare(const void *p, const void *q)
{
    int x = *(const int *)p;
    int y = *(const int *)q;
    /* to avoid undefined behaviour through signed integer overflow,
        avoid: return x - y; */
    int ret;
    if (x == y)
      ret = 0;
    else
      ret = (x < y) ? -1 : 1;

    return ret;
}

/* Sort an array of n integers, pointed to by a. */
void sort_ints(int *a, size_t n)
{
    qsort(a, n, sizeof(int), compare);
}

References

  1. ^ a b Bentley, Jon L.; McIlroy, M. Douglas (1993). "Engineering a sort function". Software—Practice and Experience 23 (11): 1249–1265.  
  2. ^ ISO/IEC 9899:201x, Programming Languages—C (draft). §7.22.5. November 16, 2010.
  3. ^ "qsort(III), from UNIX Programmer's Manual, Third Edition". Unix Archive. 
  4. ^ "qsort(III), from UNIX Programmer's Manual, Sixth Edition". Unix Archive. 
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.