Design and implement two versions of QuickSort over a set of input integers. The first version should choose the pivot as the first array location. The second version should choose the pivot as the middle value of the triple

< first value, last value, (first+last)/2-th value >

Count the number of comparisons performed by the partition function for each version.

A script file showing you running the test program for:

* Partition 1 with array of size 10
* Partition 2 with array of size 10
* Partition 1 with array of size 20
* Partition 2 with array of size 20

It is the number of comparisons of array elements needed to sort the array. So you will
need to add up all of the comparisons done in recursive calls.

[16:15] JediSpam: hey
[16:17] itssupersloth: yo
[16:17] JediSpam: do you think you could check out my post on the c++ category? i need help
[16:22] itssupersloth: ill check it out later
[16:22] itssupersloth: im busy pushing some code at work right now
[16:22] JediSpam: ah ok
[16:22] JediSpam: thats cool
[16:22] itssupersloth: the quicksort thread?
[16:22] JediSpam: yeah
[16:23] JediSpam: i've made one completely that works but i need help on trying to figure out using 2 in one source file
[16:23] JediSpam: and what my professor is asking
[16:24] itssupersloth: just create two functions
[16:26] JediSpam: but i have to count the number of comparisons.. i have ONE set of 10 values going through both of them? i don't get it
[16:27] itssupersloth: you would just have each function take a look at the original array
[16:27] JediSpam: ah.. so the number of comparisons is all of the comparisons combined i guess?
[16:27] itssupersloth: take the first function with your pivot and have it look at the original array
[16:27] itssupersloth: get its output
[16:28] itssupersloth: then take the second function with the original array
[16:28] itssupersloth: the point of the exercise as far as i can tell
[16:28] JediSpam: ah i see
[16:28] JediSpam: is comparing the two
[16:28] itssupersloth: is to show you how the pivot affects the number of times it sorts the array
[16:28] JediSpam: i would think that too.. but we're only printing out one set of comparisons? doesn't make sense
[16:28] itssupersloth: because one will have many more iterations to output the same result
[16:29] itssupersloth: email your teacher again asking if this information is correct
[16:29] itssupersloth: does that make sense though??
[16:29] JediSpam: yeah i see what you're saying


[16:29] JediSpam: and i understand the point is to see which uses less comparisons
[16:30] itssupersloth: koo
[16:30] JediSpam: but on the example of the program's output it does this:

The original order is: 22 13 54 12 26 43 38 19 28 14
The sorted order is: 12 13 14 19 22 26 28 38 43 54
The number of comparisons required is: 15
[16:30] JediSpam: how come it wouldn't have two different sets of comparisons.. one for the first quicksort and one for the second
[16:30] itssupersloth: its adding to the counter everytime it swaps a spot in the array
[16:31] JediSpam: ahhhh ok
[16:31] JediSpam: i think i understand
[16:31] itssupersloth: i think he means one comparison for each function
[16:31] itssupersloth: so you should have a number for qs1 at 10, qs1 at 20, qs2 at 10 and qs2 at 20
[16:31] JediSpam: ahh
[16:32] JediSpam: so how does the script file work? i've never written one
[16:32] itssupersloth: that way you can see how the pivot affects the number of comparisons
[16:32] JediSpam: yeah
[16:32] itssupersloth: i think he just means a text file of your output
[16:32] JediSpam: yeah
[16:32] itssupersloth: BUT for that you will have to ask him
[16:32] JediSpam: ok
[16:32] itssupersloth: which i would do to verify
[16:33] itssupersloth: is it allright if i post this conversation?
[16:34] JediSpam: sure
[16:34] JediSpam: copyright jedispam,sloth