Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 38, средняя оценка - 4.82
Hardcore
4 / 4 / 4
Регистрация: 24.10.2010
Сообщений: 200
#1

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

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

Можно написать код и коментами.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2010, 12:41
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Сортировка Quick Sort (C++):

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

Quick sort c++
Добрый день. Есть вопрос, как можно реализовать Quick sort с подсчётом...

Quick sort using vectors
Now that you have learned about three sorting algorithms with quadratic time...

Реализация алгоритма Quick sort
пожалуйсто напишите алгоритм Quick sort

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

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

13
ForEveR
В астрале
Эксперт С++
7994 / 4753 / 651
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
05.11.2010, 12:42 #2
Hardcore,
C++
1
2
3
4
5
//Вызов стандартной сортировки
//если массив большой используется быстрая
//Arr - указатель на первый элемент
//Arr+N - указатель на элемент за последним
std::sort(Arr, Arr+N);
0
Genius Ignat
1241 / 779 / 108
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 12:45 #3
http://www.cyberforum.ru/cpp-beginners/thread27084.htm
0
Hardcore
4 / 4 / 4
Регистрация: 24.10.2010
Сообщений: 200
05.11.2010, 12:49  [ТС] #4
Игнат, твоя ссылка не работает.
Можешь написать весь код с доступными коментами
0
Genius Ignat
1241 / 779 / 108
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 13:03 #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 значения хватает с лихвой.

Пример взял по той ссылки, она действительно не работает, не понятно почему.
1
Hardcore
4 / 4 / 4
Регистрация: 24.10.2010
Сообщений: 200
05.11.2010, 13:11  [ТС] #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;
}
можете отредактировать этот код, только без букв а только цифры. и чтоб я могу вводить цифры произвольно.
0
Genius Ignat
1241 / 779 / 108
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 13:16 #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;
}
0
Hardcore
4 / 4 / 4
Регистрация: 24.10.2010
Сообщений: 200
05.11.2010, 13:18  [ТС] #8
проверь, у тебя там что то не так.
ошибку приводит когда вводишь цифры.
а если можешь, то напиши сам занова код с начала до конца с коментами и без больших наваротов.
0
Genius Ignat
1241 / 779 / 108
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 13:26 #9
У меня, ни каких ошибок не происходит.
0
Hardcore
4 / 4 / 4
Регистрация: 24.10.2010
Сообщений: 200
05.11.2010, 13:36  [ТС] #10
А можешь по новому написать код?
без классов и по проще?
0
Genius Ignat
1241 / 779 / 108
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 13:45 #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;
}
0
Zilon
5 / 5 / 1
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 13:56 #12
Цитата Сообщение от Genius Ignat Посмотреть сообщение
Размер стека при такой реализации всегда имеет порядок O(log n), так что указанного в MAXSTACK значения хватает с лихвой.
Просмотрел код и не нашел перемешивания массива в случае приближения к дну стека. А, таким образом, возможен худший случай - глубина стека n.
0
Genius Ignat
1241 / 779 / 108
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 14:33 #13
Zilon
Все претензии к автору, кода я всего лишь скопировал.
0
Zilon
5 / 5 / 1
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 14:41 #14
Да какие претензии?
Просто внимание обращаю.
Я сейчас тоже QS пишу и в рамках этой задачи написал shuffld. До этого 3 дня Кнута штурмовал, по поводу генерации случайных чисел для перемешивания.
0
05.11.2010, 14:41
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2010, 14:41
Привет! Вот еще темы с решениями:

Метод сортировки quick sort ведомость абитуриентов
Ведомость абитуриентов, сдавших вступительные экзамены в университет, содержит:...

Написать функцию Quick Sort для массива с 2000 элементов
Написать функцию Quick Sort. Использовать написанную функцию для сортировки...

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

сортировка вектора sort()
программа заполняет вектор рандомными числами в диапазоне от 1 до 100 ...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

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