Alonso - 3 months ago 33

C++ Question

A **list partially ordered** of n numbers is given and I have to find those numbers that does not follow the order (just find them and count them).

- There are no repeated numbers.
- There are no negative numbers.
- is the capacity of the list.
`MAX = 100000`

- , the number of elements in the list, is given by the user.
`n`

Example of two lists:

`1 2 5 6 3`

`1 6 2 9 7 4 8 10 13`

For the first list the

The most important condition in this problem:

Here is part of the code I developed (however it is no valid since it is a quadratic search).

`int unordered (int A[MAX], int n)`

int cont = 0;

for (int i = 0; i < n-1; i++){

if (A[i] > minimal(A, n, i+1)){

count++;

}

}

return count;

`i < elements <= n`

`int minimal (int A[MAX], int n, int index)`

int i, minimal = 99999999;

for (i = index; i < n; i++){

if (A[i] <= minimo)

minimal = A[i];

}

return minimal;

How can I do it more efficiently?

Answer

Start on the left of the list and compare the current number you see with the next one. Whenever the next is smaller than the current remove the current number from the list and count one up. After removing a number at index 'n' set your current number to index 'n-1' and go on.

Because you remove at most 'n' numbers from the list and compare the remaining in order, this Algorithmus in O(n).

I hope this helps. I must admit though that the task of finding numbers that are out of of order isn't all that clear.