Разделение элементов в массиве по условию
Насколько я помню, он назывался (3,4 года назад) шагом раздела и был частью быстрой сортировки, но я не уверен.
Я должен spllt элемент в массиве против условия, например, условие: х < 5
Для массива:
7,2,7,9,4,2,8
Результат будет:
2,4,2,7,7,8,9
Порядок элементов не имеет значения. Предполагается, что это должно быть сделано в одном цикле for без встроенных циклов внутри.
Я ищу псевдо-или C ++-код для того, чтобы поменять местами элементы в таких условиях.
Код, который мне уже удалось создать:
#include "stdafx.h"#include <stdlib.h>
#include <iostream>
#include <functional>
using namespace std;
template <typename T>
size_t partition(T arr[], size_t size, function<bool(T)> fun) {
//here I would like to split it against the fun():boolean result
return 4;
}
template <typename T>
void printTable(T arr[], size_t size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
template <typename T> bool less10(T a) {
return a < 10;
}
int main(){
cout << "BLABLA" << endl;
int arri[] = { 1, 20, 3, 50, 6, 7 };
size_t sizi = sizeof(arri) / sizeof(arri[0]); printTable(arri, sizi);
size_t fi = partition(arri, sizi, (function<bool(int)>)less10<int>);
printTable(arri, sizi);
cout << "index: " << fi << endl; cout << endl;
double arrd[] = { 1, 20, 3, 50, 6, 7 };
size_t sizd = sizeof(arrd) / sizeof(arrd[0]); printTable(arrd, sizd); function<bool(double)> lambda =
[](double x) -> bool {return x > 10; }; size_t fd = partition(arrd, sizd, lambda); printTable(arrd, sizd);
cout << "index: " << fd << endl;
system("PAUSE");
return 0;
}
Решение
Вы могли бы закодировать это так
#include <algorithm>
int main()
{
int ar[] = {7,2,7,9,4,2,8};
std::partition(std::begin(ar), std::end(ar), [](int val) {
return val < 5; });
}
Если важна реализация std :: partition, вы можете проверить тривиальную реализацию
template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator partition (BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred)
{
while (first!=last) {
while (pred(*first)) {
++first;
if (first==last) return first;
}
do {
--last;
if (first==last) return first;
} while (!pred(*last));
swap (*first,*last);
++first;
}
return first;
}
Другие решения