c_project/mysort.c

/*
Copyright (c) 2013, Lily Carpenter
All rights reserved.

Redistribution and use in source and binary forms, with or without modification,
are permitted provided that the following conditions are met:

  Redistributions of source code must retain the above copyright notice, this
  list of conditions and the following disclaimer.

  Redistributions in binary form must reproduce the above copyright notice, this
  list of conditions and the following disclaimer in the documentation and/or
  other materials provided with the distribution.

  Neither the name of Lily Carpenter nor the names of its
  contributors may be used to endorse or promote products derived from
  this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <fcntl.h>

// Resizes array a using realloc
unsigned int *resize_array(unsigned int *a, size_t new_size)
{
    unsigned int *save;
    save = realloc(a, new_size);

    if (save == NULL) {
        fprintf(stderr, "Realloc failed, cannot resize array.\n");
        exit(EXIT_FAILURE);
    }

    return save;
}

// Swaps the values of a and b
void swap(unsigned int *a, unsigned int *b){
    unsigned int old_a = *a;
    *a = *b;
    *b = old_a;
}

// Creates a partition for use by quicksort
int partition(unsigned int *array, int left, int right, int pivot){
    unsigned int pivot_value = array[pivot];
    swap(&array[pivot], &array[right]);
    int storeIndex = left;
    for(int i = left; i < right; i++){
        if (array[i] < pivot_value){
            swap(&array[i], &array[storeIndex]);
            storeIndex++;
        }
    }

    swap(&array[storeIndex], &array[right]);

    return storeIndex;
}

// Using partition to sort `array`
void quicksort(unsigned int *array, int left, int right){
    if (left < right){
        int pivot = right;

        pivot = partition(array, left, right, pivot);
        quicksort(array, left, pivot - 1);
        quicksort(array, pivot + 1, right);
    }
}

int main()
{
    const int temp_size = 50; // How many numbers to load at once?
    int size = 1;

    // Holds all numbers we need to sort
    unsigned int *numbers = malloc(size * sizeof *numbers);

    // Holds the numbers recently pulled from the stream
    unsigned int *temp = malloc(temp_size * sizeof *temp);

    int ret_val; // Holds the return value of fread so we know how many numbers were read

    /// Loop through stdin stream grabbing `temp_size` numbers each iteration
    while ((ret_val = fread(temp, sizeof *temp, temp_size, stdin))){
        // Should not happen if EOF has been reached/we have loaded all data
        if (ret_val != 0){

            // This looks complicated, just the math required to figure the new size of `numbers`
            int new_size = size - 1 + ret_val;

            // Actually resize array
            numbers = resize_array(numbers, new_size * sizeof *numbers);

            // Go from size to new_size, putting the numbers from `temp` into `numbers`
            int temp_count = 0;
            for(int i = size - 1; i < new_size; i++){
                numbers[i] = temp[temp_count++];
            }

            // Update `size`, now that we are done with it's previous value
            size = new_size;
        }
    }


    quicksort(numbers, 0, size - 1);

    for (int i = 0; i < size; i++){
        printf("%u\n", numbers[i]);
    }

    free(temp);
    free(numbers);
    return 0;
}