Thread: playing with bubble sort optermisation

just for some light entertainment after the trauma of linked lists i decided to play around with the basic bubble sort and see if i could make it better.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

void printdata(int x, int data[]);
int basicsort(int x, int data[]);
int middlesort(int x, int data[]);
int firstoptimumsort(int x, int data[]);
int secondoptimumsort(int x, int data[]);

int main()
{
    int data[] = {5, 8, 12, -6, 98, 56, -19, 4, 17, 18, 3, -2, 7, 10, -5, 22, 1, 27, 25, 30};
    int num_data_items = 20, count;

    printf("Original order of data items:\n");
    printdata(num_data_items, data);
    count = firstoptimumsort(num_data_items, data);
    printf("\nData items in ascending order:\n");
    printdata(num_data_items, data);
    printf("\ncount is %d\n", count);
    return 0;
}

void printdata(int x, int data[])
{
    int i;

    for (i = 0; i < x; i++)
    {
       printf("%d ", data[ i ]);
    }
}

int basicsort(int x, int data[])
{
    int pass, i, temp, count_inner = 0, count_outter = 0;

    for (pass = 0; pass < x - 1; pass++)
    {
        for (i = 0; i < x - 1; i++)
        {
            if (data[ i ] > data[ i + 1])
            {
            temp = data[ i ];
            data[ i ] = data[ i + 1 ];
                data[ i + 1 ] = temp;
            }
            count_inner++;
        }
        count_outter++;
        printf("\nafter %d pass(s) ", count_outter);
        printdata(x, data);
    }
    return count_inner;
}

int middlesort(int x, int data[])
{
    // added in a sorted flag to limit it trys to sort a sorted array

    int pass, i, temp, count_inner = 0, count_outter = 0;
    bool data_swapped;

    for (pass = 0; pass < x - 1; pass++)
    {
        data_swapped = false;
        for (i = 0; i < x - 1; i++)
        {
            if (data[ i ] > data[ i + 1])
            {
                temp = data[ i ];
                data[ i ] = data[ i + 1 ];
                data[ i + 1 ] = temp;
                data_swapped = true;
            }
            count_inner++;
        }
        count_outter++;
        printf("\nafter %d pass(s) ", count_outter);
        printdata(x, data);
        if (!data_swapped)
        {
            break;
        }
    }
    return count_inner;
}

int firstoptimumsort(int x, int data[])
{
    //subtract the value of pass from the second loop

    int pass, i, temp, count_inner = 0, count_outter = 0;
    bool data_swapped;

    for (pass = 0; pass < x - 1; pass++)
    {
        data_swapped = false;
        for (i = 0; i < x - pass - 1; i++)
        {
            if (data[ i ] > data[ i + 1])
            {
                temp = data[ i ];
                data[ i ] = data[ i + 1 ];
                data[ i + 1 ] = temp;
                data_swapped = true;
            }
            count_inner++;
        }
        count_outter++;
        printf("\nafter %d pass(s) ", count_outter);
        printdata(x, data);
        if (!data_swapped)
        {
            break;
        }
    }
    return count_inner;
}

int secondoptimumsort(int x, int data[])
{
    //substitute the index of the last number swapped for x - pass - 1 in the second loop

    int pass, i, temp, count_inner = 0, count_outter = 0, index_num_swapped = x - 1, tmp_index;
    bool data_swapped;

    for (pass = 0; pass < x - 1; pass++)
    {
        data_swapped = false;
        for (i = 0; i < index_num_swapped; i++)
        {
            if (data[ i ] > data[ i + 1])
            {
                temp = data[ i ];
                data[ i ] = data[ i + 1 ];
                data[ i + 1 ] = temp;
                data_swapped = true;
                tmp_index = i;
            }
            count_inner++;
        }
        index_num_swapped = tmp_index;
        count_outter++;
        printf("\nafter %d pass(s) ", count_outter);
        printdata(x, data);
        if (!data_swapped)
        {
            break;
        }
    }
    return count_inner;
}

the basic one took 361 goes middle took 247 firstoptimum took 169 and second one took 141.

it would be interesting to see what sort of time difference that would make in real life. is there away of using the time function and doing a sort finished time - sort started time?

coop

Originally Posted by cooper1200

is there away of using the time function and doing a sort finished time - sort started time?

Make three separate programs, one each method. They must sort a random array of a 1,000 numbers. Then run `time ./program1`, `time ./program2` and `time ./program3` and compare how long they take.

ok cool thanks

dumb question does the array have to be completely random or can i just copy the original one 50 times

@cooper1200, not really so dumb a question really.

Some sort algorithms do poorly based on how well the list is already sorted (and some do better when it is). As a result, when you compare different algorithms you should consider providing the same data to each one, but then run through different data in multiple tests with that point in mind.

i kept getting different results but broadly there doesn't seem to be any difference in measurable time between firstoptimum and second optimum despite it taking 3429 goes less. over all though i seem to have saved 3 milliseconds on a 1000 element array with the same 20 numbers above 50 times.

i made a program to randomly fill a array with 1000 elements and then randomly swapped the elements around

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void initalizearray(const int x, int data[]);
void printarray(const int x, const int data[]);
void randomizearray(const int x, int data[]);

int main()
{
    int data[1000], num_elements = 1000;

    srand(time(NULL));
    initalizearray(num_elements, data);
    printarray(num_elements, data);
    randomizearray(num_elements, data);
    printf("\nprinting array 2nd time\n");
    printarray(num_elements, data);

    return 0;
}

void initalizearray(const int x, int data[])
{
    int i, rand_num;

    for (i = 0; i < x; i++)
    {
        rand_num = rand() % 9 + 1;
        data[i] = (i + 1) * rand_num;
    }
}
void printarray(const int x, const int data[])
{
    int i, j = 0;

    for (i = 0; i < x; i++)
    {
        if (j == 10)
        {
            printf("\n");
            j = 0;
        }
        printf("%d, ", data[i]);
        j++;
    }
}
void randomizearray(const int x, int data[])
{
    int i, rand_num, tmp_num;

    for (i = 0; i < x; i++)
    {
        rand_num = rand() % x;
        if (i == rand_num)
        {
            while (i == rand_num)
            {
                rand_num = rand() % x;
            }
        }
        tmp_num = data[i];
        data[i] = data[rand_num];
        data[rand_num] = tmp_num;
    }
}

i made it squirt the output into a file using the >> operator in the console and copied the result into the bubble sorts but didn't seem to make much difference

any suggestions on getting a more random list
coop

Try a larger array, say 1000000 elements (and randomize it with larger numbers than between 1 and 10). 1000 elements is relatively tiny on a modern computer.

Also, is it necessary to randomize the array after it's initialized with random numbers (or, on the other hand, is it necessary to initialize the array with random numbers before it's randomized)?

any suggestions on getting a more random list

Check into the C++ standard library <random>. There you have various generators, distributions and such which deal with randomness concepts beyond the old rand().

If that isn't quite enough, perhaps you'll find a bit more in Boost's support for random number generation.

Originally Posted by Niccolo

Check into the C++ standard library <random>. There you have various generators, distributions and such which deal with randomness concepts beyond the old rand().

If that isn't quite enough, perhaps you'll find a bit more in Boost's support for random number generation.

Let's not forget that we are on a C forum, not C++ :P

Originally Posted by Click_here

Let's not forget that we are on a C forum, not C++ :P

will they not work on c then???
coop