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

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


bystraja_sortirovka

Различия

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

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

bystraja_sortirovka [2010/11/12 15:00] (текущий)
Строка 1: Строка 1:
 +====== Быстрая сортировка ======
 +**Быстрая сортировка** (англ. 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 · Последние изменения: 2010/11/12 15:00 (внешнее изменение)