ZatoPulse
Badges: 4
Rep:
?
#1
Report Thread starter 1 month ago
#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
reply
Strange5050
Badges: 16
Rep:
?
#2
Report 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
reply
Baleroc
Badges: 9
Rep:
?
#3
Report 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
reply
ZatoPulse
Badges: 4
Rep:
?
#4
Report Thread starter 4 weeks ago
#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
reply
ZatoPulse
Badges: 4
Rep:
?
#5
Report Thread starter 4 weeks ago
#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
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

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

Personalise

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%

Watched Threads

View All