Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

25.04.2012, 21:26. Просмотров 5743. Ответов 19
Метки нет (Все метки)

Здравствуйте мне нужно написать быстрою сортировку Хоара но без рекурсивных функций...помогите пожалуйста разобраться
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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.04.2012, 21:26
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Быстрая сортировка Хоара без рекурсивных функций (C++):

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива - C++
Мне нужно отсортировать фрагмент массива, расположенный между первым и последним отрицательным элементом. Немогу понять как устоновить...

Быстрая сортировка (сортировка Хоара) для связных списков - C++
есть у кого готовый алгоритм? или подскажите как реализовать

Быстрая сортировка Хоара - C++
Быстрая сортировка Хоара (QSort) разбивает массив в ходе сортировки до тех пор, пока размер частичного подмассива не станет равен...

C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) - C++
Вопрос, скорее академический, по мотивам реализации. Вот в faq приведена реализация этого метода сортировки на C++. В коде есть следующий...

Быстрая сортировка (сортировка методом Хоара) - C++
Ввести массив x1,x2,...,x20 в диапазоне . Требуется расположить отрицательные элементы в порядке убывания. Вывести массивы до и после...

Сортировка Хоара / Быстрая сортировка - C++
Доброго времени суток. Написал реализацию алгоритма быстрой сортировки. void SortHhoar(int *arr,int f,int l)//Хоара { int mid = (f...

19
NeonLost
Пес войны
75 / 86 / 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) почему-то нет...
0
yuliyayuliya28
4 / 4 / 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) почему-то нет...
вот я и знаю как реализовать дальше без рекурсии
0
NeonLost
Пес войны
75 / 86 / 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;
}
вот что у меня получилось, работает
0
yuliyayuliya28
4 / 4 / 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;
}
вот что у меня получилось, работает
а как доделать мой код
0
Kuzia domovenok
2030 / 1874 / 168
Регистрация: 25.03.2012
Сообщений: 6,451
Записей в блоге: 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;
}
вот что у меня получилось, работает
охренеть! меньше чем за полчаса сделал?
0
yuliyayuliya28
4 / 4 / 0
Регистрация: 06.03.2011
Сообщений: 319
25.04.2012, 22:50  [ТС] #7
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
охренеть! меньше чем за полчаса сделал?
а вы не поможите как доделать мой код?
0
NeonLost
Пес войны
75 / 86 / 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" на "а"...
0
yuliyayuliya28
4 / 4 / 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" на "а"...
без стека это нельзя сделать?
0
NeonLost
Пес войны
75 / 86 / 3
Регистрация: 23.02.2012
Сообщений: 653
25.04.2012, 23:33 #10
хз, мб и можно(сомневаюсь), но я не знаю как
0
Kuzia domovenok
2030 / 1874 / 168
Регистрация: 25.03.2012
Сообщений: 6,451
Записей в блоге: 1
25.04.2012, 23:35 #11
Цитата Сообщение от yuliyayuliya28 Посмотреть сообщение
без стека это нельзя сделать?
как ты себе это представляешь?
0
yuliyayuliya28
4 / 4 / 0
Регистрация: 06.03.2011
Сообщений: 319
27.04.2012, 08:36  [ТС] #12
никто не знает как можно реализовать быструю сортировку без рекурсий и стека?

Добавлено через 17 часов 22 минуты
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
как ты себе это представляешь?
как заменить циклами рекурсию
0
Kuzia domovenok
2030 / 1874 / 168
Регистрация: 25.03.2012
Сообщений: 6,451
Записей в блоге: 1
27.04.2012, 15:09 #13
Цитата Сообщение от yuliyayuliya28 Посмотреть сообщение
как заменить циклами рекурсию
Зачем тебе Этот Геморой?
0
yuliyayuliya28
4 / 4 / 0
Регистрация: 06.03.2011
Сообщений: 319
27.04.2012, 17:08  [ТС] #14
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Зачем тебе Этот Геморой?
нужна будет оценка сложности...я на простой программе не понимаю как а что с рекурсией делать вообще не знаю..
0
Kuzia domovenok
2030 / 1874 / 168
Регистрация: 25.03.2012
Сообщений: 6,451
Записей в блоге: 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;
}
0
27.04.2012, 17:18
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.04.2012, 17:18
Привет! Вот еще темы с ответами:

Нестандартная быстрая сортировка (без рекурсии) - C++
Помогите пожалуйста, нужно написать программу для одномерного массива, с помощью быстрой сотрировки без рекурсии. Если можно с...

Использование рекурсивных функций - C++
Дан массив x, . . . , x, состоящий из целых чисел, и целое число y. Найти количество элементов массива x, равных y. Использовать...

Алгоритм решения рекурсивных функций - C++
Цель: Прошу подсказать алгоритм решения рекурсивной функции. Задача:

В чем преимущество рекурсивных функций? - C++
Насколько я понял, любую рекурсивную функцию можно реализовать итерационно. И при этом, итерационная реализация не переполняет стэк,...


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

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

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