How to count number of swaps in a bubble sort?

Question

So I need my program to print the values entered and count the number of swaps(not comparisons). So far I have everything working except the swap counter. I tried just incrementing by using swap++; in my if statement along with the bubble sort but that doesn't work. Any ideas? Here is my code.

#include <stdio.h>

int sort(int array[], int count);

int main(void) {

    int numArray[100];
    int counter, value;

    printf("Enter array length \n");
    scanf("%d", &counter); 

    int i = 0;
    while(i < counter){
        scanf("%d", &numArray[i]);
        i++;    
    }

    i = 0;
    while(i < counter) {
        sort(numArray, counter);
        i++;
    }

    int totalSwaps = sort(numArray, counter);
    printf("Swaps: %d\n", totalSwaps); 

    i = 0;
    while(i < counter) {
        printf("Values: %d\n", numArray[i]); 
        i++;
    }

    return 0;
}

int sort(int array[], int count) {
    int i, j, temp;
    int swaps = 0;
    for(i = 0; i < count-1; ++i) {
        for(j=0; j < count-1-i; ++j) {
            if(array[j] > array[j+1]) {
                temp = array[j+1];
                array[j+1] = array[j];
                array[j] = temp;
                swaps++;
            }
        }
    }

    return swaps;
}

Solution 1

You have a while loop to sort it count number of times. You only need to run your sort function once, unless it doesn't sort the first time.

#include <stdio.h>

int sort(int array[], int count);

int main(void){

    int numArray[100];
    int counter;

    printf("Enter array length \n");
    scanf("%d", &counter); 

    int i;
    for (i = 0; i < counter; i++){
        printf("%d. Enter a numner: ", i);
        scanf("%d", &numArray[i]);
    }

    // How many times would you like to sort this array?
    // You only need one sort
    /*
    i = 0;
    while(i < counter){
        sort(numArray, counter);
        i++;
    }
    */

    int totalSwaps = sort(numArray, counter);

    if (totalSwaps == 0) {
        printf("The array is already in sorted order\n");
        return 0;
    }

    printf("Swaps: %d\n", totalSwaps); 

    for (i = 0; i < counter; i++) {
        printf("Values: %d\n", numArray[i]); 
    }
    return 0;
}



int sort(int array[], int count){

    int i, j, temp;
    int swaps = 0;
    for(i = 0; i < count-1; ++i){

        for(j=0; j<count-1-i; ++j){

            if(array[j] > array[j+1]){

                temp = array[j+1];
                array[j+1] = array[j];
                array[j] = temp;
                swaps++;
            }
        }
    }

    return swaps;
}

Solution 2

In ascending order:

In Bubble sort, the largest element moves to the right. So swapping is done, when a smaller element is found on the right side.

So to count the number of swaps for an element, just count the number of elements on the right side that are smaller than it.

Comments

[ProfOak]

sort() sorts the array of integers the first time. So you're effectively adding 0 to totalSwaps for counter-1 number of times.

[user4766244]

ok thanks. If i wanted to count the number of time the 'sort' function was called also how would I do that?

[bwegs]

@ProfOak You're absolutely right, I don't know why you would call a sort method in a loop... it's been a long day.

[bwegs]

@Cryptic you only need to call sort() once

[ProfOak]

int totalSwaps = sort(numArray, counter); It's called once :-)

[user4766244]

What I mean is how could I terminate the program if sort is not used? @ProfOak.

[ProfOak]

Why would you want to run a sorting program that doesn't sort?

[user4766244]

@ProfOak. Well I have to use that loop as required by my teacher. So I wrote it like this int totalSwaps = 0; i = 0; while(i < counter){ totalSwaps += sort(numArray, counter); i++; }

[ProfOak]

Please understand that the function sort() sorts an array of integers. If you sort this list 1,2,3,4,5 what do you get? You get the same thing. You need to understand this because the while loop will try to do this 5 times in total. That's like taking 5 showers in a row. You were already clean the first time. Why would you do it 4 more times?

[user4766244]

@ProfOak I understand this, however it is a assignment for my class and it is the requirement to terminate the program if someone enters a already sorted array, also the while loop is required which is stupid but I have to have it.

[ProfOak]

Check if totalSwaps == 0, then print something to say it's already sorted. To exit the main function early, type return 0 where you want it to end. I will update my solution.