Alonso - 1 year ago 67
C++ Question

# How to find un-ordered numbers (lineal search) [SOLVED]

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.

• `MAX = 100000`
is the capacity of the list.

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

Example of two lists:

`1 2 5 6 3`

`1 6 2 9 7 4 8 10 13`

For the first list the output is 2 since 5 and 6 should be both after 3, they are unordered; for the second the output is 3 since 6, 9 and 7 are out of order.

The most important condition in this problem: do the searching in a linear way O(n) or being quadratic the worst case.

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

"unordered" function compares each element of the array with the one given by "minimal" function; if it finds one bigger than the minimal, that element is unordered.

``````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;
``````

"minimal" function takes the minimal of all the elements in the list between the one which is being compared in "unordered" function and the last of the list.
`i < elements <= n`
. Then, it is returned to be compared.

``````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?

[SOLVED] (thank you to user "Erik"):

``````int unordered (int A[MAX], int n)
int count = 0, j;
bool continue = false;

for (int i = n-1; i>0; i--){
j=i-1;

do {
if (A[i] < A[j]){
count++;
continue = true;
j--;
}
else{
continue = false;
i = j+1;
}
} while (continue);
}

return count;
``````