Please solve the puzzle.

In a one-dimensional array, move all negative numbers to the beginning of the array, and the rest to the end while maintaining the order of the sequence. An additional array is not allowed.

    2 answers 2

    1. checks an array element in a loop
    2. if less than 0, change with the first
    3. if not take the next item
    4. we introduce a counter (that is, the 2nd iterator), which will monitor the number of the cell in which / with which we change values

    Probably, you can even enter the counter of the 2nd iterator. Type, if the current value is less than 0, then +1, if not, but nothing to add. This will always be on the last element with which it will be possible to exchange a negative number.

      This task can be considered as a special case of stable sorting without using additional memory.

      Merge sorting is well suited as stable sorting, the complexity of which is O (n * log (n)):

      void merge_sort(BidirIterator first, BidirIterator last) { auto n = std::distance(first, last); if (n < 2) return; // Nothing to sort. auto middle = std::next(first, n / 2); merge_sort(first, middle, cmp); merge_sort(middle, last, cmp); std::inplace_merge(first, middle, last); }

      The std::inplace_merge uses O (n) memory.
      However, we do not need it, because our sort key has only two values ​​(true and false).
      After two recursive calls of merge_sort, we get the sequence of the form

       000011111000111111 ^_ middle

      And all we have to do is apply std::rotate to swap two middle parts.

      Therefore, we can rewrite our algorithm as follows:

       template<typename BidirIterator, typename Predicate> BidirIterator stable_partition(BidirIterator first, BidirIterator last, Predicate pred) { auto n = std::distance(first, last); if (n == 0) return first; if (n == 1) return pred(*first) ? last : first; auto b = std::next(first, n / 2); auto a = ::stable_partition(first, b, pred); auto c = ::stable_partition(b, last, pred); // Rotate: // [11111|0000|11111|0000] // FABCL // [11111|11111|0000|0000] // Result return std::rotate(a, b, c); }

      Example of use:

       int a[6] = {1, -1, 2, 3, -2, -3}; ::stable_partition(a, a + 6, [](int x){ return x < 0; }); for (auto x : a) std::cout << x << ' '; // Выводит -1 -2 -3 1 2 3

      ( :: it is necessary that there is no conflict with std::stable_partition )

      • Cool! Recently, someone here had a similar task: to write a comparator for qsort sishnogo, which would sort the positive numbers, and the negative carried to the end of the array, without changing the order. (And since qsort unstable, we did not find a solution.) - VladD