CODEWITHSUNDEEP
c++algorithmsorting
Krzysztof Panek
Krzysztof Panek

Reputation: 21

Changing twice "for" loop for single "for" loop (SORTING)

This is my first post here. I have to sort values that returns True or False. My problem is that, it take too long in two loops but I can't change it to single loop.

Here is code for the sorting: 

for (int i = 0; i < size; i++) {
    if (f(arr[i]) == true) {
       for(int j = 0; j < size; j++){
           if(f(arr[j]) == false){
               swap(arr[i],arr[j]);
           }
       }    
}

And here is function:

bool isEven(int e) { return e%2 == 0; }

True vaules must be first in array and false vals on the right side(place that left). I must get rid of that inside loop. Thanks for help and advices. I can't make any new arrays, that must be done with the one in loop (arr[]).

For example for array: 1,2,3,4,5,6 -> 2 4 6 1 5 3.

Upvotes: 0

Views: 214

Answers (1)

Oliver Dain
Oliver Dain

Reputation: 9953

The problem is that in that inner loop you start at 0 even though you know that all elements in [0, i] are false. So I think you can do this:

int i = 0;
int j = size - 1;
while (i < j) {
   if (f(arr[i] == true) {
       while (f[arr[j] == true && j > i) {
           j -= 1;
       }
       swap(arr[i], arr[j]);
   }
   i += 1;
}

Note that while the above looks like it has 2 loops each element is examined only once so the runtime is O(n) as opposed to your original solution which is O(n^2).

Upvotes: 1

Related Questions