testing a bubble sort algorithm

This is a discussion on testing a bubble sort algorithm within the C++ Programming forums, part of the General Programming Boards category; Hi. I have created a program which uses the bubble sort to generate random numbers and sort them using a ...

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    42

    testing a bubble sort algorithm

    Hi.

    I have created a program which uses the bubble sort to generate random numbers and sort them using a bubble sort. I then created two functions which would count the number of compares and swaps, Te problem is I have absolutely no idea on how to test if the number of compares and swaps are correct. How would i go about testing for this?

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Make sure the program prints out the original data, run through the algorithm yourself, and see how many compares and swaps are actually needed.

  3. #3
    Registered User
    Join Date
    Nov 2008
    Posts
    42
    yes, but what if you want to test for say 100 numbers, and you want to know if the number of compares and swaps are correct. we know that trying to do this by hand is quite long, how can the program be tested fairly if we dont want to do it by hand?

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You don't do 100. You do 6. And then if it works for 6, presumably it works for 100 as well.

    Alternatively, I suppose, you can find someone else in the class, make sure you are using the same data, and compare answers (you could still both be wrong, I suppose, but it's less likely).

    Also, you would expect, as the size of the list to be sorted grows, that your numbers would roughly obey O(n^2) -- so if you double the size of the list, you should do four times as much work.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305
    Why would you not trust your code to tell you the correct swap and compare counts? You can either increment counters right before the comparisons and swaps, or you can do it the way I do it, by putting the counter increments into the less-than and assignment operators of the class.
    It will give you the right answer, as long as you remember to set it to zero initially.
    (Divide by 3 if you put a counter in the assignment operator of course)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. sort algorithm
    By clairmonte in forum C Programming
    Replies: 9
    Last Post: 07-10-2009, 02:18 PM
  2. help with debug (bubble sort algorithm)
    By lbraglia in forum C Programming
    Replies: 5
    Last Post: 10-19-2007, 05:24 PM
  3. Array/Structure Bubble Sort
    By JKI in forum C++ Programming
    Replies: 3
    Last Post: 09-29-2003, 11:59 AM
  4. Replies: 2
    Last Post: 05-06-2003, 08:34 AM
  5. Bubble Sort, Qucik Sort
    By insomniak in forum C Programming
    Replies: 2
    Last Post: 03-15-2003, 03:54 PM

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