Sorting/buildValueBasedInput.c File Reference

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

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

Functions

int stringComp (char *a1, char *a2)
 comparator function for comparing string based upon ELEMENT_SIZE.
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 (struct strElement *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

strElementstrings
 information stored in memory.


Detailed Description

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.

Build up a value-based array of Strings. This means that a fixed elementSize

Required Input:

  1. int numElements
  2. int verbose

Input flags:

  1. -a Numbers are sorted in ascending order
  2. -d Numbers are sorted in descending order
  3. -u n,o When paired with [a/d] determines number of pairs out of order, and distance of entity with which to swap [if o=0 then random]
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

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 ( struct strElement 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 string based upon ELEMENT_SIZE.


Variable Documentation

struct strElement* strings

information stored in memory.

Algorithm Development Kit 1.0