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.

The best book available for this problem is The Art of Computer Programming : Sorting and Searching by Donald Knuth.


Implementations

  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 7)
  • Handbook of Algorithms and Data Structures (Pascal) (rating 7)
  • Xtango and Polka Algorithm Animation Systems (C++) (rating 6)
  • Algorithms in C++ -- Sedgewick (C++) (rating 5)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 4)
  • Nijenhuis and Wilf: Combinatorial Algorithms (FORTRAN) (rating 3)
  • Combinatorica (Mathematica) (rating 2)

    Related Problems

  • Convex Hull
  • Dictionaries
  • Median and Selection
  • Priority Queues
  • Searching
  • Topological Sorting


    Previous Problem Next Problem

    View the graph for this file

    Bulletin Board
    About ``The Algorithm Design Manual''.
    Send us Mail
    The Stony Brook Algorithm Repository -- go to front page

    This page last modified on Wed Mar 07, 2001 .