Как найти время работы и количество перестановок сортировки?
Всем доброго времени суток. Вопрос по алгоритмам сортировки на языке Си/C++.
Как найти время работы и количество перестановок сортировки (программы)?
Допустим, есть код сортировки «пузырьком» (обменом).
//код программы сортировки «Пузырьком»
#include <iostream>
void bubbleSort(int list[], int n)
{
for (int i=n-1; i>0; i--)
for (int k=0; k<i; k++)
if (list[k] > list[k+1])
std::swap(list[k], list[k+1]);
}
int main()
{
const int n=10;
int list[n];
std::cout << "Enter any " << n << " numbers:n";
for (int i=0; i<n; i++) std::cin >> list[i]; // ввод с клавиатуры
bubbleSort(list, n); // сортировка
std::cout << "nSorted Array:n";
for (int i=0; i<n; i++) std::cout << list[i] << " "; // вывод на экран
}
P.S. Судите как можно строго!
-
Вопрос заданболее трёх лет назад
-
1755 просмотров
Количество перестановок: оберните std::swap в функцию, которая будет считать количество вызовов:
struct CountingSwap
{
int count = 0;
template <typename T>
void operator()(T& lhs, T& rhs)
{
using std::swap;
swap(lhs, rhs);
++count;
}
};
int bubbleSort(int list[], int n)
{
CountingSwap swap;
for (int i=n-1; i>0; i--)
for (int k=0; k<i; k++)
if (list[k] > list[k+1])
swap(list[k], list[k+1]);
return swap.count;
}
Время: запомните время перед стартом сортировки, отсортируйте массив, запомните время после сортировки, вычтите из конца начало.
coliru.stacked-crooked.com/a/f04ed10ad976db8c
#include <time.h>
...
double t1 = clock(); // замеряем время до
bubbleSort(int list[], int n); // сортируем
double t2 = clock(); // замеряем время после
double t3 = (t2-t1) / CLOCKS_PER_SEC; // время в секундах
...
Пригласить эксперта
-
Показать ещё
Загружается…
24 мая 2023, в 21:54
100 руб./за проект
24 мая 2023, в 21:53
3000 руб./за проект
24 мая 2023, в 21:51
1 руб./за проект
Минуточку внимания
Прямой ответ на вопрос уже дан, но есть ощущение, что нужно многое уточнить.
Во-первых, нет смысла заниматься оптимизацией ради оптимизации.
Вот вам цитата из то ли Кнутта, то ли Дейкстры:
Преждевременная оптимизация — корень всех (или большинства) проблем в программировании.
Оптимизация должна преследовать строго определённые цели — улучшить производительность приложения в строго определённое количество раз (определяется нуждами пользователя) в строго определённых местах, в которых текущая производительность ниже той, которая необходима пользователю приложения. Реалии таковы, что оптимизацию можно производить тысячью разных способов: смена алгоритма, смена структур данных, смена средств языка, смена языка и так далее. Предела совершенству нет, поэтому любая оптимизация без чёткого запроса пользователя — это время, потраченное впустую. Если в приложении не возникает заметных провисаний, которые мешают приложению выполнять бизнес-функции, то никакая оптимизация в действительности не нужна.
Во-вторых, что касается оптимизаций в .Net. Для 90% хорошего кода оптимизации не нужны вовсе. Из оставшихся 10% в 90% случаев потребуется только оптимизация алгоритма. В оставшихся 10% от 10% могут потребоваться различные хаки, специфичные структуры данных и так далее. К последней категории относятся такие нагруженные продукты с большим мемори траффиком, как компиляторы, ReSharper и ему подобные вещи. Проводя оптимизацию через использование специфичных средств языка и структур данных, вы неизбежно снижаете сопровождаемость продукта. И тут естественно встает вопрос поиска баланса между читаемостью кода и выигрышем в производительности.
В-третьих, чтобы заниматься оптимизацией в .Net, нужно понимать, как работает компилятор, как работает Jit, нужно понимать, что разные версия Jit’а делают различные оптимизации вашего кода и ваш супер твик, который работает быстрее на вашей системе, в конечном счете под другой версией Jit’а может работать медленнее. Различные гениальные советы, которые тут и там всплывают в интернете, типа:
- Никогда не используйте
foreach
,for
— быстрее. - Вместо
List<>
используйте массивы, они быстрее - Не пользуйтесь
Linq
, он медленный - Разматывайте циклы (имеется в виду, например, возведение в степень, кратную 4, где в каждоё итерации происходит
a *= b
4 раза)
это всё от лукавого, ибо foreach
, List
и Linq
достаточно быстры в подавляющем большинстве случаев, а извращения, вроде разматывания циклов, могут убить оптимизацию компилятора, который и без вас бы мог этот цикл размотать.
В-четвёртых, заниматься бенчмаркингом в .Net сложно корректно по тем же причинам, что озвучены выше для занятия оптимизацией. Работа разных версий Jit, необходимость «прогревать» метод перед бенчмарком, особенности работы сборщика мусора и так далее — всё это осложняет получение честных данных замеров. Золотым стандартом в этой области является использование BenchmarkDotNet — крутейшей библиотеки для проведения бенчмарков, автором которой является Андрей Акиньшин из JetBrains, собственно, я так понимаю, продукт был написан для внутреннего пользования и в частности для разработки ReSharper. И даже этим фреймворком нужно пользоваться с головой.
Очень советую посмотреть вот это видео, в котором Андрей сам рассказывает о BenchmarkDotNet и проблемах замеров времени в .Net.
Также советую посмотреть совсем недавний доклад Сергея Теплякова на тему паттернов оптимизации в .Net приложениях.
В заключение хочу сказать, что если ваша цель — просто реализовать несколько алгоритмов сортировки и сравнить их производительность на разных наборах данных — то использование Stopwatch
может дать вам вполне неплохие результаты в рамках исследовательской задачи. Но если вопрос задан в контексте коммерческой разработки ПО, то тут уже появляется множество нюансов, касающихся целесообразности и корректности проводимых оптимизаций.
JustUnProgger 0 / 0 / 0 Регистрация: 24.06.2018 Сообщений: 7 |
||||
1 |
||||
Измерить время выполнения сортировки24.06.2018, 21:50. Показов 7568. Ответов 12 Метки нет (Все метки)
Всем привет) Хелпаните с задачей: Измерить время выполнения сортировки(в наносек-х), читал про RDTSC,но как правильно на си выполнить не понял. Посоветуйте что-нибудь,вроде прога не сложная,но я на этом застрял.
0 |
Ovederax 583 / 388 / 207 Регистрация: 30.04.2017 Сообщений: 723 |
||||
25.06.2018, 08:40 |
2 |
|||
JustUnProgger,
0 |
0 / 0 / 0 Регистрация: 24.06.2018 Сообщений: 7 |
|
25.06.2018, 09:24 [ТС] |
3 |
Ovederax, выводит постоянно 1ms. думаю это не совсем правильно Добавлено через 5 минут (2)или к примеру я домножу заранее на 1000 и сделаю сортировку 1000 раз и результат так как это инт не буду делить и он получится как бы 10-6 т.е микросек-ды
0 |
Ovederax 583 / 388 / 207 Регистрация: 30.04.2017 Сообщений: 723 |
||||
25.06.2018, 09:26 |
4 |
|||
Сообщение было отмечено JustUnProgger как решение РешениеJustUnProgger, хмм, у меня выводит «Real time for sorting 2017(ms)». Не по теме: Вы пользуетесь квантовым компьютером? Может поэтому так быстро… Этот код выводит 1 мс?
1 |
0 / 0 / 0 Регистрация: 24.06.2018 Сообщений: 7 |
|
25.06.2018, 09:29 [ТС] |
5 |
Ovederax, серьёзно? получается ваша программа из нескольких итерраций работает аж 2 сек-ды? может скинете полную прогу?)
0 |
0 / 0 / 0 Регистрация: 24.06.2018 Сообщений: 7 |
|
25.06.2018, 09:35 [ТС] |
6 |
Ovederax, вот,при том что сортировка стоит в цикле из 1000 итерраций Миниатюры
0 |
583 / 388 / 207 Регистрация: 30.04.2017 Сообщений: 723 |
|
25.06.2018, 09:41 |
7 |
получается ваша программа из нескольких итерраций работает аж 2 сек-ды? нет на 1000 итераций — работает 2000 мс -> 1 итерация в среднем 2мс
Ovederax, (1)а если я заранее на миллиард домножу?не получатся наносек-ды? Да получится, но точности то не будет, на конце будут просто нули висеть. Если нужно такой вывод то домнажайте и проверяте, чтобы результаты помещались в переменную типа long
вот,при том что сортировка стоит в цикле из 1000 итерраций Ну ё-маё, мой компьютер медленнннный Добавлено через 2 минуты
0 |
0 / 0 / 0 Регистрация: 24.06.2018 Сообщений: 7 |
|
25.06.2018, 09:52 [ТС] |
8 |
Ovederax, т.е. ваш вариант где заранее домножить на 1000. Добавлено через 38 секунд
0 |
583 / 388 / 207 Регистрация: 30.04.2017 Сообщений: 723 |
|
25.06.2018, 10:08 |
9 |
т.е. ваш вариант где заранее домножить на 1000. да, можно домножить на 10^9 — будут наносекунды.
и в цикле из 1000 итерраций следовательно результат получится в 10-6 т.е. это мкс=микросекунды а не мс,(1)верно же? Если поделите на тысячу иттераций — все равно ответ в мс будет.
(2)и он какбы примерно точный до миллионных? Точность clock() — 1 мс. Если нужны нс — ищите другой способ измерения временных промежутков.
0 |
0 / 0 / 0 Регистрация: 24.06.2018 Сообщений: 7 |
|
25.06.2018, 10:14 [ТС] |
10 |
Если поделите на тысячу иттераций — все равно ответ в мс будет. вы имели в виду если не поделите? потому что если поделю как раз таки и будет время прохождения сортировки Добавлено через 1 минуту
Если поделите на тысячу иттераций — все равно ответ в мс будет. а если я не делю время одного прохождения сортировки как раз таки умножается на 1000
0 |
583 / 388 / 207 Регистрация: 30.04.2017 Сообщений: 723 |
|
25.06.2018, 11:09 |
11 |
JustUnProgger, Вопросы это сложно. я не понимать…
0 |
JustUnProgger 0 / 0 / 0 Регистрация: 24.06.2018 Сообщений: 7 |
||||
25.06.2018, 23:32 [ТС] |
12 |
|||
Ovederax, можно задать последний вопрос?
CLOCK_PER_SEC — обычно 1000 для ПК — т.е. это мс. если не домножать и не делить на константу приращение времени выведится в мс? т.е
0 |
Ovederax 583 / 388 / 207 Регистрация: 30.04.2017 Сообщений: 723 |
||||
26.06.2018, 08:55 |
13 |
|||
если не домножать и не делить на константу приращение времени выведится в мс? Приращение времени будет выводится в тиках процессора. Константа нужна для того, чтобы переводить время из тиков в секунды. Эта константа различна для разных ОС. На Linux она может быть равна 1 000 000. Можно считать время в тиках, но переводить их во время(сек,мс) при выводе на экран.
Добавлено через 4 минуты The value of CLOCKS_PER_SEC shall be 1 million on XSI-conformant systems.
1 |
I have some code that generates 1000 numbers in an array and then sorts them:
import java.util.Arrays;
import java.util.Random;
public class OppgA {
public static void main(String[] args) {
int[] anArray;
anArray = new int[1000];
Random generator = new Random();
for(int i=0; i<1000; i++){
anArray[i] = (generator.nextInt(1000)+1);
}
Arrays.sort(anArray);
System.out.println(Arrays.toString(anArray));
}
}
Now I’m asked to calculate and print the time it took to sort the array. Any clues how I can do this? I really couldn’t find much by searching that could help me out in my case.
Thanks!
asked Aug 22, 2013 at 10:08
3
You can call (and store the result of) System.nanoTime()
before and after the call to Arrays.sort()
— the difference is the time spent in nanoseconds. That method is preferred over System.currentTimeMillis
to calculate durations.
long start = System.nanoTime();
Arrays.sort(anArray);
long end = System.nanoTime();
long timeInMillis = TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.NANOSECONDS);
System.out.println("Time spend in ms: " + timeInMillis);
But note that the result of your measurement will probably vary widely if you run the program several times. To get a more precise calculation would be more involved — see for example: How do I write a correct micro-benchmark in Java?.
answered Aug 22, 2013 at 10:13
assyliasassylias
320k80 gold badges658 silver badges779 bronze badges
0
Before sorting, declare a long which corresponds to the time before you start the sorting:
long timeStarted = System.currentTimeMillis();
//your sorting here.
//after sorting
System.out.println("Sorting last for:" + (System.currentTimeMillis() - timeStarted));
The result will return the milli seconds equivalent of your sorting.
As assylias commented you can also use System.nanoTime()
if you prefer precise measurements of elapsed time.
answered Aug 22, 2013 at 10:10
Jj TuibeoJj Tuibeo
7734 silver badges18 bronze badges
4
Proper microbenchmarking is done using a ready-made tool for that purpose, like Google Caliper or Oracle jmh. However, if you want a poor-man’s edition, follow at least these points:
- measure with
System.nanoTime()
(as explained elsewhere). Do not trust small numbers: if you get timings such as 10 microseconds, you are measuring a too short timespan. Enlarge the array to get at least into the milliseconds; - repeat the sorting process many times (10, 100 perhaps) and display the timing of each attempt. You are expected to see a marked drop in the time after the first few runs, but after that the timings should stabilize. If you still observe wild variation, you know something’s amiss;
- to avoid garbage collection issues, reuse the same array, but re-fill it with new random data each time.
answered Aug 22, 2013 at 10:17
Marko TopolnikMarko Topolnik
194k28 gold badges315 silver badges432 bronze badges
2
long beforeTime = System.currentTimeMillis();
// Your Code
long afterTime = System.currentTimeMillis();
long diffInMilliSeconds = afterTime- beforeTime;
answered Aug 22, 2013 at 10:11
before starting the calculation or exactly after generating the array you can use System#currentTimeMillis() to get the exact time and do the same exactly after completion of sorting and then find the difference.
Maroun
93.7k30 gold badges187 silver badges240 bronze badges
answered Aug 22, 2013 at 10:11
Bilbo BagginsBilbo Baggins
2,8899 gold badges52 silver badges76 bronze badges
do it this way :
long start = System.currentTimeMillis();
...
your sorting code
...
long end = System.currentTimeMillis();
long timeInMillis = end - start;
Hope that helps.
answered Aug 22, 2013 at 10:13
yogiamyogiam
1687 bronze badges
import java.util.Arrays;
import java.util.Random;
public class OppgA {
public static void main(String[] args) {
int[] anArray;
anArray = new int[1000];
Random generator = new Random();
for(int i=0; i<1000; i++){
anArray[i] = (generator.nextInt(1000)+1);
}
Date before = new Date();
Date after;
Arrays.sort(anArray);
after = new Date();
System.out.println(after.getTime()-before.getTime());
System.out.println(Arrays.toString(anArray));
}
}
answered Aug 22, 2013 at 10:13
FelquirFelquir
4311 gold badge4 silver badges12 bronze badges
This is not an ideal way. But this will work
long startingTime=System.currentTimeMillis();
Arrays.sort(anArray);
long endTime=System.currentTimeMillis();
System.out.println("Sorting time: "+(endTime-startingTime)+"ms");
Following can be the best way
long startingTime=System.nanoTime();
Arrays.sort(anArray);
long endTime=System.nanoTime();
System.out.println("Sorting time: "+(endTime-startingTime)+"ns");
answered Aug 22, 2013 at 10:19
In short, you can either extract our code to a method and than calculate the difference between the timestamps of start and end of that method or you can just run it in a profiler or an IDE and it will print the execution time
Ideally, you should not mix your business logic (array sorting in this case) with ‘metrics’ stuff.If you do need to measure execution time within the app, you can try to use AOP for that
Please refer to this post , which describes possible solutions in very detail
answered Aug 22, 2013 at 10:21
diydiy
3,5503 gold badges18 silver badges16 bronze badges
Сайт переезжает. Большинство статей уже перенесено на новую версию.
Скоро добавим автоматические переходы, но пока обновленную версию этой статьи можно найти там.
Задача сортировки массива заключается в том, чтобы расставить его элементы в определённом порядке (чаще всего — по неубыванию: каждый элемент должен быть больше или равен предыдущему).
Будет полезно вместе с описанем алгоритмов смотреть их визуализацию.
Сортировка пузырьком
Наш первый подход будет заключаться в следующем: обозначим за (n) длину массива и (n) раз пройдёмся раз пройдемся по нему, меняя два соседних элемента, если первый больше второго.
Как каждую итерацию максимальный элемент «всплывает» словно пузырек к концу массива — отсюда и название.
void bubble_sort(vector<int>& array) {
int n = (int) array.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - 1; j++) {
// сравниваем элемент со следующим
// и меняем местами, если следующий меньше
if (array[j] > arr[j + 1]) {
swap(array[j], array[j + 1]);
}
}
}
}
vector<int> a = {1, -3, 7, 88, 7};
bubble_sort(a);
for (auto elem : a) {
cout << elem << " ";
}
// -3 1 7 7 88
После (i) шагов алгоритма сортировки пузырьком последние ((i + 1)) чисел всегда отсортированы, а значит алгоритм работает корректно.
Упражнение. Алгоритм можно немного ускорить. Подумайте, какие лишние элементы мы перебираем. Как нужно изменить границы в двух циклах for
, чтобы не делать никаких бесполезных действий?
Сортировка выбором
Другим способом является сортировка выбором минимума (или максимума).
Чтобы отсортировать массив, просто (n) раз выберем минимум среди еще неотсортированных чисел и поставим его на свое место. На (i)-ом шаге будем искать минимум на отрезке ([i, n — 1]) и менять его местами с (i)-тым элементом, после чего отрезок ([0, i]) будет отсортирован.
Содержательная часть будет выглядеть так:
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
if (a[i] > a[j]) {
swap(a[j], a[i]);
}
}
}
Сортировка вставками
Определение. Префиксом длины (i) будем называть первые (i) элементов массива.
Тогда пусть на (i)-ом шаге у нас уже будет отсортирован префикс до (i)-го элемента. Чтобы этот префикс увеличить, нужно взять элемент, идущий после него, и менять с левым соседом, пока этот элемент наконец не окажется больше своего левого соседа. Если в конце он больше левого соседа, но меньше правого, то это будет означать, что мы правильно вставили этот элемент в отсортированную часть массива.
for (int i = 1; i < n; i++) {
for (int j = i; j > 0; j--) {
if (a[j - 1] < a[j]) {
break;
}
swap(a[j], a[j - 1]);
}
}
Сортировка подсчетом
Предыдущие три алгоритма работали с массивами, в которых лежат абсолютно любые объекты, которые можно сравнивать: любые числа, строки, пары, другие массивы — почти все что угодно.
Но особых случаях, когда элементы принадлежат какому-то маленькому множеству, можно использовать другой алгоритм — сортировку подсчетом.
Пусть, например, нам гарантируется, что все числа натуральные и лежат в промежутке от (1) до (100). Тогда есть такой простой алгоритм:
-
Создадим массив размера (100), в котором будем хранить на (k)-ом месте, сколько раз число (k) встретилось в этом массиве.
-
Пройдемся по всем числам исходного массива и увеличим соответствующее значение массива на (1).
-
После того, как мы посчитали, сколько раз каждое число встретилось, можно просто пройтись по этому массиву и вывести (1) столько раз, сколько встретилась (1), вывести (2) столько раз, сколько встретилась (2), и так далее.
Время работы такого алгоритма составляет (O(M+N)), где (M) — число возможных значений, (N) — число элементов в массиве. Сейчас мы расскажем, что же это означает.
О-нотация
Часто требуется оценить, сколько времени работает алгоритм. Но тут возникают проблемы:
- на разных компьютерах время работы всегда будет слегка отличаться;
- чтобы измерить время, придётся запустить сам алгоритм, но иногда приходится оценивать алгоритмы, требующие часы или даже дни работы.
Зачастую основной задачей программиста становится оптимизировать алгоритм, выполнение которого займёт тысячи лет, до какого-нибудь адекватного времени работы. Поэтому хотелось бы уметь предсказывать, сколько времени займёт выполнение алгоритма ещё до того, как мы его запустим.
Для этого сначала попробуем оценить число операций в алгоритме. Возникает вопрос: какие именно операции считать. Как один из вариантов — учитывать любые элементарные операции:
- арифметические операции с числами:
+, -, *, /
- сравнение чисел:
<, >, <=, >=, ==, !=
- присваивание:
a[0] = 3
При этом надо учитывать, как реализованы некоторые отдельные вещи в самом языке. Например, в питоне срезы массива (array[3:10]
) копируют этот массив, то есть этот срез работает за 7 элементарных действий. А swap
, например, может работать за 3 присваивания.
Упражнение. Попробуйте посчитать точное число сравнений и присваиваний в сортировках пузырьком, выбором, вставками и подсчетом в худшем случае (это должна быть какая формула, зависящая от (n) — длины массива).
Чтобы учесть вообще все элементарные операции, ещё надо посчитать, например, сколько раз прибавилась единичка внутри цикла for
. А ещё, например, строчка n = len(array)
— это тоже действие. Поэтому даже посчитав их, сразу очевидно, какой из этих алгоритмов работает быстрее — сравнивать формулы сложно. Хочется придумать способ упростить эти формулы так, чтобы:
- не нужно было учитывать много информации, не очень сильно влияющей на итоговое время;
- легко было оценивать время работы разных алгоритмов для больших чисел;
- легко было сравнивать алгоритмы на предмет того, какой из них лучше подходит для тех или иных входных данных.
Для этого придумали (O)-нотацию — асимптотическое время работы вместо точного (часто его ещё называют асимптотикой).
Определение. Пусть (f(n)) — это какая-то функция. Говорят, что алгоритм работает за (O(f(n))), если существует число (C), такое что алгоритм работает не более чем за (C cdot f(n)) операций.
В таких обозначениях можно сказать, что
- сортировка пузырьком работает за (O(n^2));
- сортировка выбором работает за (O(n^2));
- сортировка вставками работает за (O(n^2));
- сортировка подсчетом работает за (O(n + m)).
Это обозначение удобно тем, что оно короткое и понятное, а также оно не зависит от умножения на константу или прибавления константы. Например, если алгоритм работает за (O(n^2)), то это может значить, что он работает за (n^2), за (n^2 + 3), за (frac{n(n-1)}{2}) или даже за (1000 cdot n^2 + 1) действие. Главное — что функция ведет себя как (n^2), то есть при увеличении (n) (в данном случае это длина массива) он увеличивается как некоторая квадратичная функция. Например, если увеличить (n) в 10 раз, время работы программы увеличится приблизительно в 100 раз.
Все рассуждения про то, сколько операций в swap
или считать ли отдельно присваивания, сравнения и циклы — отпадают. Каков бы ни был ответ на эти вопросы, они меняют ответ лишь на константу, а значит асимптотическое время работы алгоритма никак не меняется.
Первые три сортировки именно поэтому называют квадратичными — они работают за (O(n^2)). Сортировка подсчетом может работать намного быстрее — она работает за (O(n + m)), а если в задаче (M leq N), то это вообще линейная функция (O(n)).
Упражнение. Найдите асимптотику данных функций, маскимально упростив ответ (например, до (O(n)), (O(n^2)) и т. д.):
- (frac{N}{3})
- (frac{N(N-1)(N-2)}{6})
- (1 + 2 + 3 + ldots + N)
- (1^2 + 2^2 + 3^2 + ldots + N^2)
- (log{N} + 3)
- (179)
- (10^{100})
Упражнение. Найдите асимптотическое время работы данных функций:
def f(n):
s = 0
for i in range(n):
for j in range(n):
s += i * j
return s
def g(n):
s = 0
for i in range(n):
s += i
for i in range(n):
s += i * i
return s
def h(n):
if n == 0:
return 1
return h(n - 1) * n
Упражнение. Найдите лучшее время работы алгоритмов, решающих данные задачи:
- Написать числа от (1) до (n).
- Написать все тройки чисел от (1) до (n).
- Найти разницу между максимумом и минимумом в массиве.
- Найти число единиц в бинарной записи числа (n).
Сортировки за (O(n log n))
Сортировка очень часто применяется как часть решения олимпиадных задач. В таких случаях обычно не пишут её заново, а используют встроенную.
Пример на Python:
a = [1, 5, 10, 5, -4]
a.sort()
Пример на C++:
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
vector<int> v = {1, 5, 10, 5, -4};
sort(v.begin(), v.end());
}
В разных языках она может быть реализована по-разному, но везде она работает за (O(n log n)), и, обычно, неплохо оптимизирована. Далее мы опишем два подхода к её реализации.
Сортировка слиянием
Найти количество пар элементов (a) и (b) в отсортированном массиве, такие что (b — a > K).
Наивное решение: бинарный поиск. Будем считать, что массив уже отсортирован. Для каждого элемента (a) найдем первый справа элемент (b), который входит в ответ в паре с (a). Нетрудно заметить, что все элементы, большие (b), также входят в ответ. Итоговая асимптотика (O(nlog n)).
А можно ли быстрее?
Да, давайте перебирать два указателя — два индекса (first) и (second). Будем перебирать (first) просто слева направо и поддерживать для каждого (first) первый элемент справа от него, такой что (a[second] — a[first] > K) как (second). Тогда в пару к (a=a[first]) подходят ровно (n-second) элементов массив начиная с (second).
int second = 0, ans = 0;
for (int first = 0; first < n; ++first) {
while (second != n && a[second] - a[first] <= r) {
second++;
}
ans += n - second;
}
За сколько же работает это решение? С виду может показаться, что за (O(n^2)), но давайте посмотрим сколько раз меняется значение переменной (second). Так как оно изначально равняется нулю, только увеличивается и не может превысить (n), то суммарно операций мы сделаем (O(n)).
Это называется метод двух указателей — так как мы двигаем два указателя first и second одновременно слева направо по каким-то правилам. Обычно его используют на одном отсортированном массиве.
Давайте разберем еще примеры.
Слияние
Еще пример двух указателей на нескольких массивах.
Пусть у нас есть два отсортированных по неубыванию массива размера (n) и (m). Хотим получить отсортированный массив размера (n + m) из исходных.
Пусть первый указатель будет указывать на начало первого массива, а второй, соответственно, на начало второго. Из двух текущих элементов, на которые указывают указатели, выберем наименьший и положим на соответствующую позицию в новом массиве, после чего сдвинем указатель. Продолжим этот процесс пока в обоих массивах не закончатся элементы. Тогда код будет выглядеть следующим образом:
int a[n + 1], b[m + 1], res[n + m];
a[n] = INF; // Создаем в конце массива фиктивный элемент, который заведомо больше остальных
b[m] = INF; // Чтобы избежать лишних случаев
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int j = 0; j < m; ++j) {
cin >> a[j];
}
int i = 0, j = 0;
for (int k = 0; k < n + m; ++k) {
if (a[i] < b[j]) {
res[k] = a[i];
i++;
} else {
res[k] = b[j];
j++;
}
}
Итоговая асимптотика: (O(n + m)).
Сортировка слиянием
Давайте подробно опишем как использовать операцию слияния для сортировки за (O(nlog n)).
Пусть у нас есть какой-то массив.
int a[8] = {7, 2, 5, 6, 1, 3, 4, 8};
Сделаем такое предположение. Пусть мы уже умеем как-то сортировать массив размера (n). Тогда научимся сортировать массив размера (2n). Давайте разобьем наш массив на две половины, отсортируем каждую из них, а после это сделаем слияние двух массивов, которое мы научились делать за (O(n)) в данных условиях. Также заметим, что массив размера (1) уже отсортирован, тогда мы можем делать это процедуру рекурсивно. Тогда для данного массива (a) это будет выглядеть следующим образом:
// (7 2 5 6 1 3 4 8)
// (7 2 5 6)(1 3 4 8)
// (7 2)(5 6)(1 3)(4 8)
// (2 7)(5 6)(1 3)(4 8)
// (2 5 6 7)(1 3 4 8)
// (1 2 3 4 5 6 7 8)
#include // Воспользуемся встроенной функцией merge
void merge_sort(vector &v, int l, int r) { // v - вектор, который хотим отсортировать
if (r - l == 1) { // l и r - полуинтервал, который хотим отсортировать
return;
}
int mid = (l + r) / 2;
merge_sort(v, l, mid);
merge_sort(v, mid, r);
vector temp(r - l); // временный вектор
merge(v.begin() + l, v.begin() + mid, v.begin() + mid, v.begin() + r, c.begin());
for (int i = 0; i < r - l; ++i) {
v[i + l] = temp[i];
}
return;
}
Так сколько же работает это решение?
Пускай (T(n)) — время сортировки массива длины (n), тогда для сортировки слиянием справедливо (T(n)=2T(n/2)+O(n)) (O(n)) — время, необходимое на то, чтобы слить два массива длины n. Распишем это соотношение:
(T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n)=ldots=T(1)+log(n)O(n)=O(nlog(n)).)
Количество инверсий
Пусть у нас есть некоторая перестановка (a). Инверсией называется пара индексов (i) и (j) такая, что (i < j) и (a[i] > a[j]).
Найти количество инверсий в данной перестановке.
Очевидно, что эта задача легко решается обычным перебором двух индексов за (O(n^2)):
int a[n], ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (a[i] > a[j]) {
ans++;
}
}
}
cout << ans << endl;
Внезапно эту задачу можно решить используя сортировку слиянием, слегка модифицируя её. Оставим ту же идею. Пусть мы умеем находить количество инверсий в массиве размера (n), научимся находить количество инверсий в массиве размера (2n).
Заметим, что мы уже знаем количество инверсий в левой половине и в правой половине массива. Осталось лишь посчитать число инверсий, где одно число лежит в левой половине, а второе в правой половине. Как же их посчитать?
Давайте подробнее рассмотрим операцию merge левой и правой половины (которую мы ранее заменили на вызов встроенной функции merge). Первый указатель указывает на элемент левой половины, второй указатель указывает на элемент второй половины, мы смотрим на минимум из них и этот указатель вдигаем вправо.
Рассмотрим число (A) в левой половине. В скольки инверсиях между половинами оно участвует? В стольки, сколько чисел в правой половине меньше, чем оно. Знаем ли мы это количество? Да! Ровно в тот момент, когда мы число (A) вносим в слитый массив, второй указатель указывает на первое число в правой половине, которое больше чем (A).
Значит в тот момент, когда мы добавляем число (A) из левой половины, к ответу достаточно прибавить индекс второго указателя (минус начало правой половины). Так мы учтем все инверсии между половинами.
Быстрая сортировка
Быстрая сортировка заключается в том, что на каждом шаге мы находим опорный элемент, все элементы, которые меньше его кидаем в левую часть, остальные в правую, а затем рекурсивно спускаемся в обе части.
void quicksort(int l, int r){
if (l < r){
int index = (l + r) / 2; /* index - индекс опорного элемента для
начала сделаем его равным середине отрезка*/
index = divide(l, r, index); /* divide - функция разбивающие элементы
на меньшие и больше/равные a[index],
при этом функция возвращает границу разбиения*/
quicksort(l, index);
quicksort(index + 1, r);
}
}
Давайте оценим асимптотику данной сортировки. На случайных данных она работает за (O(NlogN)) , так как каждый раз мы будем делить массив на две примерно равные части, то есть суммарно размер рекурсии будет около логарифма и при этом на каждом этапе рекурсии мы просмотрим не более, чем размер массива. Однако можно легко найти две проблемы, одна — одинаковые числа, а вторая — если вдруг середина — минимум или максимум.
Существуют несколько выходов из этой ситуации :
-
Давайте если быстрая сортировка работает долго, то запустим любую другую сортировку за (NlogN).
-
Давайте делить массив не на две, а на три части(меньше, равны, больше).
-
Чтобы избавиться от проблемы с максимумом/минимумом в середине, давайте брать случайный элемент.
Поиск (k)-ой порядковой статистики за (O(N))
Пусть дан массив (A) длиной (N) и пусть дано число (K). Задача заключается в том, чтобы найти в этом массиве (K)-ое по величине число, т.е. (K)-ую порядковую статистику.
Давайте поймем, что в быстрой сортировке мы можем узнать, сколько элементов меньше данного, тогда рассмотрим три случая
-
количество чисел, меньше данного = (k — 1), тогда наше число — ответ.
-
количество чисел, меньше данного >= (k), тогда спускаемся рекурсивно в левую часть и ищем там ответ.
-
количество чисел, меньше данного < (k), спускаемся в правую ищем ((k) — левая — 1) — ое число.
За сколько же это работает, из быстрой сортировки мы имеем, что размер убывает приблизительно в 2 раза, то есть мы имеем сумму (sum_{k=1}^n {2 ^ k} = {2^{k+1}-1}) что в нашем случае это максимум равно (2 * N — 1), то есть (O(N)).
Также в C++ эта функция уже реализована и называется nth_element
.