...
const int M=2;// должно быть явно не 2.что такое М?
...
stack[0].right=elements - 1;
...
C++, сортировка Нерекурсивная быстрая сортировка
Код:
void NonRecursiveQuickSort(int *a,int elements)
{
const int M=2;
int i=0,j=0,left,right,s,x,w;
struct{int left,right;} stack[M];
s=0;
stack[0].left=0;
stack[0].right=elements;
do
{
left=stack.left;
right=stack.right;
s--;
do
{
i=left; j=right;
x=a[(left+right)/2];
do
{
while(a<x) i++;
while (x<a[j]) j--;
if (i<=j)
{
w=a; a=a[j]; a[j]=w;
i++; j--;
}
}
while(i<j);
if(i<right)
{
s++;
stack.left=i;
stack.right=right;
}
right=j;
}
while(left<right);
}
while (s>-1);
}
{
const int M=2;
int i=0,j=0,left,right,s,x,w;
struct{int left,right;} stack[M];
s=0;
stack[0].left=0;
stack[0].right=elements;
do
{
left=stack.left;
right=stack.right;
s--;
do
{
i=left; j=right;
x=a[(left+right)/2];
do
{
while(a<x) i++;
while (x<a[j]) j--;
if (i<=j)
{
w=a; a=a[j]; a[j]=w;
i++; j--;
}
}
while(i<j);
if(i<right)
{
s++;
stack.left=i;
stack.right=right;
}
right=j;
}
while(left<right);
}
while (s>-1);
}
Если несложно, найдите ошибки
С оригинала на паскале:
Код:
PROGRAM NonRecursiveQuickSort;
{ Нерекурсивная реализация алгоритма быстрой сортировки. }
{ В программе использован тип данных - Record }
const N=8; M=12;
type Index =0..N;
Massiv=Array [0..N] of Integer;
zapis =Record
L,R: index
end;
var x,w : Integer;
a : Massiv;
i,j,L,R: Index;
s : 0..M;
stack : Array [1..M] of zapis;
BEGIN
Write('Вводите элементы массива: ');
For i:=1 to N do Read(A);
s:=1;
stack[1].L:=1;
stack.R:=N;
Repeat { Выбор из стека последнего запроса }
L:=stack.L;
R:=stack.R;
s:=s-1;
Repeat { Разделение a[L],...,a[R] }
i:=L;
j:=R;
x:=A[(L+R) DIV 2];
Repeat
While A<x do i:=i+1;
While x<A[j] do j:=j-1;
If i<=j then
begin
w:=A;
A:=A[j];
A[j]:=w;
i:=i+1;
j:=j-1
end;
until i>j;
If i<R then { Запись в стек запроса из правой части }
begin
s:=s+1;
stack.L:=i;
stack.R:=R
end;
R:=j { Теперь L и R ограничивают левую часть }
until L>=R;
until s=0;
Write('Результат: ');
For i:=1 to N do Write(A,' ');
WriteLn
END.
{ Нерекурсивная реализация алгоритма быстрой сортировки. }
{ В программе использован тип данных - Record }
const N=8; M=12;
type Index =0..N;
Massiv=Array [0..N] of Integer;
zapis =Record
L,R: index
end;
var x,w : Integer;
a : Massiv;
i,j,L,R: Index;
s : 0..M;
stack : Array [1..M] of zapis;
BEGIN
Write('Вводите элементы массива: ');
For i:=1 to N do Read(A);
s:=1;
stack[1].L:=1;
stack.R:=N;
Repeat { Выбор из стека последнего запроса }
L:=stack.L;
R:=stack.R;
s:=s-1;
Repeat { Разделение a[L],...,a[R] }
i:=L;
j:=R;
x:=A[(L+R) DIV 2];
Repeat
While A<x do i:=i+1;
While x<A[j] do j:=j-1;
If i<=j then
begin
w:=A;
A:=A[j];
A[j]:=w;
i:=i+1;
j:=j-1
end;
until i>j;
If i<R then { Запись в стек запроса из правой части }
begin
s:=s+1;
stack.L:=i;
stack.R:=R
end;
R:=j { Теперь L и R ограничивают левую часть }
until L>=R;
until s=0;
Write('Результат: ');
For i:=1 to N do Write(A,' ');
WriteLn
END.
Цитата: Вася Триллер
Зря мучились. http://php.net/array_sort
Я чтото не понял тема ведь называется С++,сортировка Нерекурсивная быстрая сортировка? Тогда причем тут php - ая asort?Зачем с паскаля что то переводить?Что нужно то ? Использовать быструю сортировку или написать ф-ию нерекурсивной быстрой сортировки ?
Если использовать - то #include <algorithm> и используй sort или используй ф-ию qsort.Если саму ф-ию написать - открой какого-нибудь Кормена или Седжвика , найди алгоритм быстрой сортировки и напиши.Например ,у Кормена так написано что разобравшись с определенным алгоритмом - написать ф-ию на С++ достаточно просто.:)
Код:
при таком М,не работает с большими массивами...попробуй с массивом в 100 элементов.Но все равно эта ф-ия хоть и работает на уровне qsort,проигрывает по скорости алгоритму stl sort.Массив 10000000 элементов заполнен случ.числами от 0 до 1000.Результаты такие:
NonRecursiveQuickSort - 1250 милисекунд
sort - 750 милисекунд.
Мне задали в лабе использовать ИМЕННО этот метод, кинули в морду код и сказали, что примерно так он работает... разбирайся... прикольно? я перекатал на Си, и спасибо, о Великий m_valery, всё дело действительно в этой сланной переменной! Всё! Теперь верно... благодарю, работает.
PS: php тэг использовал для подсветки кода ))
Так как надо было исправить эти ошибки, на что? Мне тоже задание задали)))
Сорри, не подумав написал, thx)