Sort and search arrays in C / C++ - PART 1

A few days ago I was speaking with another coder and he asked me about finding array values quickly using c or c++

He followed up with asking if the array values are sorted ascending…….

int a[] = {0, 100, 125, 154, …}

Funnily enough it slipped my mind about partitioning the array, which inspired me to write from scratch a sorting and search algorithm for arrays to help refresh my memory.

As I go through creating the algorithms I will write my articles as I go and will list problems and solutions I run into to see the process I went through.

This will be PART 1, which I will create a very simple sort algorithm. I will be using the c++ std library, but this could be easily swapped out if you want to use plain c.

So… let’s get started!

Let’s create an algorithm to sort an array into ascending order. First I will create a simple console application for testing and pre-name some functions to get an idea of some steps.

// our starting point
int main() {
	// I will declare an initialized array with 15 random integers (with a duplicate also) 
	int a[] = {5, 1, 15, 9872, 42, 2576, 234, 4, 557, 4, 78, 353464, 32534, 47523, 2};

	// I will output to the console just to make it easier to see what is going on
	std::cout << "Unsorted values: " << std::endl;

	// ok… so here I will need a simple procedure to print the values of the array…
	// array_print(…

	// now we will need to actually sort the array :)
	// array_sort(…

	// let’s print it again
	// array_print(…

	// finally, let’s return our exit status (0 = success)
	return 0;
}

Now I have a clear idea in my mind what is needed to begin. First I will create a very simple array_print procedure.

// initially I wrote the procedure with only 1 parameter, the array
// after moving on, I decided the length of the array is better to be passed to save cpu cycles
// since the length would be calculated also in the sorting algorithm
void array_print(int a[], int len) {
	// we run through our array items in increments of 1 … obviously lol
	for (int i = 0; i < len; i++) {
		// then print the value to console, not worried about ending ,
		// it’s just for testing!
		std::cout << a[i] << ", ";
	}

	// finally write the new line
	std::cout << std::endl;
}

Now in our main function below our array declaration I will add code to calculate the length (later this can be used for dynamic size)

// the length of the array is the total items divided by data type size
	int len = sizeof(a) / sizeof(int);

Next up is the sorting algorithm!

void array_sort(int a[], int len) {
    // make sure we have at least 2 items
    if (len < 2) return;

    // let's run through the input array starting from the second item
    for (int i = 1; i < len; i++) {
        // store the value of index "i" for later and so we don't need to keep accessing the array offset
        int value = a[i];
        // j set as the current index and used to go in reverse through the array
        int j = i;

        // while the current index is above the first item and
        // the value of the item before the current index is above our value THEN
        while ((j > 0) && (a[j-1] > value)) {
            // set the value at current index to the previous value
            a[j] = a[j-1];
            // decrement our j index to continue our while condition
            j--;
        }

        // finally set the value of whatever our current index is to the saved value earlier
        a[j] = value;
    }
}

My first thought was to sort through the items in order but reverse sort when the previous value is higher. Ideally this is not great because it is continuously looping through the array potentially every next item…. This will be very inefficient, but so far it works.

I decided I will give it a quick test for performance. Let’s update the main function to include time.h and use clock() function to make some very simple timing.

int main() {
	int a[] = {5, 1, 15, 9872, 42, 2576, 234, 4, 557, 4, 78, 353464, 32534, 47523, 2};
	int len = sizeof(a) / sizeof(int);

	std::cout << "Unsorted: " << std::endl;
	array_print(a, len);

	// get start tick
	int start_tick = clock();
	array_sort(a, len);
	// and end tick
	int end_tick = clock();
	// now we can output the difference to get total tick count
	std::cout << "Sort took " << ((float)end_tick - start_tick) << std::endl;
	array_print(a, len);

	return 0;
}

Now this is useless because the array is TINY! Let’s add a function to fill the array with random integers.

void array_fillrand(int a[], int len) {
    // I opted to use a static seed (my birth year!) so the random numbers will be the same each time….
    srand(1987);

    // generate random numbers
    for (int i = 0; i < len; i++) {
        a[i] = rand();
    }
}

Now to update the main function again to create the array

int main() {
    // a constant number we can change easily, how large the array will be.
    const int ARRAY_SIZE = 50000;

    // declare our array
    int a[ARRAY_SIZE];

    // call our fill function
    array_fillrand(a, ARRAY_SIZE);

    // this is useless as we know the size already, but I want to keep it as in another
    // article we may go into sorting dynamic sized arrays
    int len = sizeof(a) / sizeof(int);

    // printing this amount of numbers is crazy, we will modify our print function to print
    // only the first 15 numbers so we can see a snapshot of it working...
    std::cout << "Unsorted: " << std::endl;
    array_print(a, len);

	// get start tick
	int start_tick = clock();

	// sort the array
	array_sort(a, len);

	// get end tick
	int end_tick = clock();

	// output the difference to get total tick count, but we will convert to seconds
	std::cout << "Sort took " << ((float)end_tick - start_tick) / CLOCKS_PER_SEC << " seconds" << std::endl;

	// print sorted array
	array_print(a, len);

    return 0;
}

I also updated the array print to print a max of 15 items

void array_print(int a[], int len) {
	// we have modified this to show a max of 15 items
    for (int i = 0; i < ((len > 15) ? 15 : len); i++) {
        std::cout << a[i] << ", ";
    }
    std::cout << std::endl;
}

Great! - everything works as planned, 50,000 items sorted with an average of 1.12 seconds give or take. This is crazy long, especially if it needs to be called multiple times.



The full code for PART 1:

#include <iostream>
#include <time.h>


//
// procedure to sort the array
//
void array_sort(int a[], int len) {
    // make sure we have at least 2 items
    if (len < 2) return;

    // let's run through the input array starting from the second item
    for (int i = 1; i < len; i++) {
        // store the value of index "i" for later and so we don't need to keep accessing the array offset
        int value = a[i];
        // j set as the current index and used to go in reverse through the array
        int j = i;

        // while the current index is above the first item and
        // the value of the item before the current index is above our value THEN
        while ((j > 0) && (a[j-1] > value)) {
            // set the value at current index to the previous value
            a[j] = a[j-1];
            // decrement our j index to continue our while condition
            j--;
        }

        // finally set the value of whatever our current index is to the saved value earlier
        a[j] = value;
    }
}


//
// print array values
//
void array_print(int a[], int len) {
    // we have modified this to show a max of 15 items
    for (int i = 0; i < ((len > 15) ? 15 : len); i++) {
        std::cout << a[i] << ", ";
    }
    std::cout << std::endl;
}



//
// fill an array with random integers
//
void array_fillrand(int a[], int len) {
    // Set random seed based on current time
    srand(1987);

    // generate random numbers
    for (int i = 0; i < len; i++) {
        a[i] = rand();
    }
}


//
// our starting point
//
int main() {
    // a constant number we can change easily, how large the array will be.
    const int ARRAY_SIZE = 50000;

    // declare our array
    int a[ARRAY_SIZE];

    // call our fill function
    array_fillrand(a, ARRAY_SIZE);

    // this is useless as we know the size already, but I want to keep it as in another
    // article we may go into sorting dynamic sized arrays
    int len = sizeof(a) / sizeof(int);

    // printing this amount of numbers is crazy, we will modify our print function to print
    // only the first 15 numbers so we can see a snapshot of it working...
    std::cout << "Unsorted: " << std::endl;
    array_print(a, len);

	// get start tick
	int start_tick = clock();

	// sort the array
	array_sort(a, len);

	// get end tick
	int end_tick = clock();

	// output the difference to get total tick count, but we will convert to seconds
	std::cout << "Sort took " << ((float)end_tick - start_tick) / CLOCKS_PER_SEC << " seconds" << std::endl;

	// print sorted array
	array_print(a, len);

    return 0;
}

I will follow up with faster methods for PART 2 for sorting arrays; such as partitioning.

I hope you find this process interesting. Until next time!

/Signing off