Thread: modifying bubblesort function

These are the instructions to the problem:



You are to write a C program that behaves as follows:
1. The main function prompts the user to enter the data and then calls getInArray to read a list of up to
10 integer values into an array. Use -999 as a the sentinel value. You can assume the user will not
enter more than 10 values in the list (see sample output below).
2. The main function displays a title and then calls putIntArray to display the data in the order read (see
the sample output below).
3. The main program then calls bubbleSort which you must modify to have three parameters which in
order are the array, the number of values in the array and the direction for the sort (+1 for ascending
and -1 for descending). For this first call, bubbleSort is to do an ascending sort (third parameter set to
+1). In addition to rearranging the data, your modified bubbleSort is to return the number of
comparisons of adjacent pairs that it made while sorting the data.
4. The main program displays a title and then calls putIntArray to display the ascending sorted data (see
the sample output below).
5. The main program then displays the number of comparisons made in performing the sort (see the
sample output below).
6. The main program then calls your modified bubbleSort a second time to put the data into descending
order (third parameter set to -1).
7. The main program displays a title and then calls putIntArray to display the descending sorted data
(see the sample output below).
8. The main program then displays the number of comparisons made in performing the sort (see the
sample output below).
9. Lastly, the main program displays the program completion message (see the sample output below).

Your modified bubbleSort function must minimize the number of comparisons it makes. In particular, your
bubbleSort function is to avoid comparing data values that are known to be in order after the last pass
through the array. For example, if there are n values in the array and they are already in the required order,
your function should make n-1 comparisons.







----




This is the given code:

Code:

void putIntArray(int x[], int n){
// Display an int array with all
// values on one line.
  int k;
  for(k=0; k<n; k++)
    printf("%d ", x[k]);
  printf("\n");
  return;
}

int getIntArray(int x[],int stop){
// Read data into an integer array
// using sentinel value stop.
// Function returns the number of
// values read.
  int t, n=0;
  while(1){
    scanf("%d",&t);
    if(t==stop) return n;
    x[n++] = t;
  }
}


void bubbleSort(int numbers[], int array_size){
// This is a basic buuble sort routine.
// You must modify it to behave as described on the
// assignment.
  int i, j, temp;

  for (i = (array_size - 1); i > 0; i--){
    for (j = 1; j <= i; j++){
      if (numbers[j-1] > numbers[j]){
        temp = numbers[j-1];
        numbers[j-1] = numbers[j];
        numbers[j] = temp;
      }
    }
  }
  return;
}

this is our main function so far:

Code:

int main(){

int list[10];
int n;



printf("Enter input data (sentinel = -999): ");

n=getIntArray(list, -999);
printf("Data as read:\n");
putIntArray(list,n);

printf("Ascending order:\n");
bubbleSort(list,n, 1);

printf("Descending order:\n");
bubbleSort(list,n, -1);

printf("Program completed normally.\n");


return(0);


}

How do we modify this bubblesort function to get this output?




Output Needed

Enter input data (sentinel = -999): 1 2 3 6 5 4 7 8 9 -999
Data as read:
1 2 3 6 5 4 7 8 9
Ascending order:
1 2 3 4 5 6 7 8 9
Number of comparisons: 15
Descending order:
9 8 7 6 5 4 3 2 1
Number of comparisons: 36
Program completed normally.





If you can answer in the next 6 hours, that would be great. Thanks anyone

<< Here's a bubblesort for you, iMalc! >>

You'll need to add an int variable set to 0, and count the comparisons, your sort function makes.

You'll also need to add a function parameter to bubblesort, so it knows when to sort ascending and when to change it to descending.

call it "direction", or "order" or something.

bubblesortFunction(int numbers[], int size, int order)

Then in the inner for loop, you need to add an if statement like:

Code:

if(order > 0) {   //ascending order
   if( numbers[j-1] > numbers[j]) {
        //make your ascending order swaps in here
   }
}
if(order < 0) { //descending order
  if(numbers[j-1] < numbers[j] {      
      //descending order of swaps in here
   }
}

I played with this, using the bubblesort algorithm from Wikipedia, which is a good bubbler, I think.

Code:

#include <stdio.h>

int bubblesort(int n[]);

int main() {
  int i, compare;
  int n[9] =   {9,2,3,6,5,4,7,8,1}; 
   
  printf("\n\n\n");
  compare = bubblesort(n);
  printf("\n Comparisons made: %d\n", compare);  

  for(i = 0; i < 9; i++)
    printf("%2d ", n[i]);

  printf("\n\t\t\t     press enter when ready");
  i = getchar();
  return 0;
}
int bubblesort(int n[]) {
  int i, j, compare, temp, swaps, unsorted;
  int topIndex = 9;   
  
  compare = swaps = 0;
  
  do {
    unsorted = 0;
    for(i = 0; i < topIndex - 1;  i++) {  
                            //if(order > 0) {
        compare++;
        // shows the array when there's a comparison being made
        //printf("\n i: %d %3d%3d%3d%3d%3d%3d%3d%3d%3d", i,n[0],n[1],n[2],n[3],n[4],n[5],n[6],n[7],n[8]);
        //j = getchar();
        if(n[i] > n[i+1]) {
          temp = n[i];
          n[i] = n[i+1];
          n[i+1] = temp;
          swaps++;
          unsorted = 1;
          // shows the array when a swap has been made
          //printf("\n i: %d %3d%3d%3d%3d%3d%3d%3d%3d%3d", i,n[0],n[1],n[2],n[3],n[4],n[5],n[6],n[7],n[8]);
          //j = getchar();
        }
                            //}
    }
    topIndex--;
  }while(unsorted);

  printf("\n Swaps: %d \n", swaps);
  return compare;
}

/*
This is the bubbler algorithm from Wiki, in pascal
  do
    swapped := false
    for each i in 0 to n - 2  inclusive do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
    n := n - 1
  while swapped

*/

I can cheat and make it yield the required 15 comparisons and correctly sort that particular data set however, it's not a correct solver for other number sets (put the 9 at numbers[0], and the 1 at numbers[8] for a good test).

I have an idea for using buckets with this - we'll see how that goes. I define "compare" as any comparison of an array's value, with anything else (including just variables). Or would a comparison only be counted if it compared two array values?

Without changing the algorithm into insertion sort, (or whatever), what could you do to limit the comparisons to their lowest number possible?