Инструменты пользователя

Инструменты сайта


bystraja_sortirovka

Различия

Показаны различия между двумя версиями страницы.

Ссылка на это сравнение

bystraja_sortirovka [2020/06/13 13:45] (текущий)
Строка 1: Строка 1:
 +====== Быстрая сортировка ======
 +
 +{{htmlmetatags>
 +metatag-description=(Пример реализации на С/С++ быстрой сортировки.)
 +}}
 +
 +**Быстрая сортировка** (англ. quicksort), часто называемая **qsort** по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n lg n) обменов при упорядочении n элементов).
 +
 +<file>
 +Использование функцию qsort из библиотеки stdlib.h
 +
 +qsort( указатель_на_массив, количество_элементов, размер_элемента, функция_сравнения_элементов);
 +</file>
 +  *** функция_сравнения_элементов** - является указателем на процедуру, поставляемую пользователем, которая сравнивает два элемента массива и возвращает значение, определяющее их отношение.
 +
 +  * [[http://ru.wikibooks.org/wiki/%D0%AF%D0%B7%D1%8B%D0%BA_%D0%A1%D0%B8_%D0%B2_%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D0%B0%D1%85/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BD%D0%B0_%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D0%B5_qsort|Язык Си в примерах/Сортировка на основе 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.
 +
 +====== Пример реализации на С/С++ ======
 +<file>
 +#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";
 +}
 +</file>
  
bystraja_sortirovka.txt · Последнее изменение: 2020/06/13 13:45 (внешнее изменение)