Alonso Alonso - 1 month ago 5
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;

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.