Sorting/buildPointerBasedInput.c File Reference

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. More...

#include <stdlib.h>
#include <getopt.h>
#include <string.h>
#include <stdio.h>
#include "buildPointerBasedInput.h"
#include "problem.h"
#include "report.h"

Functions

int stringComp (char *a1, char *a2)
 comparator function for comparing two strings.
int ascending (const void *a1, const void *a2)
 default ascending operator provided externally
int descending (const void *a1, const void *a2)
 comparator function for descending order.
void killer (char *combined, int numElements)
 Take sorted/ascending set and permute into killer-of-median-quicksort order.
void prepareInput (int size, int argc, char **argv)
 Construct a random string of size ssize and have 'str1' and 'str2' be allocated strings with the same contents.
void postInputProcessing ()
 After sorting, can check whether sort succeeded.
void execute ()
 Execute by invoking malloc(numElements) a total of numT times.
void problemUsage ()
 No specific problem usage.

Variables

char ** strings
 information where input is stored.
int groupingSize = 5
 The size of the grouping is determined elsewhere.


Detailed Description

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.

Required Input:

  1. int numElements
  2. int verbose

Input flags:

  1. -a Numbers are sorted in ascending order
  2. -k Killer 'median-of-3' as proposed by Musser, 1997
  3. -w Use words from dictionary of 161,136 words of 3 or more letters
  4. -d Numbers are sorted in descending order
  5. -u n,o When paired with [a/d] determines number of pairs out of order, and distance of entity with which to swap
  6. -g Grouping size for worst-cast linear median-of-medians algorithm
External API
  1. void problemUsage() shows what is expected
  2. void postInputProcessing() performs post-solution processing
  3. void prepareInput() prepare the input
  4. void execute() begin the problem

For use by other modules:

   int groupingSize = 5;         default value is 5. Used by worst case
                                    select Kth algorithm.
 

Author:
George Heineman
Date:
6/15/08

Function Documentation

int ascending ( const void *  a1,
const void *  a2 
)

default ascending operator provided externally

int descending ( const void *  a1,
const void *  a2 
)

comparator function for descending order.

void execute (  ) 

Execute by invoking malloc(numElements) a total of numT times.

.numElements

output sum to be sure is correct.

void killer ( char *  combined,
int  numElements 
)

Take sorted/ascending set and permute into killer-of-median-quicksort order.

implementation derived from: http://ralphunden.net/content/tutorials/a-guide-to-introsort/

Note that the data is contiguous and we must swap as required large sequence of bytes (oh well; it won't count against costs).

void postInputProcessing (  ) 

After sorting, can check whether sort succeeded.

void prepareInput ( int  size,
int  argc,
char **  argv 
)

Construct a random string of size ssize and have 'str1' and 'str2' be allocated strings with the same contents.

use character-swapping algorithm from strfry.c in glibc

http://www.koders.com/c/fidBD83E492934F9F671DE79B11E6AC0277F9887CF5.aspx

terminate at word boundary, not including spaces.

void problemUsage (  ) 

No specific problem usage.

int stringComp ( char *  a1,
char *  a2 
)

comparator function for comparing two strings.


Variable Documentation

int groupingSize = 5

The size of the grouping is determined elsewhere.

char** strings

information where input is stored.

Algorithm Development Kit 1.0