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

Сортировка методом Хоара - C++

Восстановить пароль Регистрация
 
DopelGanker
0 / 0 / 1
Регистрация: 14.10.2015
Сообщений: 23
25.11.2015, 18:06     Сортировка методом Хоара #1
Дали задание
1. Пусть дано массив a1, a2, ..., an. Необходимо переставить его элементы так, чтобы сначала шла группа элементов, больших того элемента, который во входном массиве располагался на первом месте, потом - сам этот элемент, затем - группа элементов, меньших или равных ему. Количество сравнений и перемещений, каждая в отдельности, не должна превышать n-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
75
76
77
78
#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];
}
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.11.2015, 18:06     Сортировка методом Хоара
Посмотрите здесь:

C++ Сортировка двунаправленного линейного списка по алгоритму Хоара
Быстрая сортировка Хоара C++
C++ Написать функцию, которая сортирует вещественный массив методом Хоара
C++ Быстрая сортировка Хоара без рекурсивных функций
C++ Сортировка Хоара
C++ сортировка хоара
C++ Сортировка методом пузырька
C++ Сортировка методом Хоара

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zss
Модератор
Эксперт С++
 Аватар для zss
5942 / 5547 / 1783
Регистрация: 18.12.2011
Сообщений: 14,164
Завершенные тесты: 1
25.11.2015, 18:10     Сортировка методом Хоара #2
Сортировка методом Хоара
DopelGanker
0 / 0 / 1
Регистрация: 14.10.2015
Сообщений: 23
25.11.2015, 18:13  [ТС]     Сортировка методом Хоара #3
Я видел эту тему, но сказали что неправильно
Yandex
Объявления
25.11.2015, 18:13     Сортировка методом Хоара
Ответ Создать тему
Опции темы

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