Bubble Sort assignment

[rgrwatson85]

I have to write a program that sorts an array using bubble sort. I have two things that I would like to do to my code:

1. Optimize it so that if the array is already in order it will recognize it and will not run n-1 passes.

2. I want it to display the number of passes it took to sort.

I have searched around google and read something about putting a flag in the code to let it know that it is done, but I think it had a break statement in the which we are not allowed to use. Here is my bubble sort function.

void bubble_Sort(int sort_Array[], int array_Size)
{
   int pass_Number=1;
   while (pass_Number<=array_Size-1)
   {
      int number_Compared=0;
      int end_Array= array_Size-1-pass_Number;
      while (number_Compared<=end_Array)
      {
         if (sort_Array[number_Compared]>sort_Array[number_Compared+1])
         {
            int temp=sort_Array[number_Compared];
            sort_Array[number_Compared]=sort_Array[number_Compared+1];
            sort_Array[number_Compared+1]=temp;
         }
         number_Compared++;
      }
      pass_Number++;
   }
   printf ("\n");
   printf ("This process took %d pass(es).", pass_Number);
}

[anduril462]

1. Optimize it so that if the array is already in order it will recognize it and will not run n-1 passes.

This is referred to as a "smart" bubble sort. All you need to do is track whether you swapped any data. If you made it to the end of the list without swapping, everything is in order. Just make sure you quit your outer loop if you've processed the whole array, or if your swap flag is false (no swaps performed).

2. I want it to display the number of passes it took to sort.

You already try to do this, but it wont work right until you make your bubble sort smart.

[Envynness]

I think this is what you search : in the attachement.

[rgrwatson85]

Here is my updated function. I think it is right.

void bubble_Sort(int sort_Array[], int array_Size)
{
   int pass_Number=1;
   bool swap_Flag= true;
   
   while (pass_Number<=array_Size-1 && swap_Flag)
   {
      int number_Compared=0;
      int end_Array= array_Size-1-pass_Number;
      swap_Flag=false;
      
      while (number_Compared<=end_Array)
      {
         if (sort_Array[number_Compared]>sort_Array[number_Compared+1])
         {
            int temp=sort_Array[number_Compared];
            sort_Array[number_Compared]=sort_Array[number_Compared+1];
            sort_Array[number_Compared+1]=temp;
            swap_Flag= true;
         }
         
         number_Compared++;
      }
      pass_Number++;
   }
   printf ("\n");
   printf ("This process took %d pass(es).", pass_Number);
}

[anduril462]

Well, I think it's only mostly right. Actually I know it's only mostly right, because I tested it. Once you're done coding (or think you're done), you need to test it and see if it behaves as you would expect. Write a simple print function, then print the array out on each pass through your outer loop. Then, run the program several times, with different test data. Make sure it only runs through once, and doesn't swap if the array is already sorted. Make sure your pass count is correct. Test it with presorted, reversed and unsorted data, a single element array, and negative numbers. I did all of that in about 5 minutes, so it shouldn't take you too much longer.

[stahta01]

A single test case that I did not see in anduril462 list is a array filled with the same value. Tim S.

[rgrwatson85]

Ok I updated the code again, and included a function that is part of the larger program. I tested everything you guys suggested and it worked beautifully...until i tested random numbers that don't include 1. I used this as initial array [3,5,2,4,6] and got this as output:

Unsorted array |3| |5| |2| |4| |6|

Pass number 1 rendered |3| |2| |4| |5| |6|
Pass number 2 rendered |2| |3| |4| |5| |6|
The final pass rendered |2| |3| |4| |5| |6|
This process took 3 pass(es).

I can't think of where to begin to troubleshoot. Any ideas as to where the problem is at?

void bubble_Sort(int sort_Array[], int array_Size)
{
   int pass_Number=1; //initial pass must be 1
   bool swap_Flag; //used to stop function early if array is already sorted
  
   while (pass_Number<=array_Size-1 && swap_Flag) //checks that the number of passes doesn't exceed array size 
   {                                              //and if the swap flag was triggered
      printf ("\n");
      if (pass_Number>1) //if loop used to keep the original array from duplicating on screen
      {
      printf ("Pass number %d rendered ", pass_Number-1); 
      
      int i=0;
      while (i<array_Size) //outputs each bubble sort pass for debugging
      {
         printf ("|%d| ", sort_Array[i]);
         i++;
      }
      }
      
      int number_Compared=0; //index number of array
      int end_Array= array_Size-1-pass_Number; //each pass through sorting, the number of array indexes checked gets smaller by
      swap_Flag=false;                         //pass_Number.
      pass_Number++;
      
      while (number_Compared<=end_Array) //checks that index number is not bigger than the adjusted array size.
      {
         if (sort_Array[number_Compared]>sort_Array[number_Compared+1]) //if array[n] is greater than array[n+1] then they swap.
         {
            int temp=sort_Array[number_Compared];
            sort_Array[number_Compared]=sort_Array[number_Compared+1];
            sort_Array[number_Compared+1]=temp;
            swap_Flag= true; //changes swap_Flag to true so that the outer loop can repeat.
         }
         number_Compared++;
      }
   }
   printf ("\n");
   printf ("The final pass rendered ");
   output_Array (sort_Array, array_Size);
   printf ("\n");
   printf ("This process took %d pass(es).", pass_Number-1);
}

void output_Array(int array[], int array_Size) //function outputs the unsorted and sorted array
{
   int i=0;
   
   while (i<array_Size)
   {
      printf ("|%d| ", array[i]);
      i++;
   }
}

[rgrwatson85]

I take back my last post. I just tested a random series including one and it did the same thing. Sometimes it works right and sometimes it doesn't.

[anduril462]

You need to give us the exact test data for a working condition and a non-working condition. Your main function and input gathering code would be helpful too.

[cas]

You have to initialize swap_Flag.

[rgrwatson85]

I got it figured out guys. Thanks for not handing me an answer, but pointing me in the right direction. I sat down and really thought about the logic involved in the problem and had quite a few "duh" moments. It seems to be working properly now. I'll post the source code and you guys can pick it apart and tell me how to make it better.

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

int bubble_Sort(int sort_Array[], int array_Size);
void output_Array(int a[], int array_Size);

int main()
{
    printf ("This program will ask the user to pick a size for an array. It will then\n");
    printf ("auto-populate the array with numbers between 0-50. Finally it will sort the\n");
    printf ("array in increasing order and state the number of passes the sorting algorithm\n");
    printf ("took.\n");
    printf ("\n");
    printf ("To manually input array numbers simply uncomment lines 30 & 31 and\n");
    printf ("comment line 32 of the source code.\n");
    printf ("\n");
    system ("pause");
    system ("cls");
    
    int i=0;
    int n;
    printf ("Input the size of the array: ");
    scanf ("%d", &n); //user defines size of array
    int a[n];
    while (i<n)
    {
       //printf ("Input value for a[%d]: ", i);
       //scanf ("%d", &a[i]); // user inputs n variables
       a[i]=rand()%50; //auto-populates array for ease of program use
       i++;
    }
    printf ("\n");
    printf ("\n");
    
    system("pause");
    system ("cls");
    
    printf ("User input array: ");
    
    output_Array(a, n); //outputs unsorted list
    
    bubble_Sort(a, n); //sorts the array

    printf ("\n");
    printf ("\n");
    
    system("pause");
    return 0;
}

int bubble_Sort(int sort_Array[], int array_Size) 
{
   bool swap_Flag = true;
   int pass = 0;
   
   while (pass<array_Size && swap_Flag) 
   {
      printf ("\n");
      if (pass > 0 )
      {
      printf ("Pass number %d rendered ", pass); 
      for (int i=0;i<array_Size;i++) 
      {
         printf ("|%d| ", sort_Array[i]);
      }
      }
      swap_Flag = false;
      pass++;
      for (int i=0;i<array_Size-pass;i++) 
      {
         if (sort_Array[i] > sort_Array[i + 1]) 
         {
            int temp = sort_Array[i];
            sort_Array[i] = sort_Array[i + 1];
            sort_Array[i + 1] = temp;                  
            swap_Flag = true;
         }
         
      }
   }
   if (pass-1==0)
   {
      printf ("The array is already sorted!");
   }
   else
   {
      printf ("\n"); 
      printf ("\n");
      system ("pause");
      system ("cls");
      printf ("Sorted array: ");
      output_Array(sort_Array, array_Size);
      printf ("\n");
      printf ("\nTotal passes: %d", pass-1);
   }
}

void output_Array(int array[], int array_Size) //function outputs the unsorted and sorted array
{  
   for (int i=0;i<array_Size;i++)
   {
      printf ("|%d| ", array[i]);
   }
}

All that's left to do is comment it...hopefully. Thanks again everyone.

[rgrwatson85]

Fu*& I forgot to change my function back to void. I was testing some ideas with returning a value and having the final array print from int main(). Guess it doesn't make a huge difference but I'm kinda anal about having things right!