[erkant]

I need to use counters to check how many steps of outer and inner loop I need to sort some array in selection sort and bubble sort. I have the following code, but it simply doesn't give the correct results. If someone can help me I would be glad.

#include <stdio.h>

void swap(int *number1, int *number2)
{
    int temp;

    temp = *number1;
    *number1 = *number2;
    *number2 = temp;
}

void selectionSort(int array[], int outer_counter, int inner_counter, int len)
{
    int i, j, min;
    outer_counter = 0;
    inner_counter = 0;

    for(i = 0; i < len; i++)
    {
        outer_counter++;
        min = 1;

        for(j = i+1; j < len; j++)
        {
            inner_counter++;
            if(array[j] < array[min])
                min = j;
        }

        swap(&array[i], &array[min]);
    }

    printf("For the outer loop we need: %d steps.\n", outer_counter);
    printf("For the inner loop we need: %d steps.\n", inner_counter);
}

void bubbleSort(int array[], int outer_counter, int inner_counter, int len)
{
    int i, j;
    outer_counter = 0;
    inner_counter = 0;

    for(i = len - 1; i >= 0; i--)
    {
        outer_counter++;

        for(j = 1; j <= i; j++)
        {
            inner_counter++;

            if(array[j-1] > array[j])
                swap(&array[j-1], &array[j]);
        }
    }

    printf("For the outer loop we need: %d steps.\n", outer_counter);
    printf("For the inner loop we need: %d steps.\n\n", inner_counter);
}


int main()
{
    int test1[11] = {45, 18, 0, 500, 486, 212, 318, 1000, 1008, 1, 4};
    int test2[9] = {800, 3, 200, 22, 66, 23, 32, 10, 9};
    int test3[6] = {33, 334, 3, 3334, 333, 33334};
    int outer_counter, inner_counter;

    printf("In selection sort for the first array: \n");
    selectionSort(test1, outer_counter, inner_counter, 11);
    printf("In bubble sort for the the first array: \n");
    bubbleSort(test1, outer_counter, inner_counter, 11);

    printf("In selection sort for the second array: \n");
    selectionSort(test2, outer_counter, inner_counter, 9);
    printf("In bubble sort for the second array: \n");
    bubbleSort(test2, outer_counter, inner_counter, 9);

    printf("In selection sort for the third array: \n");
    selectionSort(test3, outer_counter, inner_counter, 6);
    printf("Ina bubble sort for the third array: \n");
    bubbleSort(test3, outer_counter, inner_counter, 6);

    return 0;

}

This post has been edited by erkant: 29 March 2012 - 01:55 PM

[vividexstance]

What are the results?

Just so you know, you can do things like this:

const char* str = "Hello World";
int count = 0;
for(int i = 0; str[i] != '\0'; ++i, ++count)
    ;

Notice how you can put another expression after incrementing 'i' if you use a comma.

[mojo666]

You may want to tell us what you are expecting the program to out put and what it is actually outputting.
I see the following in your selection sort.

//min=1;  should be
min=i

but this mistake doesn't effect your counts. It simply causes errors in sorting.

[erkant]

When I run it, I get for the number of loop runnings. For example if I have 6 numbers, as an outer loop counter I get result 6. For example, in the third test array, outer loop count should be something like 3 or 4, but I get result 6. Because when the whole array is sorted it keeps looping until the conditions are false. So I need something that will help to exit loops when the array will be completely sorted.

By the way, thanks mojo666 for noticing that error.

This post has been edited by erkant: 29 March 2012 - 02:32 PM

[mojo666]

for bubble sort you can add this optimization.

in the outer loop set a boolean variable to true.

in the inner loop, if you swap, set the variable to false.

after the inner loop, if the variable is still true, then nothing swapped which means the array is sorted. Break out of the outer loop.

[erkant]

If I put break in the inner loop, then the outer loop count will still be the number of elements in the array. On the other hand, if I put the break in the outer loop, I always get 1 for the outer loop count. If I put the break both in the inner and outer loop I will get 1 for both counts.

[mojo666]

Can you post the updated code. The break should be in an if-statement in the outer loop.

[erkant]

void bubbleSort(int array[], int len)
{
    int i, j;
    int outer_counter = 0;
    int inner_counter = 0;
    bool check;

    for(i = len - 1; i >= 0; i--)
    {
        check = true;
        outer_counter++;

        for(j = 1; j <= i; j++)
        {
            inner_counter++;

            if(array[j-1] > array[j])
            {
                swap(&array[j-1], &array[j]);
                check = false;
            }
            if(check == true)
                break;
        }
    }

    printf("for the outer loop we need: %d steps,\n", outer_counter);
    printf("for the inner loop we need: %d steps.\n\n", inner_counter);
}

If I write it at the outer loop I will get outer loop count always 1 I think.

This post has been edited by erkant: 29 March 2012 - 03:00 PM

[mojo666]

void bubbleSort(int array[], int len)
{
    int i, j;
    int outer_counter = 0;
    int inner_counter = 0;
    bool check;

    for(i = len - 1; i >= 0; i--)
    {
        check = true;
        outer_counter++;

        for(j = 1; j <= i; j++)
        {
            inner_counter++;

            if(array[j-1] > array[j])
            {
                swap(&array[j-1], &array[j]);
                check = false;
            }
            //if(check == true)
            //    break;
        }
        //should be here
        if(check)
        {break;}
    }

    printf("for the outer loop we need: %d steps,\n", outer_counter);
    printf("for the inner loop we need: %d steps.\n\n", inner_counter);
}

The break needs to be in the outerloop. As we scan through the unsorted part of the array in the inner loop, we are checking if it is sorted. When any swap occurs, that means it is unsorted. The inner loop needs to complete in order to properly check this, so we don't ever want to break the inner loop. Your code quits the moment any consecutive elements are not swapped. So in the array {1, 5, 4, 3, 2} it will never do anything because 1 and 5 are never swapped.