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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ курсовая работа по информатике http://www.cyberforum.ru/cpp-beginners/thread558705.html
Помогите кто чем сможет)))
C++ Задача для сложения чисел в строке. Привет всем, хочу у вас проконсультироваться, что у меня тут не правильно. Задача: Создать текстовый файл с произвольным числом строк. В тексте должны встречаться цифры. Вычислить сумму цифр и добавить ее файл. Но создавать отдельно файл я не стал, я сделал это в самой задаче, и не добавлял сумму в файл, а просто выводил на экран. Вот моя задача: #include "stdafx.h" #include... http://www.cyberforum.ru/cpp-beginners/thread558695.html
Задача со стеком C++
Всем Здравствуйте,прошу помощи по написанию программы,суть проблемы такова: необходимо написать программу, используя Стек,которая разбирает алгебраические выражения(т.е. вычисляет значение выражения) ,на подобии таких: 2+3*4/3-2.(в выражениях не используются скобки). Буду очень благодарен за помощь!!!
C++ Двусвязные списки в C++
Задача: При построении в списке располагать сначала узлы, содержащие простые числа, а потом все остальные. Я вроде сделал функцию по проверке простых числе и функции вывода двусвязного списка. Вот только сам двусвязный список нормально создать не могу. #include "locale.h" #include "iostream" #include "stdio.h" #include "string.h" #include "Windows.h" using namespace std;
C++ Конструктор класса с параметром http://www.cyberforum.ru/cpp-beginners/thread558671.html
Люди, помогите пожалуйста, а то скоро я кого-нибудь убью по-моему... Самое начало программы. Описываю первый класс. Подключил написанный ранее класс, работавший идеально. #include "vector.cpp" class HTree; class Usel { friend HTree;
C++ Дан массив A[N]. заполнить массив В[N] элементами массива A[N], которые удовлетворяют двойному неравенству Дан массив A. заполнить массив В элементами массива A, которые удовлетворяют двойному неравенству: A< A или A< A. Незаполненные элементы массива В заполнить оставшимися элементами массива A. Осуществить сдвиг вправо на k позиций, где k – число оставшихся элементов массива A. подробнее

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


Кстати, с сайта 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 ); // пока есть запросы в стеке
}
так что далеко ходить было не нужно, стоило только внимательно почитать прикрепленные темы
 
Текущее время: 13:49. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru