Различия

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

@@ Строка 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>

АйТи бубен

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

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

Различия

Инструменты страницы