Другие языки программирования и технологии

Сортировка

Необходимо написать функцию которая сортирует массив таким образом:

Путь есть массив из N = 10 элементов, и даны 2 - граныцы (0 <= L,R <= N), допустим в данном случае L = 4 R = 8.

Тогда массив:

0 1 2 3 4 5 6 7 8 9 - до выполнения функции сортировки
0 1 2 3 9 8 7 6 5 4 - после сортировки

Тоесть массив сортирован таким образом: что максимальные элементы расположены по убыванию между L и R.

Надеюсь понятно написал.

У меня такой алгоритм решения пришло в мысли:

Найти максимальный элемент от 0 до L
И максимальный от L до N
И сравнивать взять максимальное среди этих двух чисел, и сравнить с A[L + i] элементом если больше то меняем местами.
И на каждой итерации при поиске максимальногочисла, диапазон поиска от L до N уменщать таким образом от L + i до N, что бы не искать максимальное число среди уже сортированных.

Вот мое решение: КОД

Я там что то накосячил, теперь не могу понять в чем ошибка.

Может кто знает более правильное решение?
BK
Bahtiyar Kuvandykov
4 674
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>

using namespace std;

int main() {
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, l = 4, r = 8;
    sort(a + l, a + l + r - 2, greater<int>());
    copy(a, a + 10, ostream_iterator<int>(cout, " "));
    cout << endl;
}

Ну, а если тебе так нравиться изобретать велосипеды, то любой алгоритм сортировки массива легко можно применить для сортировки части массива:

#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

void buble_sort(int *a, int n) {
    for (int j = 0; j < n - 1; ++j) {
        for (int i = 0; i < n - j - 1; ++i) if (a[ i] < a[i + 1]) swap(a[ i], a[i + 1]);
    }
}

void sort_slice(int *a, int l, int r) { buble_sort(a + l, r - l + 2); }

int main() {
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, l = 4, r = 8;
    sort_slice(a, l, r);
    copy(a, a + 10, ostream_iterator<int>(cout, " "));
    cout << endl;
}
АБ
Александр Базанов
98 117
Лучший ответ
Bahtiyar Kuvandykov Спасибо)) Я пока еще плохо знаком с STL

Не понемаю что делает в данном случае greater<int>())
и что делает copy(a, a + 10, ostream_iterator<int>(cout, " "));
ra неправ. У тебя тут речь идет о нормальной сортировке при неправильной нумерации элементов массива, т. е. , мы хотим отсортировать r-l старших элементов в массиве, отображенном на обычный как
a[ i ] <==> b[ (i<l)?i:((i>r)?(r+i-l):(r-i+l))]
может, где-то на +-1 ошибся, но смысл именно такой: меняем нумерацию в массиве и сортируем, как обычный.. . Можно и с помощью stl итераторы заменить.
Vitali Gizbrekht
Vitali Gizbrekht
85 876
Bahtiyar Kuvandykov спасибо,

a[ i ] b[ (i < l) ? i : ((i > r) ? (r + i - l) : (r - i + l))]

Вы предлогаете 2 массива использовать ? или что?
Михаил Гагаркин Почему?

> любой алгоритм сортировки массива легко можно применить для сортировки части массива

0 1 2 3 4 5 6 7 8 9 -- индексы
8 1 9 2 0 5 7 3 4 6 -- значения

Элементы с индексами 0 - 3 сортирую по возрастанию, элементы с индексами 4 - 6 по убыванию, остальные снова по возрастанию, получаю:
1 2 8 9 7 5 0 3 4 6
Михаил Гагаркин А понял, невнимательно читал условие "максимальные элементы расположены по убыванию между L и R".
А остальные тогда как? Если бы Арсен написал не 0 1 2 3 4 ...а привел бы более осмысленный пример :-(