Шейкерная (перемешиванием) сортировка

Шейкерную сортировку часто называют «двунаправленная пузырьковая сортировка», что достаточно точно описывает процесс работы алгоритма. Это действительно альтернативная версия рассмотренного ранее метода. Перестановка элементов в шейкерной сортировке выполняется аналогично пузырьковой сортировке, т. е. два соседних элемента при необходимости меняются местами. Отличие заключается в том, что упорядочение происходит не строго в одном направлении (от меньшего индекса к большему), как в случае пузырьковой сортировки, а вначале от меньшего к большему, затем наоборот.

Рассмотрим листинг шейкерной сортировки для упорядочения массива по убыванию:

// заполнение массива a из n элементов

// ...

int left = 1, right = n - 1, i;

while (left <= right){

for(i = right; i >= left; i--)

     if (a[i-1] < a[i]) swap(a[i], a[i-1]);

left++;

for(i = left; i <= right; i++)

     if (a[i-1] < a[i]) swap(a[i], a[i-1]);

right--;

}

// ...

Сортировка подсчетом

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

Задача №99. Мегасортировка

В файле записан МИЛЛИОН целых неотрицательных чисел, от 1 до 1000

Выведите эти числа в порядке убывания.

Решение

При относительно небольшом количестве чисел в файле задача решается просто – всё считать в массив, а затем его отсортировать. Это решение, скорее всего, не сможет успешно пройти тесты при размере массива N ≥ 30000. Даже с использованием функции быстрой сортировки sort, описанной в главе «Рекурсия», решение не сможет быстро упорядочить столь большой объем данных и вывести его в файл.

#include <fstream>

#include <algorithm>

#define N 1000000

using namespace std;

int a[N];

bool comp(int a, int b) { // функция-компаратор

return a > b;         // по убыванию, а < b – по возрастанию

}

 

int main() {

ifstream fin("input.txt");

ofstream fout("output.txt");

for(int i = 0; i < N; i++) fin >> a[i];

sort(a, a + N, comp); //сортируем по убыванию с компаратором

for(int i = 0; i < N; i++) fout << a[i] << ' ';

}

В данном случае лучший способ произвести «мегасортировку[21]» - вообще ничего не сортировать и не хранить в памяти миллион чисел. На самом деле нам потребуется всего лишь 1000, которые мы будем использовать как счётчики. Т.е. a_i будет хранить величину, как часто встречается во входном наборе число i.

#include <fstream>

using namespace std;

int main() {

ifstream fin("input.txt");

ofstream fout("ouput.txt");

int n, i, a[1001] = {0,};

for(fin >> n; n--; ){

   fin >> i;

   a[i]++;

}

for(i = 1000; i--;)

   for(; a[i]--; )

      fout << i << ' ';

}

Такой способ упорядочения данных называется сортировкой подсчетом.

Сортировка выбором

Сортировка выбором является не только одной из самых простых в реализации, но и, пожалуй, самой интуитивно понятной. Если попросить человека упорядочить несколько объектов по размеру, например солдат в шеренге по росту, вероятнее всего он будет действовать следующим образом:

1. Выбрать самого высокого солдата, поставить его на первое место, обменяв местами с уже стоящим там солдатом.

2. Выбрать второго по росту солдата из оставшихся после первого. Обменять его местами с солдатом, который стоит на второй позиции.

3. Выбрать следующего по росту из оставшихся после второго. Обменять его местами с третьим и т.д.

Рассмотрим листинг одной из реализаций сортировки выбором (по убыванию):

// заполнение массива a из n элементов

// ...

int key;

for (int i = 0; i < n-1; i++){

key = i;

for (int j = i+1; j < n; j++)

     if (a[j] < a[key]) key = j;

if (key != i) swap(a[i], a[key]);

}

// ...

Разные задачи с сортировками

Задача №100.  Арифметическая прогрессия – 2 (acmp.ru)

Задана последовательность натуральных чисел из диапазона [1, 2147483647]. Необходимо определить: можно ли выстроить эти числа в отрезок арифметической прогрессии. При необходимости порядок чисел в последовательности можно изменять.

Требуется написать программу для решения этой задачи.

Входные данные

Входной файл INPUT.TXT содержит последовательность натуральных чисел. Количество чисел в последовательности может быть от 2 до 100 000. Числа в файле разделены пробелами или символами перехода на новую строку.

Выходные данные

Выходной файл OUTPUT.TXT должен содержать либо «Yes» в случае положительного ответа, либо «No» в противоположном случае.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	80  50  10  30  70  40  20  60  90	Yes
2	1  2  3  5	No

Решение

Воспользуемся функцией сортировки, описанной в разделе «Быстрая сортировка» главы «Рекурсия»

#include <fstream>

#include <algorithm>            //описание sort

#define SIZE 100001

using namespace std;

int main(){

ifstream cin("input.txt");

ofstream cout("output.txt");

int n = 0, a[SIZE];

while (cin >> a[n++]);

sort(a, a + n);

bool ans = true;

int d = a[1] - a[0];

for (int i = 1; i < n-1; i++)

   if (a[i+1]-a[i] != d) {ans = false; break;}

cout << (ans ? "Yes" : "No");

return 0;

}

Задача №101.  Кризисный бизнес (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Петр Васильевич Колошин никогда не был пугливым человеком и всегда отличался спокойствием и прозорливостью, особенно в сфере мировых политических и экономических процессов. Однако, не смотря ни на что, Петр Васильевича очень недооценил последствия мирового финансового кризиса и как следствие был уволен пару недель назад с должности сетевого администратора одной большой и серьезной организации.

Не смотря ни на что, Петр Васильевич не отчаялся и решил начать свое дело. Тщательно проанализировав бизнес-климат в своем регионе, Петр Васильевич пришел к выводу, что наиболее целесообразным будет открыть новый таксопарк. Первое с чего решил начать новоиспеченный бизнесмен – это закупить автомобили. За все время работы Петр Васильевичу удалось накопить сумму S, которую он готов потратить на закупку машин.

В городе, в котором живет Петр Васильевич, есть только один автосалон. Известно, что в этом автосалоне выставлено на продажу N автомобилей, причем установлено, что стоимость i-го автомобиля равняется A_i. Вашей задачей является помочь еще неопытному бизнесмену Петр Васильевичу приобрести максимальное количество автомобилей, потратив сумму не более S.

Входные данные

В первой строке находится два целых положительных числа разделенные одиночным пробелом – это числа N( 1 ≤ N ≤ 100) и S ( 1 ≤ S ≤ 10⁹) соответственно.

Вторая строка содержит ровно N чисел A_i (1 ≤ A_i ≤ 10⁹) , которые описывают стоимость соответствующих автомобилей. Все числа в строке разделены одиночными пробелами.

Выходные данные

Выведите одно целое число – максимальное количество автомобилей, которые сможет приобрести Петр Иванович на сумму не более чем S.

Примеры

№	Ввод	Вывод
1	5 30 15 5 11 10 12	3
2	6 18 5 10 1 2 1 20	4

Решение

#include <iostream>

#include <algorithm>

using namespace std;

long long n, a[100], s, i;

int main(){

cin >> n >> s;

for(i = 0; i < n; i++)

   cin >> a[i];

sort(a, a + n);

for(i = 0; i < n && (s -= a[i]) >= 0; i++);

cout << i;

}

Задача №102.  Минимальная сумма (e-olimp)

(Лимит времени 0.1 секунда. Память 32 Мб)

Имеются два массива натуральных чисел a_1..n и b_1..n.

Найти перестановку i1, i2, ..., in чисел 1, 2, ..., n, для которой сумма

                   a₁ * b_i1 + ... + a_n * b_in

минимальна. В перестановку каждое число должно входить только один раз.

Входные данные

В первой строке находится количество элементов n (n ≤ 100) в массивах. Во второй строке заданы значения элементов первого массива, а в третьей - второго. Значения элементов массивов не превышают 10⁶.

Выходные данные

Вывести минимальное значение искомой суммы.

Пример

Ввод	Вывод
5 7  2  4  3  10 5  11  6  9  6	165

Решение

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

Это легко доказать – произведение двух чисел будет увеличиваться быстрее, если числа увеличиваются равномерно. Например, если в произведении один из множителей увеличить на 2, то значение произведения будет меньше, чем если каждый множитель увеличить на 1.

Далее можно доказать по индукции

#include <iostream>

#include <algorithm>                 // функция sort

using namespace std;

bool comp(int x, int y) {return x > y;} //компаратор по убыванию

int main(){

long long n, a[100], b[100], i, s = 0;

cin >> n;

for(i = 0; i < n; i++)

   cin >> a[i];

for(i = 0; i < n; i++)

   cin >> b[i];

sort(a, a + n);             // сортируем a по возрастанию

sort(b, b + n, comp);       // затем b по убыванию

for(i = 0; i < n; i++)

   s += a[i]*b[i];

cout << s << endl;

}

В этой задаче мы впервые использовали компаратор[22] для быстрой сортировки по убыванию. Также можно было воспользоваться любой сортировкой по возрастанию, а затем функцией reverse из билиотеки algorithm, которая переставляет элементы набора в обратном порядке

Задача №103.  Аудитории

Симферополь, II этап, 2008 г

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

В частности, имеется N групп студентов A₁, A₂…A_N. Каждая группа со своим преподавателем, которому тоже нужен компьютер на рабочем месте. Университет готов предоставить для них M аудиторий, в каждой из которых имеется B₁, B₂, … , B_M компьютеров соответственно.

Помогите рассадить как можно больше людей по аудиториям.

Помните, что группа должна находиться целиком в одной аудитории. Две группы в одной аудитории находиться не могут.

Входные данные

В первой строке записаны два натуральных числа N и M, не превышающие 1000, разделённые пробелом.

Во второй строке N натуральных числел A₁, A₂…A_N – количество студентов в каждой группе. Все числа не больше 100.

В третьей строке M натуральных чисел B₁, B₂, … , B_M – число компьютеров в аудиториях.

Выходные данные

Nчисел C₁, C₂, …C_N – номера аудиторий C_i, куда должна отправиться группа студентов номер i. Если для группы найти аудиторию не удалось, то C_i = 0. Если допустимых распределений несколько, выведите любое из них.

Пример

Ввод	Вывод
3 4 5 3 4 3 5 3 6	4 0 2

Пояснение к примеру: 1-я группа студентов должна отправиться в 4-ю аудиторию. 3-я группа пойдёт во 2-ю. А второй группе место найти не удалось.

Решение

Задача сама по себе не очень сложная, но требует умения аккуратно писать код. Иначе в нем можно запутаться.

Используем контейнер «пара» pair, с помощью которого для каждой аудитории запомним её номер, и также для группы людей запомним её номер.

Две разных пары при сортировке упорядочиваются по первому элементу в паре.

#include <iostream>

#include <algorithm>      // sort и reverse

using namespace std;

int n, m, i, j;

pair<int, int> a[1000], b[1000]; // пары «к-во людей, номер группы»

                          //и «к-во компьютеров, номер кабинета»

bool comp(int x, int y) {return x > y;} // компаратор по убыванию

 

int main(){

cin >> n >> m;

for(i = 0; i < n; i++){ // вводим группы

  cin >> a[i].first; // количество студентов

  a[i].first++;      // с преподавателем

  a[i].second = i + 1; // и номер группы

}

for(j = 0; j < m; j++){ // вводим аудитории

  cin >> b[j].first; // количество компьютеров

  b[j].second = j + 1; // и номер аудитории

}  

sort(a, a + n, comp);  // сортировка в обратном

sort(b, b + m, comp);  // порядке (по убыванию)

for(i = 0, j = 0; i<n; i++){

  if(a[i].first <= b[j].first) { // если группу можно рассадить

      a[i].first = b[j].second; // запоминаем номер кабинета

      j++;                 // переходим к след. аудитории

  } else a[i].first = 0;   // иначе рассадить нельзя

  swap(a[i].first, a[i].second); // сохраняем в 1 элементе

}                            // группу, а во 2 аудиторию

sort(a, a + n);        // опять сортируем по номерам групп

for(i = 0; i < n; i++)

  cout << a[i].second << ' ';

}

Задача №104.  Музей (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

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

Входные данные

В первой строке записано натуральное число N (N < 10⁵) – количество зафиксированных посетителей в музее в течении суток. Далее, идут N строк с информацией о времени визитов посетителей: в каждой строке располагается отрезок времени посещения в формате «ЧЧ:ММ ЧЧ:ММ» (00:00 ≤ ЧЧ:ММ ≤ 23:59).

Выходные данные

Вывести одно целое число — максимальное количество посетителей, одновременно находящихся в музее.

Пример

Ввод	Вывод
6 09:00 10:07 10:20  11:35 12:00  17:00 11:00  11:30 11:20  12:30 11:30  18:15	4

Решение

Учитывая большой объем вводимых данных, воспользуемся вместо потоковых операций cin и cout функции printf и scanf, которые работают быстрее. Идея решения состоит в следующем: переведём всё введенное время прихода и ухода в минуты, затем отсортируем по возрастанию.

#include <cstdio>

#include <algorithm>

#define SIZE 100000

using namespace std;

int main() {

int n, hh, mm, p[SIZE], u[SIZE], k, i, j, mx;

char c;

scanf("%d", &n);

for(i=0; i<n; i++){              // считываем данные

   scanf("%d%c%d", &hh, &c, &mm);

   p[i] = hh * 60 + mm;         // время прихода в минутах

   scanf("%d%c%d", &hh, &c, &mm);

   u[i] = hh * 60 + mm;         // время ухода в минутах

}

sort(p, p + n);                  // сортируем по возрастанию

sort(u, u + n);

i = j = mx = k = 0;

while(i<n && j<n){               // для каждого посетителя

   while(p[i]<=u[j] && i<n) i++; // считаем, сколько еще

   k = i - j;                   // не ушли

   if(k > mx) mx = k;

   j++;

}

printf("%d", mx);

}

Более быстрое решение можно получить с использованием дерева отрезков.

Задача №105.  Сплоченная команда

(Время: 0,5 сек. Память: 16 Мб)

Источник: Московская городская олимпиада по информатике 2005 г.

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

Ваша задача состоит в том, чтобы помочь сделать правильный выбор из N человек, для каждого из которых известен его ПП.

Входные данные

В первой строке записано целое число N (0 ≤ N ≤ 30000). В следующей строке записано N целых чисел P_i (0 ≤ P_i ≤ 60000), представляющих собой ПП соответствующего игрока.

Выходные данные

Выведите максимально возможную сумму ПП игроков сплоченной команды.

Примеры

№	Ввод	Вывод
1	4 1 5 3 3	11
2	5 100 20 20 20 20	120

Пояснение к примеру №1: самая сильная сплоченная команда должна содержать игроков 5+3+3

Решение

Вначале отсортируем введённый пользователем массив по возрастанию. Пусть i – номер самого слабого, а j – номер самого сильного спортсмена в такой сплочённой команде. Легко доказать, что номера спортсменов в искомой команде идут подряд. Если есть спортсмен с номером k< i-1 (значит P_k ≤ P_i), который включен в команду, и команда остаётся сплочённой, т.е.

то можно взять любой номер t, такой, что k < t < i (значит P_k ≤ P_t ≤ P_i). Очевидно, если заменить игрока с номером k на игрока с номером t, то команда будет сильнее и продолжит оставаться сплочённой. Аналогично доказывается для k > j+1.

Для определения наибольшего возможного ПП сплоченной команды применим бинарный поиск в массиве. Возьмём в качестве первой сплочённой команды двух первых спортсменов в массиве i=0, j=1. Если текущая команда остаётся сплочённой, увеличиваем j на 1, иначе i на 1. Для каждой сплочённой команды находим её суммарный ПП и из них выбираем максимальный. Продолжаем, пока j < n.

Для того чтобы было проще вычислять суммы на любом наборе подряд идущих элементов исходного массива, заменим каждый элемент Pi величиной Si – суммой всех элементов от начального до i-го включительно. Такой подход называется суммой на префиксах. Например, для

i	0	1	2	3
Pi	1	2	3	7
Si	1	3	6	13

Сумма от i-го до j-го элемента будет равна

а сам i-ый элемент соответственно

#include <iostream>

#include <algorithm>

#define S(t) (0 <= t && t < n ? p[t] : 0)

using namespace std;

 

int main () {

int n, p[30001], i, j, r;

cin >> n;

for(i = 0; i < n; i++)

   cin >> p[i];

 

sort(p, p + n);                       // сортируем P

for(i = 1; i < n; i++)                // заменяем Pi

   p[i] += p[i-1];                   // суммами Si

r = p[0];

   

for(i = 0, j = 1; j < n;)

   if(S(j)-S(j-1) <= S(i+1)-S(i-1)){ // команда сплоченная

       r = max(r, S(j) - S(i-1));

       j++;

   } else i++;

cout << r;

}