CODEWITHSUNDEEP
algorithmsortingpseudocode
user602996
user602996

Reputation:

Bubble sort pseudo code what does n-1 mean?

I have a question about a specific line in the bubble sort pseudo code.

This pseudocode is taken from wikipedia:

procedure bubbleSort( A : list of sortable items )
   n = length(A)
   repeat     
     swapped = false
     for i = 1 to  n-1 inclusive do //THIS IS THE LINE I DON'T UNDERSTAND
       /* if this pair is out of order */
       if A[i-1] > A[i] then
         /* swap them and remember something changed */
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
     until not swapped
end procedure

I do not understand the for loop's condition (1 to n-1). I clearly have to run through all elements from the second element at index 1 to the last element for the algorithm to work.

But when I read the term n-1 I see it as the last element minus 1, which will skip the last element. So I guess my question is, what does n-1 really mean in this context?

Upvotes: 1

Views: 5453

Answers (5)

Johannes
Johannes

Reputation: 6717

If n is the count of elements. The highest index is n-1.

This line iterates from the index 1 to the highest index n-1.

The first element has an index of 0. This code does not start there because of what it does inside the loop. pay attention to the i-1 part.

To give you an example of what that pseudocode does:

`A ={'C', 'E', 'B', 'D', 'A'}`
`n` = `5`
inner_loop for i  => 1, 2, 3, 4
    i = 1
    if(A[0] > A[1]) => false
    i = 2
    if(A[1] > A[2]) => true
        swap(A[1] , A[2]) => A ={'C', 'B', 'E', 'D', 'A'}
        swapped =  true
    i = 3
    if(A[2] > A[3]) => false
    i = 4
    if(A[3] > A[4]) => true
        swap(A[3] , A[4]) => A ={'C', 'B', 'E', 'A', 'D'}
        swapped =  true

In a senses this code does not run through the elements but rather trough the comparisson of adjacent elements.

Upvotes: 2

DRY Believer
DRY Believer

Reputation: 1018

the sorting is occurring till n-1 because the last element will automatically be sorted during the last iteration i.e the nth iteration in case of bubblesort

Upvotes: 0

dan.m was user2321368
dan.m was user2321368

Reputation: 1705

That is written in pseudo-code, so we don't know for sure how that "language" implements array indexing, but it seems that it is 0-indexed. Which means that if length(A) = n = 5 the elements are numbered from 0 through 4 (i.e. A[0] is how you access the first element A[4] is how you access the last one).

Upvotes: 0

Steve Cobb
Steve Cobb

Reputation: 831

Since most programming languages start with index 0, you'll only want to compare from array index 0 to array index n-1 for an array of size n. If you continue to n, you'll be comparing outside of the array in the line:

if A[i-1] > A[i]

Hope this helps.

Upvotes: 0

Andrew
Andrew

Reputation: 5083

n-1 does not mean the second-to-last element. It means the last element.

Here's why: Usually in programming, lists are zero-indexed, meaning the numbering starts at zero and goes to n-1 where n is the length of the list. The loop starts at i = 1 which is actually the second element (since later you have to compare A[i] to A[i-1]—that's the first element).

Upvotes: 1

Related Questions