From f4c27a37d82dd9b481081ac6b0b599555341f3d7 Mon Sep 17 00:00:00 2001 From: "W. Trevor King" Date: Sun, 24 Oct 2010 14:03:23 -0400 Subject: [PATCH] Minor style cleanups to src/sorting. Also ran through `indent --linux *.[hc]`. --- src/sorting/Makefile | 2 +- src/sorting/README | 2 +- src/sorting/bubble.c | 34 +++---- src/sorting/main.c | 160 ++++++++++++++++----------------- src/sorting/quicksort.c | 71 +++++++-------- src/sorting/{main.h => sort.h} | 5 ++ 6 files changed, 137 insertions(+), 137 deletions(-) rename src/sorting/{main.h => sort.h} (64%) diff --git a/src/sorting/Makefile b/src/sorting/Makefile index ec89dfe..c85a83c 100644 --- a/src/sorting/Makefile +++ b/src/sorting/Makefile @@ -24,7 +24,7 @@ clean: data : data.py ./$< $(DATA_SIZE) > $@ -$(EXECS:%=%.o) main.o : %.o : %.c main.h +$(EXECS:%=%.o) main.o : %.o : %.c sort.h $(CC) -c $(CFLAGS) -o $@ $< $(EXECS) : % : main.o %.o diff --git a/src/sorting/README b/src/sorting/README index 9506a9d..4f619ff 100644 --- a/src/sorting/README +++ b/src/sorting/README @@ -35,7 +35,7 @@ Timing Timing 8191 data points on my 571 MHz netbook with - $ time ./quicksort data > /dev/null + $ time ./bubble data > /dev/null $ time ./quicksort data > /dev/null quicksort takes 0.075 s and bubble takes 3.994s. diff --git a/src/sorting/bubble.c b/src/sorting/bubble.c index d747d63..8b7358c 100644 --- a/src/sorting/bubble.c +++ b/src/sorting/bubble.c @@ -2,27 +2,27 @@ /* Michel Vallieres, 2009 */ -#include "main.h" +#include "sort.h" +void swap(double *x, double *y) +{ + double temp; + temp = *x; + *x = *y; + *y = temp; +} void sort(int list_size, double *list) { - double temp; - int i, exchange; + int i, exchange = 1; - exchange = 1; - while( exchange != 0 ) - { - exchange = 0; - for( i=0; i list[i+1] ) - { - temp = list[i]; - list[i] = list[i+1]; - list[i+1] = temp; - exchange++; - } + while (exchange != 0) { + exchange = 0; + for (i = 0; i < list_size - 1; i++) { + if (list[i] > list[i + 1]) { + swap(&list[i], &list[i + 1]); + exchange++; + } + } } - } } diff --git a/src/sorting/main.c b/src/sorting/main.c index 65d00d9..7eb791d 100644 --- a/src/sorting/main.c +++ b/src/sorting/main.c @@ -6,99 +6,93 @@ #include #include -#include "main.h" +#include "sort.h" - -void printlist(FILE *stream, int list_size, double *list, int num_shown) +void printlist(FILE * stream, int list_size, double *list, int num_shown) { - int i; - for(i=0; i < num_shown; i++) - fprintf(stream, "%f\t", list[i]); - fprintf(stream, "\n"); - for(i=num_shown; i > 0 ; i--) - fprintf(stream, "%f\t", list[list_size-i]); - fprintf(stream, "\n"); + int i; + for (i = 0; i < num_shown; i++) + fprintf(stream, "%f\t", list[i]); + fprintf(stream, "\n"); + for (i = num_shown; i > 0; i--) + fprintf(stream, "%f\t", list[list_size - i]); + fprintf(stream, "\n"); } double checklist(int list_size, double *list) { - int i; - double sum; + int i; + double sum; - sum = 0.0; - for(i = 0; i < list_size; i++ ) - sum = sum + list[i]; - return sum; + sum = 0.0; + for (i = 0; i < list_size; i++) + sum = sum + list[i]; + return sum; } -int read_data(const char *file_name, int *pList_size, double **pList) { - FILE *fp; - int i; - double x; - - // open the file - if ((fp = fopen(file_name, "r")) == NULL) - { - fprintf(stderr, "error in opening data file %s\n", file_name); - return EXIT_FAILURE; - } - - // read the size of the data file - fscanf(fp, "# %d", pList_size); - - // allocate memory for the data - *pList = (double *)malloc(sizeof(double)* *pList_size); - if (*pList == NULL) - { - fprintf(stderr, "could not allocate %d bytes\n", - sizeof(double)* *pList_size); - return EXIT_FAILURE; - } - - // read in the data - fprintf(stderr, "reading %d points\n", *pList_size); - for (i=0; i < *pList_size ; i++) - { - fscanf(fp, "%lf", &x); - (*pList)[i] = x; - } - - // close the file - fclose(fp); - return EXIT_SUCCESS; +int read_data(const char *file_name, int *pList_size, double **pList) +{ + FILE *fp; + int i; + double x; + + // open the file + if ((fp = fopen(file_name, "r")) == NULL) { + fprintf(stderr, "error in opening data file %s\n", file_name); + return EXIT_FAILURE; + } + // read the size of the data file + fscanf(fp, "# %d", pList_size); + + // allocate memory for the data + *pList = (double *)malloc(sizeof(double) * *pList_size); + if (*pList == NULL) { + fprintf(stderr, "could not allocate %d bytes\n", + sizeof(double) * *pList_size); + return EXIT_FAILURE; + } + // read in the data + fprintf(stderr, "reading %d points\n", *pList_size); + for (i = 0; i < *pList_size; i++) { + fscanf(fp, "%lf", &x); + (*pList)[i] = x; + } + + // close the file + fclose(fp); + return EXIT_SUCCESS; } - -int main ( int argc, char *argv[] ) +int main(int argc, char *argv[]) { - int list_size, i; - double *list; - char *file_name = "data"; - - // parse arguments - if (argc > 1) - file_name = argv[1]; - - // setup - if (read_data(file_name, &list_size, &list) != EXIT_SUCCESS) - return EXIT_FAILURE; - - /* print initial list */ - fprintf(stderr, "The list before sorting is:\n"); - printlist(stderr, list_size, list, 3); - fprintf(stderr, "Check: sum of %d elements = %f\n", - list_size, checklist(list_size, list)); - - /* sort the list */ - sort(list_size, list); - - /* print final list */ - fprintf(stderr, "The list after sorting is:\n"); - printlist(stderr, list_size, list, 3); - fprintf(stderr, "Check: sum of %d elements = %f\n", - list_size, checklist(list_size, list)); - for (i=0; i < list_size; i++) - printf("%f\n", list[i]); - - return EXIT_SUCCESS; + int list_size, i; + double *list; + char *file_name = "data"; + + // parse arguments + if (argc > 1) + file_name = argv[1]; + + // setup + if (read_data(file_name, &list_size, &list) != EXIT_SUCCESS) + return EXIT_FAILURE; + + /* print initial list */ + fprintf(stderr, "The list before sorting is:\n"); + printlist(stderr, list_size, list, 3); + fprintf(stderr, "Check: sum of %d elements = %f\n", + list_size, checklist(list_size, list)); + + /* sort the list */ + sort(list_size, list); + + /* print final list */ + fprintf(stderr, "The list after sorting is:\n"); + printlist(stderr, list_size, list, 3); + fprintf(stderr, "Check: sum of %d elements = %g\n", + list_size, checklist(list_size, list)); + for (i = 0; i < list_size; i++) + printf("%g\n", list[i]); + + return EXIT_SUCCESS; } diff --git a/src/sorting/quicksort.c b/src/sorting/quicksort.c index 927c43a..0d82e07 100644 --- a/src/sorting/quicksort.c +++ b/src/sorting/quicksort.c @@ -4,53 +4,54 @@ * * ref: http://cprogramminglanguage.net/quicksort-algorithm-c-source-code.aspx * Numerical Recipes - */ + */ void swap(double *x, double *y) { - double temp; - temp = *x; - *x = *y; - *y = temp; + double temp; + temp = *x; + *x = *y; + *y = temp; } -int choose_pivot(int i,int j ) +int choose_pivot(int i, int j) { - return((i+j) /2); + return ((i + j) / 2); } -void quicksort( double list[], int m, int n ) +/* sort the list from list[m] to list[n] */ +void quicksort(double list[], int m, int n) { - int i,j,k; - double key; - - if( m < n) - { - k = choose_pivot(m,n); - swap(&list[m],&list[k]); - key = list[m]; - i = m+1; - - j = n; - while(i <= j) - { - while((i <= n) && (list[i] <= key)) - i++; - while((j >= m) && (list[j] > key)) - j--; - if( i < j) - swap(&list[i],&list[j]); + int i, j, k; + double key; + + if (m < n) { + k = choose_pivot(m, n); + swap(&list[m], &list[k]); + key = list[m]; + + i = m + 1; + j = n; + while (1) { + while ((i <= n) && (list[i] <= key)) + i++; + while ((j >= m) && (list[j] > key)) + j--; + if (i >= j) + break; + swap(&list[i], &list[j]); + } + + // put the pivot back in + swap(&list[m], &list[j]); + + // recursively sort the lesser lists + quicksort(list, m, j - 1); + quicksort(list, j + 1, n); } - // swap two elements - swap(&list[m],&list[j]); - - // recursively sort the lesser list - quicksort(list,m,j-1); - quicksort(list,j+1,n); - } } void sort(int list_size, double *list) { - quicksort(list, 0, list_size-1); + quicksort(list, 0, list_size - 1); } diff --git a/src/sorting/main.h b/src/sorting/sort.h similarity index 64% rename from src/sorting/main.h rename to src/sorting/sort.h index 0b43b5e..9418b4a 100644 --- a/src/sorting/main.h +++ b/src/sorting/sort.h @@ -1,2 +1,7 @@ +#ifndef sort_h +#define sort_h + /* sort a list `list` of `list_size` elements in place. */ void sort(int list_size, double *list); + +#endif /* sort_h */ -- 2.26.2