Помогите новичку разобраться с массивами :) [C++]

[Sow]

Я конечно понимаю, мой вопрос детский для вас, но помогите разобраться, как написать код? если не затруднит, с небольшими комментариями, просто хочу понять, как это делается, а не просто увидеть)

а задание такое:
Разделить массив на две части, поместив в первую элементы, большие среднего арифметического их суммы, а во вторую —меньшие (части не сортировать)

насколько представляю:
генератор случайных чисел
два счетчика: один на убавление, второй на увеличение
и контрольная точка, до которой идут оба счетчика
и еще не могу понять, надо ли в отдельный массив полученные числа или в этом делить, если в нем, то как это?!(

[Алексей++]

1) посчитать среднее арифметическое (первый проход по массиву)
2) пройтись второй раз и раскидать элементы

[Sow]

1) посчитать среднее арифметическое (первый проход по массиву)
2) пройтись второй раз и раскидать элементы

Спасибо за ответ
1) понятно
2) вот с этим не уловил...все таки в другие массивы раскидывать или нет? не могу понять, как это должно выглядеть

[Вад]

Sow, зачем? в этот Нужно просто разумно организовать обмен элементов в массиве.
Вообще, алгоритм quicksort выполняет на каждом шаге похожую задачу: в одну часть массива перебрасываются все числа, большие некоторого выбранного значения, а в другую - меньшие (после чего к обеим половинам применяется то же действие - рекурсивно).

Поступает quicksort примерно так: двигается сразу в двух направлениях - от начала массива и от конца. Допустим, нужно в первой части получить элементы, большие заданного числа. Тогда:
1. мы двигаемся по массиву от начала к концу, пока не найдём число, не удовлетворяющее этому условию (т.е. оно <=).
2. Теперь начинаем движение от конца массива к началу, пока не найдём число, >= заданного.
3. Сравниваем позиции: если найденное "большее" левее "меньшего", то прекращаем сортировку. В противном случае производим обмен значений двух найденных элементов массива и возвращаемся к пункту 1 (счётчики/указатели, естественно, не сбрасываем, а продолжаем с тех позиций, где остановились)

[Sow]

Вад, спасибо)
но есть загвоздка про такой алгоритм еще вроде ничего не слышал, самое начало обучения, только массивы проходим..да и я не очень хорошо в этом разбираюсь, если еще не понятно..если это уже из позднего, сам понимаешь, низя) но мог и неправильно понять, можешь можешь показать на примере?

[Вад]

Подробное описание с примерами - тут.
Если всё-таки сложно и непонятно (до такой степени, что реализация принципа разделения массива на части вызывает трудности), то, возможно, и на самом деле стоит выбрать менее эффективные и более простые методы.

[Sow]

Посмотрел, вроде даже все понятно, но мы таким еще не пользуемся точно, нужна более простая версия