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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 38, средняя оценка - 4.82
Hardcore
4 / 4 / 0
Регистрация: 24.10.2010
Сообщений: 200
05.11.2010, 12:41     Сортировка Quick Sort #1
Можно написать код и коментами.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7955 / 4717 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 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
1233 / 771 / 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
1233 / 771 / 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
1233 / 771 / 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
1233 / 771 / 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
1233 / 771 / 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
1233 / 771 / 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
Еще ссылки по теме:

Не работает сортировка Stl sort C++
Написать функцию Quick Sort для массива с 2000 элементов C++
Сортировка массива c++ std :: sort() C++
Метод сортировки quick sort ведомость абитуриентов C++
Quick sort using vectors C++

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

Или воспользуйтесь поиском по форуму:
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
Ответ Создать тему
Опции темы

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