Efficient Bubble Sort in C?-CodePudding

I'm currently working on a college project to practice pointers and array modification. To get a complete 4.0 on the project, I need to tweak my bubble sort code to be efficient. In other terms, I need the function to stop running through sorting iterations after the array is successfully in order. To be honest, I'm beat. I need any and all suggestions on how I could achieve this.

My code is below:

int bubbleSortAscend(int *ary, int i, int l) {
    for (i = 0; i < l; i  ) {
        if (*(ary   i) > *(ary   (i   1))) {
            int temp = *(ary   (i   1));
            *(ary   (i   1)) = *(ary   i);
            *(ary   i) = temp;
        }
    }
}

Thank you in advance!

CodePudding user response：

Got it! Thank you to ShadowRanger for the suggestion. I took his idea and spun it. Code below. Started with a Boolean set to false and if no more sorting could be done, the loop will break then print. I'm sure there's a more compact way to do it than how I did (I'm a C noob.) But here's the idea behind it :P

EDIT: THIS WAS PREVIOUSLY INCORRECT. NEW CODE:

int bubbleSortAscend(int *ary, int i, int l){
    char sorted = false;

    l -= 1;
    while(sorted == false) {
      sorted = true;
      for (i = 0; i < l; i  ) {
        if(*(ary i) > *(ary (i 1))) {
          int temp = *(ary (i 1));
          *(ary (i 1)) = *(ary i);
          *(ary i) = temp;
          sorted = false;
          }
        }
      }
    printf("Your sorted array is: ");
    for(i = 0; i < (l   1); i  )
      printf("%d ", *(ary i));
    printf("\n");

Changing the value of sorted to true now occurs outside the for loop instead of in an else statement. Thank you again to everyone for help.

CodePudding user response：

Your code does not implement bubble sort because you only perform a single pass on the array. Furthermore, you access the element beyond the end of the array and the second argument is not not needed.

Here is a modified version that is efficient^(*) as it stops as soon as the array is sorted:

int bubbleSortAscend(int *ary, int n) {
    for (;;) {
        int sorted = 1;
        for (int i = 0; i < n - 1; i  ) {
            if (*(ary   i) > *(ary   (i   1))) {
                int temp = *(ary   (i   1));
                *(ary   (i   1)) = *(ary   i);
                *(ary   i) = temp;
                sorted = 0;
            }
        }
        if (sorted)
            return;
    }
}

Unless you are required to use the pointer syntax, the code would be much readable this way:

int bubbleSortAscend(int *ary, int n) {
    for (;;) {
        int sorted = 1;
        for (int i = 0; i < n - 1; i  ) {
            if (ary[i] > ary[i   1]) {
                int temp = ary[i];
                ary[i] = ary[i   1];
                ary[i   1] = temp;
                sorted = 0;
            }
        }
        if (sorted)
            return;
    }
}

^{(*) efficient bubble sort is an awfully good CS oxymoron. Bubble sort has an average time complexity of O(n²), so it is not efficient, but good implementations have linear complexity on sorted lists: much better than standard mergesort and quicksort. As a matter of fact, simplistic implementations of quicksort have quadratic complexity for sorted lists}