can someone explain the while loop part of this pseudocode

user_16316081 0
Viewed 64

I understand this is a code to check if elements in the list are different. But the while loop is aspect is confusing. Can someone explain this part

// Input: list (or array) of n integers a[0]; a[1]; a[2],....., a[n − 1]

// Output: Does there exist a repeated integer in the list?

repeat ← false
i ← 0 // set i to zero

while i <= n − 2 do
    j ← i + 1 
    while j <= n − 1 do
        if (a[i] == a[j]) then
            repeat ← true
        else
            repeat ← false
        j ← j + 1
    i ← i + 1

if (repeat == true) then
    print "Some numbers repeated"
else
    print "All numbers are different"
pseudocode list arrays algorithm
1 Answers

As other users mentioned in the comments the code contains a bug. You have to remove the "else" branch from the if-statement in the inner while-loop. If you do that, the code should work according to the specifications checking all pairs of elements in the array for equality. The first while-loop with running index i iterates over all elements of the array up to the second last. In each iteration of the outer while-loop the inner (nested) while-loop iterates from element j = i + 1 to the last element (i.e. j runs over all elements to the right of the i-th element) and checks each pair of elements (i-th and j-th element) for equality (setting the repeated-flag if two elements are equal). To better understand the pattern this algorithm follows and see why it actually compares all pairs of elements it could help to execute the algorithm manually on a small example. This algorithm is quite inefficient, its time complexity is O(n^2). You can use an efficient set data stracture (such as a balanced binary tree or a hash set) to reduce the time complexity to O(nlog(n)) or amortized O(n).

user_155319860
Related