Thread: bubble sort help.

  1. #1
    Registered User zeromx's Avatar
    Join Date
    Oct 2006
    Location
    uk
    Posts
    6

    bubble sort help.

    Hi,
    I just recently joined and i need some help with one of my assignments. please can you have a look and try to help thank you.

    task:
    Write an efficient bubble sort function optimised so as not to check data that is guaranteed to be in the correct position (i.e. each pass is shorter than the previous one). It should include code (as the naivesort program below does) that counts the number of comparisons performed storing the result in a call by reference variable to pass the information back to the calling function. Your program should print out a copy of the array before and after sorting. Include a test function that tests the code for a series of data sets containing from 1 to 100 pieces of randomly generated data. Modify the program given below.

    Code:
    // 	Sort an array of integers using naive sort: multiple 
    //   passes with smaller values gradually bubbling up to the 
    //   top. It works by repeated comparison of pairs of values
    //   Count critical ops and save in a file for sorting array sizes up to 100
    
    
    // For gcc compiler:
    // gcc  -std=c99 naivesort.c -o naivesort
    // even harder options -ansi -pedantic
    
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    void naive_sort (int array [], int arraySize, int * count);
    void swap (int * v1, int * v2);
    void fill_array (int array [], int arraySize);
    void print_array(int array[], int sizeOfData);
    
    const int RANGE = 200; // random data used in range 0-199
    
    int main()
      {
         const int arraySize = 100;
         int a[arraySize];
         FILE *resultsFile;
         
         // open the file for writing ("w")
         resultsFile = fopen("nsort.dat", "w");  
    
         if (resultsFile != NULL)      // file successfully opened
          {
             // seed the random number generator so it gives different
           // random numbers each time
           srand ( time (0) );
    
    
           // Table headings
           printf ("Found\t Data Size\t Comparisons Needed\n"  );
           
           //\t puts in a tab character, \n a new line
           fprintf (resultsFile, "Data Size\t Comparisons Needed\n"  );
    
           // Generate table for data of different sizes
           // giving number of comparisons each time
    
           for (int datasize = 1; datasize <= arraySize; datasize = datasize + 1)
    		{
    	  		int count = 0;  // number of comparisons this time
    
    	  		fill_array(a, datasize);
    
    	  		naive_sort (a, datasize, & count);
    
    	  		// print results in a table
              	printf("%d  \t\t\t  %d\n", datasize, count);
              	fprintf(resultsFile, "%d  \t\t\t  %d\n", datasize, count);
    		}
    
            print_array(a, arraySize); // check final version at least was sorted
    
           
         }
       else
          fprintf(resultsFile, "File not opened\n");
    
       fclose(resultsFile); return 0;
      }

  2. #2
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    Ok, first of all, here we answer questions, not just general pleas for help. What exactly is the problem ? Unexpected behaviour ? Not compiling ? General question on bubble sort ?

    Be specific.

    Oh, and by the way, chances are we'll have to look at your other functions too, (except probably print_array), so you may want to post them as well.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  3. #3
    Registered User zeromx's Avatar
    Join Date
    Oct 2006
    Location
    uk
    Posts
    6
    Hi,
    Basically i need to make a bubble sort from that piece of code. As i have just started learning C. i would imagine that someone could help me, by making it a bubble sort. thank you.

  4. #4
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  5. #5
    Registered User zeromx's Avatar
    Join Date
    Oct 2006
    Location
    uk
    Posts
    6
    From what code i got up there. isnt it possible?.

  6. #6
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    What appears to be lacking from the code you posted is an attempt to implement a sort of any kind.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Welcome to the forum.

    You've got some interesting phrases in the task description:
    "efficient bubble sort": bubble sorts are *not* efficient
    "not to check data that is guaranteed to be in the correct position": very odd idea that I can't wrap my head around. Maybe it's just me.

    "naive" sort: never heard of "naive" sort.


    If I understand this right, you're supposed to replace the naive sort function, with the bubble sort function. What part of the assignment has you stumped?

    You need to get into this enough to ask some specific code or algorithm, questions.

    Adak

  8. #8
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Quote Originally Posted by zeromx
    From what code i got up there. isnt it possible?.
    It is possible

    replace the line
    Code:
    naive_sort (a, datasize, & count);
    with the following
    Code:
    bubble_sort (a, datasize, & count);
    Then - write the function bubble_sort as required by the assignment
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  9. #9
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Code:
    // even harder options -ansi -pedantic
    Um...
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  10. #10
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    Quote Originally Posted by zeromx
    i would imagine that someone could help me, by making it a bubble sort. thank you.
    What you don't understand is that NO ONE will do that unless you post a half-decent attempt at it. We won't do your homework for you...
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 05-13-2009, 03:25 PM
  2. Bubble Sort... which type?
    By gflores in forum C++ Programming
    Replies: 8
    Last Post: 08-15-2004, 04:48 AM
  3. Bubble Sort, Qucik Sort
    By insomniak in forum C Programming
    Replies: 2
    Last Post: 03-15-2003, 04:54 PM
  4. optimizing bubble sort
    By Sargnagel in forum C Programming
    Replies: 14
    Last Post: 01-23-2003, 06:27 AM
  5. Help with Bi-Directional Bubble Sort in C
    By cunninglinguist in forum C Programming
    Replies: 0
    Last Post: 04-19-2002, 02:32 PM