Быстрая сортировка

Опис документу:
Быстрая сортировка (сортировка Хоара).

Відображення документу є орієнтовним і призначене для ознайомлення із змістом, та може відрізнятися від вигляду завантаженого документу. Щоб завантажити документ, прогорніть сторінку до кінця

Перегляд
матеріалу
Отримати код Поділитися

Быстрая сортировка (сортировка Хоара)
"Быстрая сортировка", хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов

Псевдокод:

1

2

3

4

5

6

7

8

quickSort ( массив a, верхняя граница N ) {

Выбрать опорный элемент p - середину массива

Разделить массив по этому элементу

Если подмассив слева от p содержит более одного элемента,

вызвать quickSort для него.

Если подмассив справа от p содержит более одного элемента,

вызвать quickSort для него.

}

Реализация на Си

Код C++

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

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);

}

Каждое разделение требует, очевидно, O(n) операций. Количество шагов деления(глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n), что и имеет место на практике.

Итеративный алгоритм быстрой сортировки.

1

2

3

4

5

6

7

8

quickSort ( массив a, верхняя граница N ) {

Выбрать опорный элемент p - середину массива

Разделить массив по этому элементу

Если подмассив слева от p содержит более одного элемента,

вызвать quickSort для него.

Если подмассив справа от p содержит более одного элемента,

вызвать quickSort для него.

}

Псевдокод:

1

2

3

4

5

6

7

8

9

10

11

Итеративная QuickSort (массив a, размер size) {

Положить в стек запрос на сортировку массива от 0 до size-1.

do {

Взять границы lb и ub текущего массива из стека.

do {

1. Произвести операцию разделения над текущим массивом a[lb..ub].

2. Отправить границы большей из получившихся частей в стек.

3. Передвинуть границы ub, lb чтобы они указывали на меньшую часть.

} пока меньшая часть состоит из двух или более элементов

} пока в стеке есть запросы

}

Реализация на Си.

Код C++Выделить код

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

#define MAXSTACK 2048 // максимальный размер стека

template<class T>

void qSortI(T a[], long size) {

 

long i, j; // указатели, участвующие в разделении

long lb, ub; // границы сортируемого в цикле фрагмента

 

long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов

// каждый запрос задается парой значений,

// а именно: левой(lbstack) и правой(ubstack)

// границами промежутка

long stackpos = 1; // текущая позиция стека

long ppos; // середина массива

T pivot; // опорный элемент

T temp;

 

lbstack[1] = 0;

ubstack[1] = size-1;

 

do {

// Взять границы lb и ub текущего массива из стека.

lb = lbstack[ stackpos ];

ub = ubstack[ stackpos ];

stackpos--;

 

do {

// Шаг 1. Разделение по элементу pivot

ppos = ( lb + ub ) >> 1;

i = lb; j = ub; pivot = a[ppos];

do {

while ( a[i] < pivot ) i++;

while ( pivot < a[j] ) j--;

if ( i <= j ) {

temp = a[i]; a[i] = a[j]; a[j] = temp;

i++; j--;

}

} while ( i <= j );

 

// Сейчас указатель i указывает на начало правого подмассива,

// j - на конец левого (см. иллюстрацию выше), lb ? j ? i ? ub.

// Возможен случай, когда указатель i или j выходит за границу массива

 

// Шаги 2, 3. Отправляем большую часть в стек и двигаем lb,ub

if ( i < ppos ) { // правая часть больше

if ( i < ub ) { // если в ней больше 1 элемента - нужно

stackpos++; // сортировать, запрос в стек

lbstack[ stackpos ] = i;

ubstack[ stackpos ] = ub;

}

ub = j; // следующая итерация разделения

// будет работать с левой частью

} else { // левая часть больше

if ( j > lb ) {

stackpos++;

lbstack[ stackpos ] = lb;

ubstack[ stackpos ] = j;

}

lb = i;

}

} while ( lb < ub ); // пока в меньшей части более 1 элемента

} while ( stackpos != 0 ); // пока есть запросы в стеке

}

Зверніть увагу, свідоцтва знаходяться в Вашому особистому кабінеті в розділі «Досягнення»

Всеосвіта є суб’єктом підвищення кваліфікації.

Всі сертифікати за наші курси та вебінари можуть бути зараховані у підвищення кваліфікації.

Співпраця із закладами освіти.

Дізнатись більше про сертифікати.

Приклад завдання з олімпіади Українська мова. Спробуйте!
До ЗНО з НІМЕЦЬКОЇ МОВИ залишилося:
0
4
міс.
1
2
дн.
1
3
год.
Готуйся до ЗНО разом із «Всеосвітою»!