modifying bubblesort function

This is a discussion on modifying bubblesort function within the C Programming forums, part of the General Programming Boards category; These are the instructions to the problem: You are to write a C program that behaves as follows: 1. The ...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    1

    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

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    << 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
       }
    }

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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?

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,264
    Quote Originally Posted by Adak View Post
    [B]<< Here's a bubblesort for you, iMalc! >>
    Indeed! I noticed it earlier too.

    I suggest tracking where a bubble floats to and making subsequent iterations of the inner loop only go that far. Google "Improved Bubble Sort".
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursive function
    By WatchTower in forum C Programming
    Replies: 11
    Last Post: 07-15-2009, 07:42 AM
  2. Getting an error with OpenGL: collect2: ld returned 1 exit status
    By Lorgon Jortle in forum C++ Programming
    Replies: 6
    Last Post: 05-08-2009, 08:18 PM
  3. In over my head
    By Shelnutt2 in forum C Programming
    Replies: 1
    Last Post: 07-08-2008, 06:54 PM
  4. Troubleshooting Input Function
    By SiliconHobo in forum C Programming
    Replies: 14
    Last Post: 12-05-2007, 06:18 AM
  5. Replies: 28
    Last Post: 07-16-2006, 11:35 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21