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

Быстрая сортировка Хоара без рекурсивных функций - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 38, средняя оценка - 4.66
yuliyayuliya28
3 / 3 / 0
Регистрация: 06.03.2011
Сообщений: 319
25.04.2012, 21:26     Быстрая сортировка Хоара без рекурсивных функций #1
Здравствуйте мне нужно написать быстрою сортировку Хоара но без рекурсивных функций...помогите пожалуйста разобраться
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
#include <iostream>
#include <conio.h>
 
using namespace std;
 
int main()
{  int array[100];
    int size,i,j,p,temp;
    cin>>size;
 
    for(i=0;i<size;i++)
        cin>>array[i];
 
 
    p=array[size/2];
    do{
        while (array[i]<p)i++;
        while (array[j]>p)j--;
        if(i<=j)
        {
            temp=array[i];
            array[i]=array[j];
            array[j]=temp;
            i++;
            j--;
        }
 
    for(i=0;i<size;i++;
    cout<<array[i]<< " ";
 
    return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
NeonLost
Пес войны
 Аватар для NeonLost
74 / 85 / 3
Регистрация: 23.02.2012
Сообщений: 653
25.04.2012, 21:37     Быстрая сортировка Хоара без рекурсивных функций #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
 p = array[ size>>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 );
я do(17) у тебя увидел, а while(27) почему-то нет...
yuliyayuliya28
3 / 3 / 0
Регистрация: 06.03.2011
Сообщений: 319
25.04.2012, 21:42  [ТС]     Быстрая сортировка Хоара без рекурсивных функций #3
Цитата Сообщение от NeonLost Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
 p = array[ size>>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 );
я do(17) у тебя увидел, а while(27) почему-то нет...
вот я и знаю как реализовать дальше без рекурсии
NeonLost
Пес войны
 Аватар для NeonLost
74 / 85 / 3
Регистрация: 23.02.2012
Сообщений: 653
25.04.2012, 22:04     Быстрая сортировка Хоара без рекурсивных функций #4
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <windows.h>
#include <iostream>
#define MAXSTACK 2048 // максимальный размер стека
void qSortI(int a[], long size) {
 
long i, j; // указатели, участвующие в разделении
long lb, ub; // границы сортируемого в цикле фрагмента
 
long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
// каждый запрос задается парой значений,
// а именно: левой(lbstack) и правой(ubstack)
// границами промежутка
long stackpos = 1; // текущая позиция стека
long ppos; // середина массива
int pivot; // опорный элемент
int 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 ); // пока есть запросы в стеке
}
 
int main()
{
int mass[10];
for (int i=0; i<10; i++)
{
    std::cin>>mass[i];
}
qSortI(mass,10);
for (int i=0; i<10; i++)
{
    std::cout<<mass[i];
}
    getchar();
    getchar();
    return 0;
}
вот что у меня получилось, работает
yuliyayuliya28
3 / 3 / 0
Регистрация: 06.03.2011
Сообщений: 319
25.04.2012, 22:31  [ТС]     Быстрая сортировка Хоара без рекурсивных функций #5
Цитата Сообщение от NeonLost Посмотреть сообщение
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <windows.h>
#include <iostream>
#define MAXSTACK 2048 // максимальный размер стека
void qSortI(int a[], long size) {
 
long i, j; // указатели, участвующие в разделении
long lb, ub; // границы сортируемого в цикле фрагмента
 
long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
// каждый запрос задается парой значений,
// а именно: левой(lbstack) и правой(ubstack)
// границами промежутка
long stackpos = 1; // текущая позиция стека
long ppos; // середина массива
int pivot; // опорный элемент
int 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 ); // пока есть запросы в стеке
}
 
int main()
{
int mass[10];
for (int i=0; i<10; i++)
{
    std::cin>>mass[i];
}
qSortI(mass,10);
for (int i=0; i<10; i++)
{
    std::cout<<mass[i];
}
    getchar();
    getchar();
    return 0;
}
вот что у меня получилось, работает
а как доделать мой код
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
25.04.2012, 22:34     Быстрая сортировка Хоара без рекурсивных функций #6
Цитата Сообщение от NeonLost Посмотреть сообщение
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <windows.h>
#include <iostream>
#define MAXSTACK 2048 // максимальный размер стека
void qSortI(int a[], long size) {
 
long i, j; // указатели, участвующие в разделении
long lb, ub; // границы сортируемого в цикле фрагмента
 
long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
// каждый запрос задается парой значений,
// а именно: левой(lbstack) и правой(ubstack)
// границами промежутка
long stackpos = 1; // текущая позиция стека
long ppos; // середина массива
int pivot; // опорный элемент
int 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 ); // пока есть запросы в стеке
}
 
int main()
{
int mass[10];
for (int i=0; i<10; i++)
{
    std::cin>>mass[i];
}
qSortI(mass,10);
for (int i=0; i<10; i++)
{
    std::cout<<mass[i];
}
    getchar();
    getchar();
    return 0;
}
вот что у меня получилось, работает
охренеть! меньше чем за полчаса сделал?
yuliyayuliya28
3 / 3 / 0
Регистрация: 06.03.2011
Сообщений: 319
25.04.2012, 22:50  [ТС]     Быстрая сортировка Хоара без рекурсивных функций #7
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
охренеть! меньше чем за полчаса сделал?
а вы не поможите как доделать мой код?
NeonLost
Пес войны
 Аватар для NeonLost
74 / 85 / 3
Регистрация: 23.02.2012
Сообщений: 653
25.04.2012, 23:18     Быстрая сортировка Хоара без рекурсивных функций #8
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
охренеть! меньше чем за полчаса сделал?
это я из фака взял, все, что я сделал это написал main()

Добавлено через 1 минуту
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
63
64
65
66
67
68
69
70
71
72
73
74
#include <windows.h>
#include <iostream>
#define MAXSTACK 2048 // максимальный размер стека
void main() {
int a[100];
    int size,i,j,p,temp; // указатели, участвующие в разделении
    std::cin>>size;
 
    for(i=0;i<size;i++)
       std::cin>>a[i];
 
long lb, ub; // границы сортируемого в цикле фрагмента
 
long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
// каждый запрос задается парой значений,
// а именно: левой(lbstack) и правой(ubstack)
// границами промежутка
long stackpos = 1; // текущая позиция стека
long ppos; // середина массива
int pivot; // опорный элемент
 
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 ); // пока есть запросы в стеке
 
 
 
for(i=0;i<size;i++)
    std::cout<<a[i]<<" ";
getchar();
getchar();
}
единственное что изменил это название массива с "array" на "а"...
yuliyayuliya28
3 / 3 / 0
Регистрация: 06.03.2011
Сообщений: 319
25.04.2012, 23:33  [ТС]     Быстрая сортировка Хоара без рекурсивных функций #9
Цитата Сообщение от NeonLost Посмотреть сообщение
это я из фака взял, все, что я сделал это написал main()

Добавлено через 1 минуту
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
63
64
65
66
67
68
69
70
71
72
73
74
#include <windows.h>
#include <iostream>
#define MAXSTACK 2048 // максимальный размер стека
void main() {
int a[100];
    int size,i,j,p,temp; // указатели, участвующие в разделении
    std::cin>>size;
 
    for(i=0;i<size;i++)
       std::cin>>a[i];
 
long lb, ub; // границы сортируемого в цикле фрагмента
 
long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
// каждый запрос задается парой значений,
// а именно: левой(lbstack) и правой(ubstack)
// границами промежутка
long stackpos = 1; // текущая позиция стека
long ppos; // середина массива
int pivot; // опорный элемент
 
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 ); // пока есть запросы в стеке
 
 
 
for(i=0;i<size;i++)
    std::cout<<a[i]<<" ";
getchar();
getchar();
}
единственное что изменил это название массива с "array" на "а"...
без стека это нельзя сделать?
NeonLost
Пес войны
 Аватар для NeonLost
74 / 85 / 3
Регистрация: 23.02.2012
Сообщений: 653
25.04.2012, 23:33     Быстрая сортировка Хоара без рекурсивных функций #10
хз, мб и можно(сомневаюсь), но я не знаю как
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
25.04.2012, 23:35     Быстрая сортировка Хоара без рекурсивных функций #11
Цитата Сообщение от yuliyayuliya28 Посмотреть сообщение
без стека это нельзя сделать?
как ты себе это представляешь?
yuliyayuliya28
3 / 3 / 0
Регистрация: 06.03.2011
Сообщений: 319
27.04.2012, 08:36  [ТС]     Быстрая сортировка Хоара без рекурсивных функций #12
никто не знает как можно реализовать быструю сортировку без рекурсий и стека?

Добавлено через 17 часов 22 минуты
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
как ты себе это представляешь?
как заменить циклами рекурсию
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
27.04.2012, 15:09     Быстрая сортировка Хоара без рекурсивных функций #13
Цитата Сообщение от yuliyayuliya28 Посмотреть сообщение
как заменить циклами рекурсию
Зачем тебе Этот Геморой?
yuliyayuliya28
3 / 3 / 0
Регистрация: 06.03.2011
Сообщений: 319
27.04.2012, 17:08  [ТС]     Быстрая сортировка Хоара без рекурсивных функций #14
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Зачем тебе Этот Геморой?
нужна будет оценка сложности...я на простой программе не понимаю как а что с рекурсией делать вообще не знаю..
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
27.04.2012, 17:18     Быстрая сортировка Хоара без рекурсивных функций #15
Цитата Сообщение от yuliyayuliya28 Посмотреть сообщение
нужна будет оценка сложности...я на простой программе не понимаю как а что с рекурсией делать вообще не знаю..
И из-за этого типичный рекурсивный алгоритм, реализаций которого через рекурсию тысячи штук на любом сайте надо пытаться решать другим способом???
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int counter=0;
void qsort(int*, int, int){
  //....
  while (left<right){
    ////...
    if (a[left]>a[right]){
      swap(left, right);
      counter++;
    }
  }
  if(...)qsort(...);
  if(...)qsort(...);
}
int main(){
//...
  counter=0;
  qsort(...);
  cout<<counter;
 
}
или static int counter можно
или, чтоб qsort возвращал число операций.
C++
1
2
3
4
5
6
7
8
9
10
11
12
void qsort(int*, int, int){
   int ops_num=0
  //....
  while (left<right){
    ////...
    if (a[left]>a[right]){
      swap(left, right);
      ops_num++;
    }
  }
  return qsort(...)+qsort(...)+ops_num;
}
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
28.04.2012, 20:49     Быстрая сортировка Хоара без рекурсивных функций #16
Kuzia domovenok, число операций к асимптотической сложности никакого отношения не имеет.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
28.04.2012, 23:51     Быстрая сортировка Хоара без рекурсивных функций #17
Цитата Сообщение от silent_1991 Посмотреть сообщение
число операций к асимптотической сложности никакого отношения не имеет.
LOL, а что имеет к ней отношение? Тем более автору нужно скорее всего именно это. А не скопировать из книжки таблицу оценок сложности алгоритмов сортировки.

нужна будет оценка сложности...я на простой программе не понимаю как а что с рекурсией делать вообще не знаю..
Предложи свой метод практической оценки скорости алгоритма, зачем выпендриваться? И без асимптотических обозначений, пожалуйста. Автор о них ничего не говорил. Автору нужен конкретный результат: число, оценивающее сложность. А не копия таблицы асимптотических оценок сортировок.

Тем более, что автор хоть с рекурсией, хоть без неё не полностью понимает, что ему нужно.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
29.04.2012, 06:40     Быстрая сортировка Хоара без рекурсивных функций #18
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
LOL, а что имеет к ней отношение?
Сложность алгоритмов и только она.
А если вы предлагаете подсчитать все операции, то вы забываете, что время тратится не только на перестановку элементов массива, но и на инкременты счетчиков, проверку условий и т.д., причем на ассемблерном уровне это может быть реализовано как угодно(возможно, там будет векторизация использоваться).
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
29.04.2012, 11:23     Быстрая сортировка Хоара без рекурсивных функций #19
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
автору нужно скорее всего именно это
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Автору нужен конкретный результат
Пусть автор сам скажет, что ему нужно. Потому что когда разговор переходит в область гипотез, прав будет всякий, кто в нём участвует.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.09.2012, 14:12     Быстрая сортировка Хоара без рекурсивных функций
Еще ссылки по теме:

Быстрая сортировка (сортировка Хоара) для связных списков C++
Быстрая сортировка (сортировка методом Хоара) C++
C++ Сортировка Хоара / Быстрая сортировка

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

Или воспользуйтесь поиском по форуму:
Mikl___
Заблокирован
Автор FAQ
11.09.2012, 14:12     Быстрая сортировка Хоара без рекурсивных функций #20
Быстрая сортировка без рекурсии


Кстати, с сайта algolist.manual.ru/sort/quick_sort.php mik-a-el вставил листинг быстрой сортировки без рекурсии в Алгоритмы сортировок смотрим внимательно
Итеративный алгоритм быстрой сортировки.
Псевдокод.
Код
Итеративная 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 ); // пока есть запросы в стеке
}
так что далеко ходить было не нужно, стоило только внимательно почитать прикрепленные темы
Yandex
Объявления
11.09.2012, 14:12     Быстрая сортировка Хоара без рекурсивных функций
Ответ Создать тему
Опции темы

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