Необходимо написать функцию которая сортирует массив таким образом:
Путь есть массив из 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, что бы не искать максимальное число среди уже сортированных.
Вот мое решение: КОД
Я там что то накосячил, теперь не могу понять в чем ошибка.
Может кто знает более правильное решение?
Другие языки программирования и технологии
Сортировка
#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;
}
#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;
}
ra неправ. У тебя тут речь идет о нормальной сортировке при неправильной нумерации элементов массива, т. е. , мы хотим отсортировать r-l старших элементов в массиве, отображенном на обычный как
a[ i ] <==> b[ (i<l)?i:((i>r)?(r+i-l):(r-i+l))]
может, где-то на +-1 ошибся, но смысл именно такой: меняем нумерацию в массиве и сортируем, как обычный.. . Можно и с помощью stl итераторы заменить.
a[ i ] <==> b[ (i<l)?i:((i>r)?(r+i-l):(r-i+l))]
может, где-то на +-1 ошибся, но смысл именно такой: меняем нумерацию в массиве и сортируем, как обычный.. . Можно и с помощью stl итераторы заменить.
Bahtiyar Kuvandykov
спасибо,
a[ i ] b[ (i < l) ? i : ((i > r) ? (r + i - l) : (r - i + l))]
Вы предлогаете 2 массива использовать ? или что?
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
> любой алгоритм сортировки массива легко можно применить для сортировки части массива
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 ...а привел бы более осмысленный пример :-(
А остальные тогда как? Если бы Арсен написал не 0 1 2 3 4 ...а привел бы более осмысленный пример :-(
Похожие вопросы
- Изучил несколько простых алгоритмов сортировки, осталось изучить быструю и слияние, нужно ли вообще писать эти алгоритмы
- Сортировки, язык Си.
- C++ Сортировка в сортировке вектора экземпляров структуры
- Сортировка простыми вставками.
- Проблема с алгоритмом быстрой сортировкой С++
- Как написать макрос для Word 2003 чтобы выполнял сортировку чисел в квадратных скобках?
- Сортировка вставками и сортировка слиянием!
- Можно-ли использовать сортировку слиянием на массиве, состоящем из 10-ти элементов.
- Сортировка простыми вставками. Язык Си.
- как при сортировке одномерного массива оставить на месте неположительные элементы
Не понемаю что делает в данном случае greater<int>())
и что делает copy(a, a + 10, ostream_iterator<int>(cout, " "));