Algorithms_in_a_Nutshell File List

Here is a list of all files with brief descriptions:
Addresses/alloc.cTask to allocate fixed number of elements.Example to simply time the allocation of a fixed number of elements whose size is determined by the user
Addresses/down.cTask to free elements from address table in reverse order.Allocated memory stored in the 'addr' table are free'd in reverse order
Addresses/memory.cStand-alone program to show examples of addresses Provide a small example to show how memory is allocated on the Stack and on the Heap
Addresses/order.cBase task definition for building 'addr' table.Constructs the 'addr' table full of allocated memory. Only later options (UP, DOWN, SCATTERED) determine the order in which it is free'd
Addresses/report.cHelper program to format the table of addresses.Helper program that properly formats the addresses for ease of reading
Addresses/scattered.cTask to free elements from address table in random order.Allocated memory stored in the 'addr' table are free'd in random order
Addresses/up.cTask to free elements from address table in order.Allocated memory stored in the 'addr' table are free'd in reverse order
bin/eval.cCompute averages and stdev over results.Assuming the number of trials is always greater than two, this program takes in the timing results of a number of 't' trials, throws away the best and the worst performing and computes the average (and stdev) of the remaining t-2 trials
Chapter1/large.cDriver for testing allocation/deallocation mechanisms. Allocate REALLY large number of allocations and then time the cost to deallocate just one of these (the last one)
Chapter1/tester.cDriver for testing allocation/deallocation mechanisms. Allocate REALLY large number of allocations and then time the cost to deallocate just one of these (the last one)
Chapter2/AdditionExample.javaJava Example showing four add implementations. Code to show alternative implementations for adding two n-digit numbers
Chapter2/addTest.cDriver for timing a variety of add implementations. Four separate add implementations are provided and they are all executed to compare their performance
Chapter2/newton.cExample program using Newton's method for root finding. Show the execution of Newton's method on a small example
Chapter2/Newton.javaJava Example of Newton's method. Java implementation of Newton's method that also shows the binary digits of the resulting floating point value to provide a sense of the convergance of the approach
Chapter3/comparison.cxxTime 100,000 allocations of a table of 100 strings. Allocate 100,000 tables of char* strings and time the result. Used as a baseline for comparing against Comparison.java
Chapter3/Comparison.javaTime 100,000 allocations of a table of 100 strings. Allocate 100,000 tables of String[] and time the result. Used as a baseline for comparing against comparison.cxx
Chapter3/example_3_2.cSample program that may CRASH your machine. Infinite recursion with output to see how long program can execute before it consumes available resources
Chapter4/numTranspositions.cCompute average number of transpositions in Insertion Sort of n elements. Exhaustively permute all n objects and compute the total number of transpositions when using Insertion Sort. The average is computed by dividing this total by the number of permutations. Really only useful for table sizes of less than 12
Clock/forLoop.cTask to add the integers from 1. Task to add the integers from 1..numElements. This can be timed using the timing infrastructure
Clock/sample.cShow timing example in both milliseconds and nanonseconds. Show the ability on Unix systems to time both using milliseconds and nanosecond timers
Clock/tr.cReport on the clock resolution for the given machine
Graph/fsInspector.cDriver for generating a graph by interpreting the file system as a graph. Traverse the file system from a particular root directory and construct a graph whose vertices are files and directories and whose edges are containment (within a file) or symbol links (as defined by unix)
Graph/Graph.cxxImplementation of Graph concept

Contains the implementation of the Graph class

Graph/Graph.h [code]Defines the Graph concept

A Graph=(V,E) and is a central data structure for numerous algorithms

Graph/GraphList.h [code]Defines Graph concept for linked lists

Representation of a graph using adjacency lists

Graph/testFS.cDriver to simply test the loading of a graph. Loads up a graph and outputs the number of vertices
Graph/testGraph.cxxSample (and Simple!) graph tests. Just a few test cases. Not too much here, really
Graph/AllPairsShortestPath/allPairsShortest.cxxFloyd-Warshall implementation

Contains the Floyd-Warshall implementation which solves the All Pairs Shortest Path problem

Graph/AllPairsShortestPath/allPairsShortest.h [code]Defines the All Pairs Shortest Problem interface
Graph/AllPairsShortestPath/figure.cCompute the results used by Figure in book. Computes the AllPairsShortestPath for sample graph
Graph/AllPairsShortestPath/test1.cxxTest Case for Floyd-Warshall

A test case

Graph/AllPairsShortestPath/test2.cxxTest Case for Floyd-Warshall

A test case

Graph/AllPairsShortestPath/testGraph.cTest Case for All Pairs Shortest Path

Loads up a sample graph and computes All Pairs Shortest Path

Graph/BinaryHeap/BinaryHeap.cxxContains the implementation of a BinaryHeap

A BinaryHeap is a core data structure that represents a heap within a fixed array of size n elements

Graph/BinaryHeap/BinaryHeap.h [code]Defines the BinaryHeap concept

A BinaryHeap is a core data structure that represents a heap within a fixed array of size n elements

Graph/BinaryHeap/test1.cxxTest Case for Binary Heap

A test case

Graph/BinaryHeap/test2.cxxTest Case for Binary Heap

A test case

Graph/BreadthFirstSearch/bfs.cxxContains the Breadth-First Search implementation

Implementation of Breadth First Search algorithm over a graph

Graph/BreadthFirstSearch/bfs.h [code]Defines the interface to Breadth-First Search

Defines the interface to breadth-first search

Graph/BreadthFirstSearch/counter_bfs.cxxExtends Breadth First Search with counter

A breadth-first search implementation that increments a counter with each vertex found, to be able to compare results against corresponding depth-first search implementations

Graph/BreadthFirstSearch/figure6_12.cxxSample figure showing Breadth-First Search for book

Implementation of figure for book

Graph/DepthFirstSearch/dfs.cxxContains the Depth-First Search implementation

Implementation of Depth First Search algorithm over a graph

Graph/DepthFirstSearch/dfs.h [code]Defines the interface to Depth-First Search

Defines the interface to depth-first search

Graph/DepthFirstSearch/figure.cxxContains Figure for book. Sample graph to be used to generate figure in book. Ultimately used by Dijkstra's algorithm
Graph/DepthFirstSearch/figure6_10.cxxContains Figure for book. Sample graph to be used to generate figure in book
Graph/DepthFirstSearch/test1.cxxTest Case for Depth-First Search

A test case

Graph/DepthFirstSearch/test2.cxxTest Case for Depth-First Search

A test case

Graph/DepthFirstSearch/test3.cxxTest Case for Depth-First Search

A test case

Graph/MinimumSpanningTree/mst.cxxPrim's Algorithm for Minimum Spanning Tree problem
Graph/MinimumSpanningTree/mst.h [code]Defines the interface to Minimum Spanning Tree

Defines the interface to minimum spanning tree problem

Graph/MinimumSpanningTree/process.cxxDriver for timing MST algorithmsn

Compute performance of Prim's algorithm

Graph/MinimumSpanningTree/smallTest.cxxSmall test case for MST

A test case

Graph/MinimumSpanningTree/testCormen.cxxSmall test case for MST

A test case

Graph/SingleSourceShortestPath/bellmanFord.cxxBellmanFord implementation of Single Source Shortest Path

Contains BellmanFord implementation for solving Single Source Shortest Path problems

Graph/SingleSourceShortestPath/dense.cxxDijkstra's implementation for dense graphs
Graph/SingleSourceShortestPath/generateBench.cProgram to generate a bunch of large (sparse) sample graphs
Graph/SingleSourceShortestPath/rawDense.cxxOptimized Dijkstra's implementation for dense graphs
Graph/SingleSourceShortestPath/rawTest.cxxTest case for optimized implementation
Graph/SingleSourceShortestPath/singleSourceShortest.cxxDijsktra's Algorithm Implementation

Contains implementatino of Dijkstra's Algorithm

Graph/SingleSourceShortestPath/singleSourceShortest.h [code]Defines the Single Pair Shortest Path Problem interface
Graph/SingleSourceShortestPath/test.cxxTest Case for Single Source

A test case

Graph/SingleSourceShortestPath/testBellmanFord.cxxTest case for Bellman Ford
Graph/SingleSourceShortestPath/testBellmanFordFigure.cxxTest case for Bellman Ford
Graph/SingleSourceShortestPath/testCaseBellmanFord.cxxAnother test case for Bellman Ford
Graph/SingleSourceShortestPath/testFigure.cxxTest case for Fact Sheet figure
Graph/SingleSourceShortestPath/testGraph.cxxTest case
Graph/SingleSourceShortestPath/tsplib.cTest driver code that understands TSP data formatn

Driver that can load up dense graphs whose input is stored using the TSP format as recognized by the community

Graph/ZeroKnowledge/sample.cxxDriver to show size of complex graphs that are possible
Math/buildInt.cTask to create integers to use for comparison

Execute for a fixed number of iterations the comparison of two random integers

Math/buildString.cTask to create strings to use for comparison

Execute for a fixed number of iterations the comparison of two random strings

Math/DivTimeDouble.cTask to create two double numbers for division. Execute for a fixed number of iterations the division of two random double numbers
Math/DivTimeFloat.cTask to create two float numbers for division. Execute for a fixed number of iterations the division of two random float numbers
Math/DivTimeInt.cTask to create two int numbers for division. Execute for a fixed number of iterations the division of two random int numbers
Math/MulTimeDouble.cTask to create two double numbers for muliplication. Execute for a fixed number of iterations the multiplication of two random double numbers
Math/MulTimeFloat.cTask to create two float numbers for muliplication. Execute for a fixed number of iterations the multiplication of two random float numbers
Math/MulTimeInt.cTask to create two int numbers for muliplication. Execute for a fixed number of iterations the multiplication of two random int numbers
Math/MulTimeLongDouble.cTask to create two long double numbers for muliplication. Execute for a fixed number of iterations the multiplication of two random long double numbers
Math/MulTimeShort.cTask to create two short numbers for muliplication. Execute for a fixed number of iterations the multiplication of two random short numbers
Math/SqrtTimeDouble.cTask to create double floating point number for sqrt. Execute for a fixed number of iterations the square root of a double
Math/SqrtTimeFloat.cTask to create floating point number for sqrt. Execute for a fixed number of iterations the square root of a float
Memory/heapbust.cTask to show code that crashes a C program. Provide code that exhausts all available memory and crashes. Make sure that you don't execute this program on a shared machine since it might force that machine to be rebooted
Memory/sample.cProgram to show addresses in memory

Small program to show internal memory addresses

Memory/stackbust.cTask to show code that crashes a C program. Provide code that exhausts all available memory by using infinite recursion. This will not likely crash your machine
Search/binarySearch.cTask to perform number of binary search operations over a binary tree. Load up a number of strings into a non-balancing binary tree and define the search task for locating desired elements from within the tree
Search/binarySearchFileInteger.cTask to perform number of binary search operations on a disk file with integers. Receive integers one by one (must be in sorted order!) to be written to disk where a file "input.dat" is first created and then it is used as the source for a disk-based binary search of integers
Search/binarySearchInteger.cTask to perform number of binary search operations on an array

Receive integers one by one (in sorted order) and create an array over which binary searches are performed

Search/binarySearchTreeInteger.cTask to perform number of binary search operations on a non-balanced binary tree

Receive integers one by one (in sorted order) and create a binary tree which means the tree heavily leans to the right and ultimately forms a linked list

Search/buildIntegerProblem.cDriver that populates a search structure by invoking insert on integers in sorted order. Populates a search structure by first inserting numElements integers, in sorted order. Thereafter, performs a number of search operations as dictated by the command line arguments
Search/buildProblem.cDriver that populates a search structure by invoking insert on strings in random order. Populates a search structure by first inserting numElements strings, in random order. Thereafter, performs a number of search operations as dictated by the command line arguments
Search/linkedList.cTask to perform searches in unordered linked list

Load up a linked list of strings and perform number of unordered searches

Search/linkedListMoveToEnd.cTask to perform searches in unordered linked list and move to end when found. Load up a linked list of strings and perform number of unordered searches. No check for NULL is used. Move to End of list on a successful find
Search/linkedListMoveToFront.cTask to perform searches in unordered linked list and move to front when found. Load up a linked list of strings and perform number of unordered searches. No check for NULL is used. Move to Front of list on a successful find
Search/moveToEnd.cTask to perform searches in unordered array and move to end when found. Load up an array of strings and perform number of unordered searches. No check for NULL is used. Move to End of array on a successful find
Search/moveToFront.cTask to perform searches in unordered array and move to front when found. Load up an array of strings and perform number of unordered searches. No check for NULL is used. Move to Front of array on a successful find
Search/moveUp.cTask to perform searches in unordered array and move up one slot when found. Load up an array of strings and perform number of unordered searches. No check for NULL is used. Move up one slot for each successful find
Search/search.cTask to perform searches in unordered array

Load up an array of strings and perform number of unordered searches

Search/Search.javaTask to perform searches in unordered array

Construct example collection from permutations of the string 'abcdef' and allow command-line interface to search for a target string from within this collection and return its time in milliseconds

Search/searchInteger.cTask to perform searches in unordered array

Load up an array of integers and perform number of unordered searches

Search/searchNull.cTask to perform searches in unordered array

Load up an array of strings and perform number of unordered searches

Search/SearchNull.javaTask to perform searches in unordered array with Null check. Construct example collection from permutations of the string 'abcdef' and allow command-line interface to search for a target string from within this collection and return its time in milliseconds. Search for NULL is included in the timing
Search/searchOrdered.cTask to perform searches in ordered array

Load up an array of strings and perform number of ordered searches

Sorting/buildDoubleBasedInput.cDriver to construct array of doubles for sorting. Build up a pointer-based array of Doubles to use as a basis for testing the various sorting algorithms
Sorting/buildDoubleBasedInput.h [code]Define interface for sorting algorithms over pointer-based information

Build up a pointer-based array of Doubles to use as a basis for testing the various sorting algorithms

Sorting/buildFileBasedInput.cDriver to construct array of Strings on disk

Build up a file on disk representing an array of strings to test the various sorting algorithms

Sorting/buildFileBasedInput.h [code]Define interface for sorting algorithms over information stored on disk

Build up a file of strings of fixed-size to use as input for the various sorting algorithms

Sorting/buildPointerBasedInput.cDriver to construct array of strings for sorting. Build up a pointer-based array of strings to use as a basis for testing the various sorting algorithms
Sorting/buildPointerBasedInput.h [code]Define interface for sorting algorithms over pointer-based information. Build up a pointer-based array of Strings to use as a basis for testing the various sorting algorithms
Sorting/buildValueBasedInput.cDriver to construct contiguous string block for sorting. Build up a value-based array of strings to use as a basis for testing the various sorting algorithms
Sorting/buildValueBasedInput.h [code]Define interface for sorting algorithms over value-based information. Build up a value-based array of Strings to use as a basis for testing the various sorting algorithms
Sorting/Doubles/hash.cDefine hash to use for Bucket Sort of doubles drawn from the range [0,1]. Bucket Sort succeeds with uniform distribution since the hashing function can partition the input set of n values into n bins. The number of elements in the collection (numElements) is used to define a set of 'num' bins
Sorting/FileBased/insertion.cDefine code to produce a file containing array of strings which are to be sorted. Implementation of file-based sorting algorithm, where input is stored on disk in a contiguous block of n*s bytes where n is the number of elements in the disk and s is the length of each one (no null-terminated values used to determine string length)
Sorting/Ints/countingSort.cImplementation of CountingSort over integer array Implementation of counting-sort using integer array where each element is drawn from the range [0,k)
Sorting/Ints/fileLoad.cDriver that sorts integer array loaded up from disk The file to be loaded is a sequence of integers, one per line
Sorting/Ints/heapSort.cOptimized (and efficient) Heap Sort implementation. This implementation of Heap Sort is taken from:
Sorting/Ints/quickSort.cUse native qsort() function to sort integer array. This implementation simply invokes the qsort() function available from the Unix operating system. Note that on some system variants, the qsort routine is actually implemented using Heap Sort
Sorting/Ints/testCountingSort.cTest the Counting Sort algorithm on small example. A test case for Counting Sort
Sorting/Longs/dot.cImplementation of interface to DOT for sorting graphs. Enable DOT graphs (http://www.graphviz.org) to be generatd from the invocation of specially crafted sort routines. This code is used to show the progress of MedianSort and QuickSort in the book
Sorting/Longs/dot.h [code]Define interface for accessing API to generate sorting DOT graphs. Enable DOT graphs (http://www.graphviz.org) to be generatd from the invocation of specially crafted sort routines. This code is used to show the progress of MedianSort and QuickSort in the book
Sorting/Longs/dot_baseQsort.cGenerate QuickSort DOT graph

Implementation that uses dot.h interface to produce on stdout the DOT commands for a QuickSort execution

Sorting/Longs/dot_medianSort.cGenerate MedianSort DOT graph

Implementation that uses dot.h interface to produce on stdout the DOT commands for a MedianSort execution

Sorting/Longs/figure4-8.cGenerate Figure 4-8 of the book

Example (test case) for median sort and produces image

Sorting/Longs/figure4-9.cGenerate Figure 4-9 of the book

Example (test case) for median sort and produces image

Sorting/Longs/figure4-heapsort.cGenerate Small example(s) for heapsort. Several test cases for heapsort. Used in debug mode (step by step) when manually generating the figures in the book
Sorting/Longs/figure4-qsort.cGenerate Small example(s) for Quicksort. Several test cases for Quicksort. Used in debug mode (step by step) when manually generating the figures in the book
Sorting/PointerBased/baseQsort.cQuicksort implementation

Complete Quicksort implementation optimized to switch to Insertion Sort when problem sizes are less than or equal to minSize in length

Sorting/PointerBased/bubblePtr.cContain Bubble Sort implementation

Though the book never refers to Bubble Sort (for which we are proud), we had to just include the code for that ill-fated algorithm to show just how bad some sorting algorithms can be

Sorting/PointerBased/bucketArraySortPtr.cDefine core driver for Bucket Sort, pending the proper hash() and numBuckets() implementations, using arrays. To employ Bucket Sort you only need to (a) provide a meaningful hash () method to return an integer given an element; and (b) provide a method to compute the number of buckets to use. This code acts as the driver and relies on external code to provide the domain-specific coding
Sorting/PointerBased/bucketArraySortPtr.h [code]Define interface for accessing Bucket Sort

To employ Bucket Sort you only need to (a) provide a meaningful hash () method to return an integer given an element; and (b) provide a method to compute the number of buckets to use

Sorting/PointerBased/bucketLinkedListSortPtr.cDefine core driver for Bucket Sort, pending the proper hash() and numBuckets() implementations, using linked lists. To employ Bucket Sort you only need to (a) provide a meaningful hash () method to return an integer given an element; and (b) provide a method to compute the number of buckets to use. This code acts as the driver and relies on external code to provide the domain-specific coding
Sorting/PointerBased/bucketLinkedListSortPtr.h [code]Define interface for accessing Bucket Sort

To employ Bucket Sort you only need to (a) provide a meaningful hash () method to return an integer given an element; and (b) provide a method to compute the number of buckets to use

Sorting/PointerBased/heapSort.cGeneric Heap Sort implementation

Contains an optimized Heap Sort implementation for sorting strings

Sorting/PointerBased/insertionPtr.cInsertion Sort implementation

Contains Insertion Sort implementation

Sorting/PointerBased/invertedInsertionQsort.cNovel variation of Quicksort (which fails badly)

Variation to Quicksort (which fails badly) which considers just using the base Quicksort cases to partition the relevant subarrays, without actually sorting the smaller cases

Sorting/PointerBased/Linux-2.6.11-rc5-lib-qsort.c
Sorting/PointerBased/medianMinSort.cContains Median Sort implementation with Min Size optimization

Contains Median Sort implementation that switches to Insertion Sort when the problem size is small enough

Sorting/PointerBased/medianSort.cContains Median Sort implementation

Contains Median Sort implementation

Sorting/PointerBased/minSize0.cDefines MinSize set of 0

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize1.cDefines MinSize set of 1

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize10.cDefines MinSize set of 10

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize11.cDefines MinSize set of 11

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize12.cDefines MinSize set of 12

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize13.cDefines MinSize set of 13

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize14.cDefines MinSize set of 14

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize15.cDefines MinSize set of 15

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize16.cDefines MinSize set of 16

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize17.cDefines MinSize set of 17

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize18.cDefines MinSize set of 18

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize19.cDefines MinSize set of 19

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize2.cDefines MinSize set of 2

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize20.cDefines MinSize set of 20

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize3.cDefines MinSize set of 3

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize30.cDefines MinSize set of 30

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize4.cDefines MinSize set of 4

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize5.cDefines MinSize set of 5

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize6.cDefines MinSize set of 6

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize7.cDefines MinSize set of 7

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize8.cDefines MinSize set of 8

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/minSize9.cDefines MinSize set of 9

Done in this way to be able to assemble various alternative sorting arrangements staticly, rather than requiring one to recompile an application as part of running a test suite

Sorting/PointerBased/NonRecursiveQsort.cA Quicksort implementation without recursion
Sorting/PointerBased/pivotFirst.cCode to select leftmost element as pivot index

Given array vals[left,right] select left as the pivot index

Sorting/PointerBased/pivotLast.cCode to select rightmost element as pivot index

Given array vals[left,right] select right as the pivot index

Sorting/PointerBased/pivotMedianOfMedians.cCode to select median of medians as pivot index

Given array vals[left,right] select left as the pivot index

Sorting/PointerBased/pivotMedianOfThree.cCode to select random index as pivot index from array of strings

Given array vals[left,right] of strings, select random index within this range to use for partition

Sorting/PointerBased/pivotRandom.cCode to select random index as pivot index

Given array vals[left,right] select random index within this range to use for partition

Sorting/PointerBased/revisedPartition_baseQsort.cBase implementation of Quicksort with leftmost pivot selection and all subcases sorted by do_qsort. Straight Quicksort implementation with no optimizations
Sorting/PointerBased/selectionSort.cContains Selection Sort implementation. Straight Selection Sort implementation
Sorting/PointerBased/selectKth.cWithout recursion, Select the kth element of ar[left, right]

A non-recursive implementation to select the kth smallest element from the subarray ar[left, right]

Sorting/PointerBased/selectKthRecursive.cRecursive implementation to select the kth element of ar[left, right]

A recursive implementation to select the kth smallest element from the subarray ar[left, right]

Sorting/PointerBased/selectKthWorstLinear.cGeneric implementation of BFPRT to select kth smallest from an array in worst-case linear time. A recursive implementation of BFPRT to select the kth smallest element within ar[left, right] in worst-case linear time
Sorting/PointerBased/selectKthWorstLinearFive.cOptimized implementation of BFPRT with groupingSize=5 to select kth smallest from an array in worst-case linear time. A recursive implementation of BFPRT to select the kth smallest element within ar[left, right] in worst-case linear time. Customized to group the elements in groups of 5
Sorting/PointerBased/selectKthWorstLinearFour.cOptimized implementation of BFPRT with groupingSize=4 to select kth smallest from an array in worst-case linear time. A recursive implementation of BFPRT to select the kth smallest element within ar[left, right] in worst-case linear time. Customized to group the elements in groups of 4
Sorting/PointerBased/selectKthWorstLinearThree.cOptimized implementation of BFPRT with groupingSize=3 to select kth smallest from an array in worst-case linear time. A recursive implementation of BFPRT to select the kth smallest element within ar[left, right] in worst-case linear time. Customized to group the elements in groups of 3
Sorting/PointerBased/straight_HeapSort.cGeneric Heap Sort implementation. A recursive Heap Sort implementation
Sorting/Strings/hash17576.cCreate a Hash table to support 26^3 elements for Bucket Sort. Enable Bucket Sort over a hash table with 26^3 buckets
Sorting/Strings/hash26.cCreate a Hash table to support 26 elements for Bucket Sort. Enable Bucket Sort over a hash table with 26 buckets
Sorting/Strings/hash676.cCreate a Hash table to support 26^2 elements for Bucket Sort. Enable Bucket Sort over a hash table with 26^2 buckets
Sorting/ValueBased/insertion.cInsertion Sort implementation over value-based arrays. Contains Insertion Sort implementation for value-based arrays. Optimized to use memmove for bulk moves
Sorting/ValueBased/insertion_all_copy.cInsertion Sort implementation over value-based arrays. Contains Insertion Sort implementation for value-based arrays. No special optimizations, so each transposition results in a single swap of elements
Sorting/ValueBased/Linux-2.6.11-rc5-lib-qsort.c
Sorting/ValueBased/Linux-2.6.6-rc2-fs-xfs-support-qsort.c
Sorting/ValueBased/straight-qsort.cStraight Quicksort access to qsort() unix call. Simply invoke the underlying Unix qsort() library method to sort the value based array
Timing/benchmark.cTask to sleep for fixed length of time

Simple example to show accuracy of timing code when the task at hand does nothing more than sleep for a fixed length of time

Timing/problem.h [code]Define interface to problem statement

Each problem statement is defined by four methods:

Timing/report.cCommon reporting code

Implements a standard reporting approach used throughout the repository

Timing/report.h [code]Define interface to reporting infrastructure

if -DCOUNT is among the compile flags, then certain algorithms are enabled to compute the number of comparisons, the number of swaps, and the number of comparisons with Null

Timing/timing.cCommon driver to launch many experiments. Implements a standard driver for processing command line arguments to retrieve (a) the number of elements; (b) the verbose setting; (c) the randomized seed to use to enable repeated experiments
Algorithm Development Kit 1.0