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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 38, средняя оценка - 4.82
Hardcore
4 / 4 / 0
Регистрация: 24.10.2010
Сообщений: 200
#1

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

05.11.2010, 12:41. Просмотров 5351. Ответов 13
Метки нет (Все метки)

Можно написать код и коментами.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2010, 12:41     Сортировка Quick Sort
Посмотрите здесь:

Быстрая Сортировка quick-sort (ошибка в 40 строке) как исправить? - C++
#include <iostream> #include <vector> using std::endl; using std::cout; using std::vector; template<class T> void...

Quick sort c++ - C++
Добрый день. Есть вопрос, как можно реализовать Quick sort с подсчётом перестановок. По условию задания у нас есть 10000 элементов. ...

Quick sort using vectors - C++
Now that you have learned about three sorting algorithms with quadratic time complexity (Bubble, (./selection) and Insertion sorts) you...

Алгоритм Быстрой сортировки (Quick Sort) - C++
Всем доброго времени суток. Реализовал Быструю Сортировку на C++. Всё работает. Только препод требует доказать, что мой алгоритм...

Quick sort, не понятно некоторые моменты. - C++
здравствуйте нужно реализовать quicksort Есть код с учебника по которому мы учимся, и вот не понятно некоторые моменты кода ...

Метод сортировки quick sort ведомость абитуриентов - C++
Ведомость абитуриентов, сдавших вступительные экзамены в университет, содержит: Ф.И.О. абитуриента, оценки. Определить средний балл по...

Написать функцию Quick Sort для массива с 2000 элементов - C++
Написать функцию Quick Sort. Использовать написанную функцию для сортировки массива типа double на 2000 элементов. Нужна помощь:-|

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
05.11.2010, 12:42     Сортировка Quick Sort #2
Hardcore,
C++
1
2
3
4
5
//Вызов стандартной сортировки
//если массив большой используется быстрая
//Arr - указатель на первый элемент
//Arr+N - указатель на элемент за последним
std::sort(Arr, Arr+N);
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 12:45     Сортировка Quick Sort #3
http://www.cyberforum.ru/cpp-beginners/thread27084.htm
Hardcore
4 / 4 / 0
Регистрация: 24.10.2010
Сообщений: 200
05.11.2010, 12:49  [ТС]     Сортировка Quick Sort #4
Игнат, твоя ссылка не работает.
Можешь написать весь код с доступными коментами
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 13:03     Сортировка Quick Sort #5
Быстрая сортировка (сортировка Хоара)

"Быстрая сортировка", хоть и была разработана более 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 значения хватает с лихвой.

Пример взял по той ссылки, она действительно не работает, не понятно почему.
Hardcore
4 / 4 / 0
Регистрация: 24.10.2010
Сообщений: 200
05.11.2010, 13:11  [ТС]     Сортировка Quick Sort #6
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
#include <iostream>
 
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); //Вот это тоже не ясно что делается
}
 
int main()
{
        setlocale(LC_ALL, "Russian");
        char str[] = "бвгда";
        quickSortR(str, strlen(str));
        std::cout << str << std::endl;
        int a[] = { 2, 5, 1, 20, 8, 0, 9 };
        quickSortR(a, 6);
 
        for(int i = 0; i < 7; i++)
                std::cout << a[i] << " ";
 
        std::cout << std::endl;
 
        return 0;
}
можете отредактировать этот код, только без букв а только цифры. и чтоб я могу вводить цифры произвольно.
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 13:16     Сортировка Quick Sort #7
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
#include <iostream>
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); //Вот это тоже не ясно что делается
}
 
int main()
{
     
      
    
        int a[6] ;
        for( int k = 0 ; k < 6 ; k++ )cin>>a[k];
    
 
        quickSortR(a, 6);
 
        for(int i = 0; i < 6; i++)
                cout << a[i] << " ";
 
        cout << endl;
 
        return 0;
}
Hardcore
4 / 4 / 0
Регистрация: 24.10.2010
Сообщений: 200
05.11.2010, 13:18  [ТС]     Сортировка Quick Sort #8
проверь, у тебя там что то не так.
ошибку приводит когда вводишь цифры.
а если можешь, то напиши сам занова код с начала до конца с коментами и без больших наваротов.
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 13:26     Сортировка Quick Sort #9
У меня, ни каких ошибок не происходит.
Hardcore
4 / 4 / 0
Регистрация: 24.10.2010
Сообщений: 200
05.11.2010, 13:36  [ТС]     Сортировка Quick Sort #10
А можешь по новому написать код?
без классов и по проще?
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 13:45     Сортировка Quick Sort #11
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
#include <iostream>
using namespace std;
 
void quickSortR(int * a, long N) {
// На входе - массив a[], a[N] - его последний элемент.
 
  long i = 0, j = N;            //Что это?
  int 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); //Вот это тоже не ясно что делается
}
 
int main()
{
     
      
    
        int a[6] ;
        for( int k = 0 ; k < 6 ; k++ )cin>>a[k];
    
 
        quickSortR(a, 6);
 
        for(int i = 0; i < 6; i++)
                cout << a[i] << " ";
 
       cout << endl;
 
        return 0;
}
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 13:56     Сортировка Quick Sort #12
Цитата Сообщение от Genius Ignat Посмотреть сообщение
Размер стека при такой реализации всегда имеет порядок O(log n), так что указанного в MAXSTACK значения хватает с лихвой.
Просмотрел код и не нашел перемешивания массива в случае приближения к дну стека. А, таким образом, возможен худший случай - глубина стека n.
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 14:33     Сортировка Quick Sort #13
Zilon
Все претензии к автору, кода я всего лишь скопировал.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2010, 14:41     Сортировка Quick Sort
Еще ссылки по теме:

q-sort сортировка - C++
Здраствуйте , не могу понять где в коде ошибка . Выдает такое :d:\program...

сортировка вектора sort() - C++
программа заполняет вектор рандомными числами в диапазоне от 1 до 100 сортирует с помощью алгоритма sort(.begin(),.end()) - в...

Не работает сортировка Stl sort - C++
вот код сортировки массива обычным stl sort () #include&lt;conio.h&gt; #include&lt;iostream.h&gt; #include&lt;vector.h&gt; #include&lt;algorithm&gt; ...

Сортировка слиянием (Merge sort) - C++
Пожалуйста, помогите сортировать лист в C++ только надо именно слиянием отсортировать

Сортировка массива c++ std :: sort() - C++
Дан двумерный массив символов char M, надо отсортировать его при помощи std :: sort(), построчно, т.е. допустим было 00011 11111 ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 14:41     Сортировка Quick Sort #14
Да какие претензии?
Просто внимание обращаю.
Я сейчас тоже QS пишу и в рамках этой задачи написал shuffld. До этого 3 дня Кнута штурмовал, по поводу генерации случайных чисел для перемешивания.
Yandex
Объявления
05.11.2010, 14:41     Сортировка Quick Sort
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru