Быстрая сортировка
Быстрая сортировка (англ. quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n lg n) обменов при упорядочении n элементов).
Использование функцию qsort из библиотеки stdlib.h qsort( указатель_на_массив, количество_элементов, размер_элемента, функция_сравнения_элементов);
- функция_сравнения_элементов - является указателем на процедуру, поставляемую пользователем, которая сравнивает два элемента массива и возвращает значение, определяющее их отношение.
Метод основан на разделении массива на части. Общая схема такова:
- Из массива выбирается некоторый опорный элемент a[i].
- Запускается функция разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], слева от него, а все ключи, большие, либо равные a[i] - справа, теперь массив состоит из двух частей, причем элементы левой меньше элементов правой.
- Если в подмассивасивах более двух элементов, рекурсивно запускаем для них ту же функцию.
- В конце получится полностью отсортированная последовательность.
Рассмотрим алгоритм более детально.
Делим массив пополам. Входные данные: массив a[0]…a[N] и элемент p, по которому будет производиться разделение.
- Введем два указателя: i и j. В начале алгоритма они указывают, соответственно, на левый и правый конец последовательности.
- Будем двигать указатель i с шагом в 1 элемент по направлению к концу массива, пока не будет найден элемент a[i] >= p.
- Затем аналогичным образом начнем двигать указатель j от конца массива к началу, пока не будет найден a[j] ⇐ p.
- Далее, если i ⇐ j, меняем a[i] и a[j] местами и продолжаем двигать i,j по тем же правилам.
- Повторяем шаг 3, пока i ⇐ j.
Пример реализации на С/С++
#include <iostream> #include <stdlib.h> #include <time.h> using namespace std; template <class T> void quickSortR(T a[], long N) { // На входе - массив a[], a[N] - его последний элемент. long i = 0, j = N; // поставить указатели на исходные места T temp, p; p = a[ N>>1 ]; // центральный элемент // процедура разделения do { while ( a[i] < p ) i++; while ( a[j] > p ) j--; if (i <= j){ temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j--; } }while ( i<=j ); // рекурсивные вызовы, если есть, что сортировать if ( j > 0 ) quickSortR(a, j); if ( N > i ) quickSortR(a+i, N-i); } void main(){ srand(time(NULL)); const long SIZE=10; int ar[SIZE]; // до сортировки for(int i=0;i<SIZE;i++){ ar[i]=rand()%100; cout<<ar[i]<<"\t"; } cout<<"\n\n"; quickSortR(ar,SIZE-1); // после сортировки for(int i=0;i<SIZE;i++){ cout<<ar[i]<<"\t"; } cout<<"\n\n"; }
📌 Для тестирования скриптов, установщиков VPN, Python ботов рекомендуем использовать надежные VPS на короткий срок. Если вам нужна помощь с более сложными задачами, вы можете найти фрилансера, который поможет с настройкой. Узнайте больше о быстрой аренде VPS для экспериментов и о фриланс-бирже для настройки VPS, WordPress. 📌
💥 Подпишись в Телеграм 💥 и задай вопрос по сайтам и хостингам бесплатно!
7 Самых Популярных Статей
- Как запустить скрипты и веб-приложения на Python
- Что такое страны TIER 1,2,3
- 7 способов сравнения файлов по содержимому в Windows или Linux
- Установка и тестирование веб-панели HestiaCP
- Китайский VPN Shadowsocks простая установка и настройка
- top, htop, atop определение загрузки ОС (Load average, LA)
- Использование rsync в примерах