This discussion is now closed.

Check out other Related discussions

decision maths help- bubble sort

How would you find the maximum number of comparisons and the maximum number of swaps that might be needed in a bubble sort to rearrange seven numbers into ascending order?

Thanks

Reply 1

ste0731

12

max number is when their all in reverse
= 6+5+4+3+2+1 = 21
or n(n-1)/2 is the formula to use

Reply 2

Princess Angelina

OP

3

so for example 6 numbers would have 15 comparisons and 15 swaps

Reply 3

ste0731

12

Princess Angelina

so for example 6 numbers would have 15 comparisons and 15 swaps

correct
5 on 1st pass
4 on 2nd pass
etc

(5+4+3+2+1) = 15

Reply 4

Princess Angelina

OP

3

is this the same for every algorithm, for example quick sort?

Reply 5

L-x

12

Princess Angelina

is this the same for every algorithm, for example quick sort?

Think about this for more than 2 seconds instead of asking TSR and you'll have the answer.

Reply 6

ahmed2017

10

How do you workout the number of swaps in bubble sort?

Reply 7

DylanJ42

18

Original post by ahmed2017

How do you workout the number of swaps in bubble sort?

looking at your profile I dont think youre a troll but this thread is more than 7 years old.

Its pretty straightforward to work out based on the order of the numbers just by counting it swap by swap though, i dont think a formula as such for the number of swaps in a given bubble sort exist

Reply 8

ahmed2017

10

Original post by DylanJ42

looking at your profile I dont think youre a troll but this thread is more than 7 years old.

Its pretty straightforward to work out based on the order of the numbers just by counting it swap by swap though, i dont think a formula as such for the number of swaps in a given bubble sort exist

😂😂 oops didnt see it was made 2009
Thanks and i also need help in knowing how to find the number of comparisons when using quick sort? Is it the same as finding the number of comparisons for the bubble sort?

Reply 9

ahmed2017

10

Original post by ahmed2017

😂😂 oops didnt see it was made 2009
Thanks and i also need help in knowing how to find the number of comparisons when using quick sort? Is it the same as finding the number of comparisons for the bubble sort?

I saw your profile, you got a* in maths and furthermaths, that's amazing! Could you please give me some tips on how to revise and what you used. Also what was you daily study routine, since once i reach home i have tonnes of homework to get through first and then not much time for revision for all my subjects. Thanks

Reply 10

DylanJ42

18

Original post by ahmed2017

😂😂 oops didnt see it was made 2009
Thanks and i also need help in knowing how to find the number of comparisons when using quick sort? Is it the same as finding the number of comparisons for the bubble sort?

oh thats okay then, in the future if a thread is super old just make a new one :smile:

quick sort is the pivot one right? if so then the number of comparisons is surely equal to the number of items in the list since every item must be a pivot at some point. If you mean how many lines of work you need to do (ie how many recursions of the algorithm) then that really just depends on the items, it will vary.

short answer though, im not sure. If that was an exam question i doubt id get it right

Reply 11

username5689222

8

how do you do this for quick sort?

decision maths help- bubble sort

Related discussions

Articles for you