CODEWITHSUNDEEP
c++arraysalgorithm
stoner
stoner

Reputation: 161

C++ shift values to begin of array

Need to move all values which is less than 1 in begin of array (WITHOUT SORT, and need solution without second array)

for example:

START ARRAY: {-2.12, -3, 7.36, 6.83, -1.82, 7.01}

FINISH ARRAY: {-2.12, -3, -1.82, 7.36, 6.83, 7.01}

There is my solution but it doesn't work very well, because at final we receive:

FINISH ARRAY: {-2.12, -3, -1.82, 6.83, 7.36, 7.01}

Values which less than 1, moves to begin of array, but 4 and 5 elements not in correct order

#include <iostream>

using namespace std;

int main() {
    double arr[6] = {-2.12, -3, 7.36, 6.83, -1.82, 7.01};

    cout << "Start array: " << endl;
    for (int x = 0; x < 6; x++) {
        cout << arr[x] << ", ";
    }

    int index=0;
    double temp;
    for (int i = 0; i < 6; i++) { 
        if (arr[i] < 1) {
            temp=arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
            index++;
        }
     }
    cout << endl << "FINISH ARRAY: " << endl;
    for (int x = 0; x < 6; x++) {
        cout << arr[x] << ", ";
    }



    return 0;
}

Upvotes: 2

Views: 195

Answers (1)

Evg
Evg

Reputation: 26282

Use std::stable_partition:

std::stable_partition(std::begin(arr), std::end(arr), 
    [](double d) { return d < 1; });

If you want to implement it yourself, note, that in-place stable partition (using comparisons and swaps) cannot be done better than in O(N log N) time. Any algorithm with O(N) running time is incorrect.

One possible solution can be obtained with divide-and-conquer approach:

template<class It, class Pred>
It stable_partition(It first, It last, Pred pred) {
    // returns the iterator to the first element of the second group:
    // TTTTTFFFFFF
    //      ^ return value

    if (first == last)
        return last;
    if (last - first == 1) {
        if (pred(*first))     // T
            return last;      //  ^ last  
        else                  // F
            return first;     // ^ first
    }

    // Split in two halves
    const auto mid = first + (last - first) / 2;

    // Partition the left half
    const auto left = stable_partition(first, mid, pred);
    // TTTTTFFFFF
    //      ^ left
    //           ^ mid 

    // Partition the right half
    const auto right = stable_partition(mid, last, pred);
    // TTTTTFFFFF
    //      ^ right
    // ^ mid

    // Rotate the middle part: TTTTTFFFFFTTTTTFFFFF
    //                              ~~~~~~~~~~
    //                              ^ left    ^ right
    //                                   ^ mid
    const auto it =  std::rotate(left, mid, right);
    // TTTTTTTTTTFFFFFFFFFF
    //           ^ it
    return it;
}

It resembles quicksort, but here we do not actually sort the range. std::rotate itself can be easily implemented via three reverses.

Upvotes: 5

Related Questions