Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > преобразовать массив

Автор: ArniLand 16.3.2011, 00:18

Нужно преобразовать массив из целых чисел, который состоит из положительных и отрицательных элементов, чтобы вначале располагались положительные элементы, затем отрицательные. Вариант использование сортировки просьба не рассматривать.

Автор: Earnest 16.3.2011, 07:50

Вообще-то любое переупорядочивание можно назвать сортировкой. В данном случае подойдет алгоритм partition из стандартной библиотеки C++.
Если у тебя не C++, то несложно реализовать самому: перебираем элементы массива, пока они положительные, как только встретишь отрицательный, начинаешь двигаться с конца, пока не встретишь положительный, затем меняешь их местами; далее продолжаешь это движение навстречу друг другу.

Автор: Akina 16.3.2011, 08:38

И в чём проблема?
Обрабатываем масиив, используя 2 указателя. Первый идёт с начала, второй с конца. Первый останавливается, встретив отрицательный элемент, второй - встретив положительный. Если оба указателя остановились - соотв. элементы меняются местами, и процесс продолжается. Когда указатели встретились - процесс завершён.

Автор: Earnest 16.3.2011, 09:05

Akina, респект, у тебя значительно лучше получилось изложить этот алгоритм. smile

Автор: _Y_ 16.3.2011, 15:53

Цитата(ArniLand @ 16.3.2011, 00:18

)

использование сортировки просьба не рассматривать

Ну если задаться удовлетворением этого странного условия, то можно так:

Создаем два новых пустых массива (MP и MM) того же размера, что и исходный (M0).
В цикле проходим по элементам M0. Если элемент больше нуля - кладем его в MP, если меньше - в MM.
Копируем заполненную часть MM в конец MP.

Обработка нулевых значений здесь не предусмотрена, но как быть с ними - ежику понятно - третий массив можно использовать, например.

И никакого намека на вражескую сортировку smile

Автор: Akina 16.3.2011, 15:59

Цитата(_Y_ @ 16.3.2011, 16:53

)

Обработка нулевых значений здесь не предусмотрена, но как быть с ними - ежику понятно - третий массив можно использовать, например.

В зависимости от того, какое сравнение с нулём (строгое или нет) будет использовано, все нули ссыплются в один из массивов... но поскольку ноль принято считать всё-таки числом неотрицательным, то ему место среди положительных...
А можно просто изначально МР инициализировать нулями, а при обработке нули тупо игнорировать. Правда, это увеличит вдвое количество сравнений.

Автор: _Y_ 16.3.2011, 18:21

Akina, поскольку массив целочисленный, то строгое сравнение, конечно.

Но мы уже идем в дебри, т.к. про нули в условиях задачи вообще ничего сказано не было.

Может нулей вООбще не бывает smile

Их .... это самое .... русские мужики придумали. Ну .... чтобы деньги не платить smile