# Bubble sort algorithm question

Watch
Announcements
#1
numbers = [9, 5 , 4, 15, 3, 8, 11]
numItems = len(numbers_)
for i = 0 to numItems - 2
--snip---
could somebody explain why it is numItems - 2 instead of 1? This was in the OCR A level textbook.
Thanks !
0
1 month ago
#2
It's -2 because the algorithm evaluates and/or swaps with the next index. Otherwise you'd be thrown an index out of bound error when the algorithm comes to the last index and tries to evaluate its value based on the next index which is non-existent. Bubble sort doesn't need to ever arrive at the last index, only the one prior to it. Hence -2 and not -1.

var array = [1, 2, 3, 4]

The value 4 is at array.length -1 (or array[3]). If the algorithm got to that index, it would check if the value at that index is greater or less than array[(array.length -1) + 1]. That index doesn't exist, thus you need -2 in this instance to stop it from checking a non-existent index and thus throwing an error.
Last edited by Strange5050; 1 month ago
1
4 weeks ago
#3
(Original post by ZatoPulse)
numbers = [9, 5 , 4, 15, 3, 8, 11]
numItems = len(numbers_)
for i = 0 to numItems - 2
--snip---
could somebody explain why it is numItems - 2 instead of 1? This was in the OCR A level textbook.
Thanks !
So here's my explanation of it:

So you know how Bubble Sort works, right: you look at the first two elements.

Comparison 1: 9 and 5. Swap 9 with 5.
New array: [5, 9, 4, 15, 3, 8, 11]

Comparison 2: 9 and 4. Swap 9 and 4.
New array: [5, 4, 9, 15, 3, 8, 11]

Comparison 3: 9 and 15. No swap.

Comparison 4: 15 and 3. Swap
New array: [5, 4, 9, 3, 15, 8, 11]

Comparison 5: 15 and 8. Swap
New array: [5, 4, 9, 3, 8, 15. 11]

Comparison 6: 15, 11. Swap
New array: [5,4, 9, 3, 8, 11, 15]

Now, after len(numbers-2), we are done after 6 comparisons.

Now, let's suppose we have len(numbers-1), that would mean we would have a 7th comparison, which would be:

Comparison 7: 15 and [?]
Index out of bounds.
You see, when you get to 15, it will look if there is another number to the right. It can't find another number, so it will be comparing 15 with nothing.

Hope that helps
1
#4
(Original post by Baleroc)
So here's my explanation of it:

So you know how Bubble Sort works, right: you look at the first two elements.

Comparison 1: 9 and 5. Swap 9 with 5.
New array: [5, 9, 4, 15, 3, 8, 11]

Comparison 2: 9 and 4. Swap 9 and 4.
New array: [5, 4, 9, 15, 3, 8, 11]

Comparison 3: 9 and 15. No swap.

Comparison 4: 15 and 3. Swap
New array: [5, 4, 9, 3, 15, 8, 11]

Comparison 5: 15 and 8. Swap
New array: [5, 4, 9, 3, 8, 15. 11]

Comparison 6: 15, 11. Swap
New array: [5,4, 9, 3, 8, 11, 15]

Now, after len(numbers-2), we are done after 6 comparisons.

Now, let's suppose we have len(numbers-1), that would mean we would have a 7th comparison, which would be:

Comparison 7: 15 and [?]
Index out of bounds.
You see, when you get to 15, it will look if there is another number to the right. It can't find another number, so it will be comparing 15 with nothing.

Hope that helps
Ahhh so its because its a comparison you dont need to go to the end of the array
Makes total sense
Thanks : )
0
#5
(Original post by Strange5050)
It's -2 because the algorithm evaluates and/or swaps with the next index. Otherwise you'd be thrown an index out of bound error when the algorithm comes to the last index and tries to evaluate its value based on the next index which is non-existent. Bubble sort doesn't need to ever arrive at the last index, only the one prior to it. Hence -2 and not -1.

var array = [1, 2, 3, 4]

The value 4 is at array.length -1 (or array[3]). If the algorithm got to that index, it would check if the value at that index is greater or less than array[(array.length -1) + 1]. That index doesn't exist, thus you need -2 in this instance to stop it from checking a non-existent index and thus throwing an error.
Got it thanks man !
0
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### Poll

Join the discussion

#### Are you travelling in the Uni student travel window (3-9 Dec) to go home for Christmas?

Yes (106)
28.49%
No - I have already returned home (47)
12.63%
No - I plan on travelling outside these dates (71)
19.09%
No - I'm staying at my term time address over Christmas (38)
10.22%
No - I live at home during term anyway (110)
29.57%