The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.3.1 Sorting

Problem Input | Problem Output

INPUT                    OUTPUT

Input Description: A set of n items.

Problem: Arrange the items in increasing order.

Excerpt from The Algorithm Design Manual: Sorting is the fundamental algorithmic problem in computer science. Learning the different sorting algorithms is like learning scales for a musician. Sorting is the first step in solving a host of other algorithm problems. Indeed, ``when in doubt, sort'' is one of the first rules of algorithm design.

Sorting is also used to illustrate the standard paradigms of algorithm design. The result is that most programmers are familiar with many different sorting algorithms, which sows confusion as to which should be used for a given application.

Implementations

  • BSD Sort (C) (rating 10)
  • GNU Coreutils (C) (rating 10)
  • Standard Template library in C++ form SGI (C++) (rating 10)
  • CoSort: High Performance Data Transformation (Binary) (rating 9)
  • Syncsort Incorporated Software (Binary) (rating 9)
  • Ordinal Technology: Nsort (Binary) (rating 9)

    • Recommended Books

    Algorithms in Java, Third Edition (Parts 1-4) by Robert Sedgewick and Michael Schidlowsky Compared to What? by G. Rawlins Combinatorial Search by M. Aigner
    Programming Pearls by J. Bentley

    Related Problems
    Convex Hull
    Dictionaries
    Median and Selection
    Priority Queues
    Searching
    Topological Sorting


    This page last modified on 2008-07-10 .
    www.algorist.com