Форум программистов, компьютерный форум CyberForum.ru

Сортировка Quick Sort - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ оператор cin. Как вывести информацию. http://www.cyberforum.ru/cpp-beginners/thread186542.html
Я написал программу: #include<iostream.h> void main(void) { int t; cout<<"введите ваше любимое число и нажмите enter:"; cin>>t; cout<<"ваше любимое число равно "<<t<<endl; cin.get();
C++ Исключить из массива первый, предшествующий максимуму, положительный элемент Дан одномерный массив А, состоящий из N элементов. Исключить из массива первый, предшествующий максимуму, положительный элемент. http://www.cyberforum.ru/cpp-beginners/thread186541.html
C++ найти ошибку
не выводит на экран arrsizetck, т.е как можно вывести число элементов в цикле?? int TCKf(char tcki, int tck, unsigned char *arrtck) { int arrsizetck; int i,c,j=0; printf("arrtck ");
C++ Уплотнить матрицу. Что-то я намудрил..
Задание такое: Нужно уплотнить матрицу. Т.е. на убрать все 0-ли. Вместо их поставить следующий элемент если он есть. Вот код: (Только вот намудрил я что-то страшное) #include "stdafx.h" #include <stdio.h> #include <conio.h> int _tmain(int argc, _TCHAR* argv) { int n, m, i, j, mat, buf;
C++ Нужна литература по теории графов http://www.cyberforum.ru/cpp-beginners/thread186504.html
у меня курсовая работа идет на основе графов, а мы их не изучали, в теории которую дал препод все запутанно, смотрела в Google тож ничего конкретного, кто-нить может помочь? Помощь заключается в том что б дать какую нибудь ссылку на теорию где все расписано или простенькую прогу из которой элементарно было бы видно действия графов
C++ Как получить размер блока в файловой системе Си+ linux. Пытаюсь вывести размер блока файловой системы struct stat buf; i = stat("имя файла", &buf); printf("Размер блока файловой системы - %u", buf.st_blksize); Но получаю странное значение, типа - 131072. В чем может быть дело? Спасибо за любую ссылку или подсказку. подробнее

Показать сообщение отдельно
Genius Ignat
1233 / 771 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 13:03     Сортировка Quick Sort
Быстрая сортировка (сортировка Хоара)

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

Псевдокод.
Код:
//-----------------------
quickSort ( массив a, верхняя граница N ) {
Выбрать опорный элемент p - середину массива
Разделить массив по этому элементу
Если подмассив слева от p содержит более одного элемента,
вызвать quickSort для него.
Если подмассив справа от p содержит более одного элемента,
вызвать quickSort для него.
}
//-----------------------

Реализация на C++.
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);
}
Каждое разделение требует, очевидно, Theta(n) операций. Количество шагов деления(глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n), что и имеет место на практике.

Итеративный алгоритм быстрой сортировки.
Псевдокод.
Код:
//--------------------------------------------
Итеративная 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 ); // пока есть запросы в стеке
}
Размер стека при такой реализации всегда имеет порядок O(log n), так что указанного в MAXSTACK значения хватает с лихвой.

Пример взял по той ссылки, она действительно не работает, не понятно почему.
 
Текущее время: 07:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru