You are Here: Home >< Maths

# Very quick/easy D1 question. watch

1. Find the maximum number of interchanges needed when 8 values are sorted into descending order using the Bubble Sort algorithm.

Thanks guys. <3
2. Anyone?
3. (Original post by OGC)
Anyone?
http://en.wikipedia.org/wiki/Bubble_sort
Worst case = n^2
4. so 64? Cool, thanks.
5. (Original post by Chrosson)
http://en.wikipedia.org/wiki/Bubble_sort
Worst case = n^2
It's not n^2. You wouldnt need to do 64 passes for it to be completely sorted.

@op, I think its.......7, but let me check.

Oh wait, interchanges =/= passes.

Yes...n^2 for interchanges, if you mean each time you swap 2 numbers round, sorry.
6. (Original post by OGC)
Find the maximum number of interchanges needed when 8 values are sorted into descending order using the Bubble Sort algorithm.

Thanks guys. <3
Spoiler:
Show
(Original post by wikipedia)
First observe that, after each comparison (and contingent swap), the largest element encountered in the current pass will reside in the last position traversed. Therefore, after the first pass, the largest element in the array will be in the very last position; that is, given a list of size n, the nth element will be in its final position after the first pass. Thus, inductively, it suffices to sort the remaining n - 1 elements: after the second pass, the n - 1th element will be in its final place, and so on. So each pass can be one step shorter than the previous pass, instead of every pass continuing to traverse all the elements at the end, which are already in their final positions and will not move in any case.

this is probably what is expected in A level..
Edit:thats still gives what chrosson said

### Related university courses

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: January 13, 2010
The home of Results and Clearing

### 3,194

people online now

### 1,567,000

students helped last year
Today on TSR

### University open days

1. Sheffield Hallam University
Tue, 21 Aug '18
2. Bournemouth University
Wed, 22 Aug '18
3. University of Buckingham
Thu, 23 Aug '18
Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams