Addresses/alloc.c | Task 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.c | Task to free elements from address table in reverse order.Allocated memory stored in the 'addr' table are free'd in reverse order |
Addresses/memory.c | Stand-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.c | Base 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.c | Helper program to format the table of addresses.Helper program that properly formats the addresses for ease of reading |
Addresses/scattered.c | Task to free elements from address table in random order.Allocated memory stored in the 'addr' table are free'd in random order |
Addresses/up.c | Task to free elements from address table in order.Allocated memory stored in the 'addr' table are free'd in reverse order |
bin/eval.c | Compute 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.c | Driver 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.c | Driver 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.java | Java Example showing four add implementations. Code to show alternative implementations for adding two n-digit numbers |
Chapter2/addTest.c | Driver for timing a variety of add implementations. Four separate add implementations are provided and they are all executed to compare their performance |
Chapter2/newton.c | Example program using Newton's method for root finding. Show the execution of Newton's method on a small example |
Chapter2/Newton.java | Java 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.cxx | Time 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.java | Time 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.c | Sample program that may CRASH your machine. Infinite recursion with output to see how long program can execute before it consumes available resources |
Chapter4/numTranspositions.c | Compute 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.c | Task to add the integers from 1. Task to add the integers from 1..numElements. This can be timed using the timing infrastructure |
Clock/sample.c | Show timing example in both milliseconds and nanonseconds. Show the ability on Unix systems to time both using milliseconds and nanosecond timers |
Clock/tr.c | Report on the clock resolution for the given machine |
Graph/fsInspector.c | Driver 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.cxx | Implementation 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.c | Driver to simply test the loading of a graph. Loads up a graph and outputs the number of vertices |
Graph/testGraph.cxx | Sample (and Simple!) graph tests. Just a few test cases. Not too much here, really |
Graph/AllPairsShortestPath/allPairsShortest.cxx | Floyd-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.c | Compute the results used by Figure in book. Computes the AllPairsShortestPath for sample graph |
Graph/AllPairsShortestPath/test1.cxx | Test Case for Floyd-Warshall A test case |
Graph/AllPairsShortestPath/test2.cxx | Test Case for Floyd-Warshall A test case |
Graph/AllPairsShortestPath/testGraph.c | Test Case for All Pairs Shortest Path Loads up a sample graph and computes All Pairs Shortest Path |
Graph/BinaryHeap/BinaryHeap.cxx | Contains 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.cxx | Test Case for Binary Heap A test case |
Graph/BinaryHeap/test2.cxx | Test Case for Binary Heap A test case |
Graph/BreadthFirstSearch/bfs.cxx | Contains 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.cxx | Extends 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.cxx | Sample figure showing Breadth-First Search for book Implementation of figure for book |
Graph/DepthFirstSearch/dfs.cxx | Contains 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.cxx | Contains Figure for book. Sample graph to be used to generate figure in book. Ultimately used by Dijkstra's algorithm |
Graph/DepthFirstSearch/figure6_10.cxx | Contains Figure for book. Sample graph to be used to generate figure in book |
Graph/DepthFirstSearch/test1.cxx | Test Case for Depth-First Search A test case |
Graph/DepthFirstSearch/test2.cxx | Test Case for Depth-First Search A test case |
Graph/DepthFirstSearch/test3.cxx | Test Case for Depth-First Search A test case |
Graph/MinimumSpanningTree/mst.cxx | Prim'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.cxx | Driver for timing MST algorithmsn Compute performance of Prim's algorithm |
Graph/MinimumSpanningTree/smallTest.cxx | Small test case for MST A test case |
Graph/MinimumSpanningTree/testCormen.cxx | Small test case for MST A test case |
Graph/SingleSourceShortestPath/bellmanFord.cxx | BellmanFord implementation of Single Source Shortest Path Contains BellmanFord implementation for solving Single Source Shortest Path problems |
Graph/SingleSourceShortestPath/dense.cxx | Dijkstra's implementation for dense graphs |
Graph/SingleSourceShortestPath/generateBench.c | Program to generate a bunch of large (sparse) sample graphs |
Graph/SingleSourceShortestPath/rawDense.cxx | Optimized Dijkstra's implementation for dense graphs |
Graph/SingleSourceShortestPath/rawTest.cxx | Test case for optimized implementation |
Graph/SingleSourceShortestPath/singleSourceShortest.cxx | Dijsktra'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.cxx | Test Case for Single Source A test case |
Graph/SingleSourceShortestPath/testBellmanFord.cxx | Test case for Bellman Ford |
Graph/SingleSourceShortestPath/testBellmanFordFigure.cxx | Test case for Bellman Ford |
Graph/SingleSourceShortestPath/testCaseBellmanFord.cxx | Another test case for Bellman Ford |
Graph/SingleSourceShortestPath/testFigure.cxx | Test case for Fact Sheet figure |
Graph/SingleSourceShortestPath/testGraph.cxx | Test case |
Graph/SingleSourceShortestPath/tsplib.c | Test 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.cxx | Driver to show size of complex graphs that are possible |
Math/buildInt.c | Task to create integers to use for comparison Execute for a fixed number of iterations the comparison of two random integers |
Math/buildString.c | Task to create strings to use for comparison Execute for a fixed number of iterations the comparison of two random strings |
Math/DivTimeDouble.c | Task to create two double numbers for division. Execute for a fixed number of iterations the division of two random double numbers |
Math/DivTimeFloat.c | Task to create two float numbers for division. Execute for a fixed number of iterations the division of two random float numbers |
Math/DivTimeInt.c | Task to create two int numbers for division. Execute for a fixed number of iterations the division of two random int numbers |
Math/MulTimeDouble.c | Task to create two double numbers for muliplication. Execute for a fixed number of iterations the multiplication of two random double numbers |
Math/MulTimeFloat.c | Task to create two float numbers for muliplication. Execute for a fixed number of iterations the multiplication of two random float numbers |
Math/MulTimeInt.c | Task to create two int numbers for muliplication. Execute for a fixed number of iterations the multiplication of two random int numbers |
Math/MulTimeLongDouble.c | Task 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.c | Task to create two short numbers for muliplication. Execute for a fixed number of iterations the multiplication of two random short numbers |
Math/SqrtTimeDouble.c | Task to create double floating point number for sqrt. Execute for a fixed number of iterations the square root of a double |
Math/SqrtTimeFloat.c | Task to create floating point number for sqrt. Execute for a fixed number of iterations the square root of a float |
Memory/heapbust.c | Task 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.c | Program to show addresses in memory Small program to show internal memory addresses |
Memory/stackbust.c | Task 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.c | Task 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.c | Task 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.c | Task 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.c | Task 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.c | Driver 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.c | Driver 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.c | Task to perform searches in unordered linked list Load up a linked list of strings and perform number of unordered searches |
Search/linkedListMoveToEnd.c | Task 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.c | Task 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.c | Task 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.c | Task 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.c | Task 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.c | Task to perform searches in unordered array Load up an array of strings and perform number of unordered searches |
Search/Search.java | Task 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.c | Task to perform searches in unordered array Load up an array of integers and perform number of unordered searches |
Search/searchNull.c | Task to perform searches in unordered array Load up an array of strings and perform number of unordered searches |
Search/SearchNull.java | Task 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.c | Task to perform searches in ordered array Load up an array of strings and perform number of ordered searches |
Sorting/buildDoubleBasedInput.c | Driver 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.c | Driver 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.c | Driver 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.c | Driver 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.c | Define 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.c | Define 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.c | Implementation 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.c | Driver that sorts integer array loaded up from disk The file to be loaded is a sequence of integers, one per line |
Sorting/Ints/heapSort.c | Optimized (and efficient) Heap Sort implementation. This implementation of Heap Sort is taken from: |
Sorting/Ints/quickSort.c | Use 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.c | Test the Counting Sort algorithm on small example. A test case for Counting Sort |
Sorting/Longs/dot.c | Implementation 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.c | Generate QuickSort DOT graph Implementation that uses dot.h interface to produce on stdout the DOT commands for a QuickSort execution |
Sorting/Longs/dot_medianSort.c | Generate MedianSort DOT graph Implementation that uses dot.h interface to produce on stdout the DOT commands for a MedianSort execution |
Sorting/Longs/figure4-8.c | Generate Figure 4-8 of the book Example (test case) for median sort and produces image |
Sorting/Longs/figure4-9.c | Generate Figure 4-9 of the book Example (test case) for median sort and produces image |
Sorting/Longs/figure4-heapsort.c | Generate 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.c | Generate 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.c | Quicksort 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.c | Contain 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.c | Define 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.c | Define 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.c | Generic Heap Sort implementation Contains an optimized Heap Sort implementation for sorting strings |
Sorting/PointerBased/insertionPtr.c | Insertion Sort implementation Contains Insertion Sort implementation |
Sorting/PointerBased/invertedInsertionQsort.c | Novel 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.c | Contains 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.c | Contains Median Sort implementation Contains Median Sort implementation |
Sorting/PointerBased/minSize0.c | Defines 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.c | Defines 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.c | Defines 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.c | Defines 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.c | Defines 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.c | Defines 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.c | Defines 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.c | Defines 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.c | Defines 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.c | Defines 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.c | Defines 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.c | Defines 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.c | Defines 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.c | Defines 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.c | Defines 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.c | Defines 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.c | Defines 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.c | Defines 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.c | Defines 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.c | Defines 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.c | Defines 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.c | Defines 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.c | A Quicksort implementation without recursion |
Sorting/PointerBased/pivotFirst.c | Code to select leftmost element as pivot index Given array vals[left,right] select left as the pivot index |
Sorting/PointerBased/pivotLast.c | Code to select rightmost element as pivot index Given array vals[left,right] select right as the pivot index |
Sorting/PointerBased/pivotMedianOfMedians.c | Code to select median of medians as pivot index Given array vals[left,right] select left as the pivot index |
Sorting/PointerBased/pivotMedianOfThree.c | Code 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.c | Code 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.c | Base implementation of Quicksort with leftmost pivot selection and all subcases sorted by do_qsort. Straight Quicksort implementation with no optimizations |
Sorting/PointerBased/selectionSort.c | Contains Selection Sort implementation. Straight Selection Sort implementation |
Sorting/PointerBased/selectKth.c | Without 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.c | Recursive 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.c | Generic 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.c | Optimized 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.c | Optimized 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.c | Optimized 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.c | Generic Heap Sort implementation. A recursive Heap Sort implementation |
Sorting/Strings/hash17576.c | Create 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.c | Create a Hash table to support 26 elements for Bucket Sort. Enable Bucket Sort over a hash table with 26 buckets |
Sorting/Strings/hash676.c | Create 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.c | Insertion 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.c | Insertion 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.c | Straight Quicksort access to qsort() unix call. Simply invoke the underlying Unix qsort() library method to sort the value based array |
Timing/benchmark.c | Task 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.c | Common 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.c | Common 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 |