Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

C++, сортировка Нерекурсивная быстрая сортировка

14K
18 марта 2007 года
demonoide
30 / / 11.02.2007
Пытался переделать с паскальевской...

Код:
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);
}


Если несложно, найдите ошибки

С оригинала на паскале:
Код:
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.
320
18 марта 2007 года
m_Valery
1.0K / / 08.01.2007
Зря мучились. http://php.net/array_sort


Я чтото не понял тема ведь называется С++,сортировка Нерекурсивная быстрая сортировка? Тогда причем тут php - ая asort?Зачем с паскаля что то переводить?Что нужно то ? Использовать быструю сортировку или написать ф-ию нерекурсивной быстрой сортировки ?
Если использовать - то #include <algorithm> и используй sort или используй ф-ию qsort.Если саму ф-ию написать - открой какого-нибудь Кормена или Седжвика , найди алгоритм быстрой сортировки и напиши.Например ,у Кормена так написано что разобравшись с определенным алгоритмом - написать ф-ию на С++ достаточно просто.:)

320
18 марта 2007 года
m_Valery
1.0K / / 08.01.2007
По поводу твоего кода - все работает,если исправишь
 
Код:
...
 const int M=2;// должно быть явно не 2.что такое М?
  ...
 stack[0].right=elements - 1;
 ...

при таком М,не работает с большими массивами...попробуй с массивом в 100 элементов.Но все равно эта ф-ия хоть и работает на уровне qsort,проигрывает по скорости алгоритму stl sort.Массив 10000000 элементов заполнен случ.числами от 0 до 1000.Результаты такие:
NonRecursiveQuickSort - 1250 милисекунд
sort - 750 милисекунд.
14K
19 марта 2007 года
demonoide
30 / / 11.02.2007
Спасибо за отклик ))

Мне задали в лабе использовать ИМЕННО этот метод, кинули в морду код и сказали, что примерно так он работает... разбирайся... прикольно? я перекатал на Си, и спасибо, о Великий m_valery, всё дело действительно в этой сланной переменной! Всё! Теперь верно... благодарю, работает.

PS: php тэг использовал для подсветки кода ))
73K
10 ноября 2011 года
Zzema
13 / / 10.11.2011
Так как надо было исправить эти ошибки, на что? Мне тоже задание задали)))
73K
10 ноября 2011 года
Zzema
13 / / 10.11.2011
Сорри, не подумав написал, thx)
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог