Быстрая сортировка
От: Аноним  
Дата: 21.11.07 11:59
Оценка:
Быстрая сортировка

Здравствуйте. В книге Кормена про алгоритмы, приведен следующий алгоритм быстрой сортировки на псевдокоде:


Набил это дело на С++
#include <iostream>

namespace quick
{
    typedef int elem_type;

    void swap(elem_type& a, elem_type& b)
    {
        elem_type temp = a;
        a = b;
        b = temp;
    }

    int hoare_partition(elem_type A[], int left, int right)
    {
        elem_type pivot = A[left];
        int i = left - 1;
        int j = right + 1;

        while(true)
        {
            do
            {
                --j;
            }
            while(A[j] > pivot);

            do
            {
                ++i;
            }
            while(A[i] < pivot);

            if(i < j)
                swap(A[i], A[j]);
            else
                return j;
        }
    }

    void quicksort(elem_type A[], int left, int right)
    {
        if(left < right)
        {
            int pivot = hoare_partition(A, left, right);
            quicksort(A, left, pivot - 1);
            quicksort(A, pivot + 1, right);
        }
    }

    void quicksort(elem_type A[], int size)
    {
        quicksort(A, 0, size - 1);
    }

    void dump(elem_type A[], int size)
    {
        for(int i = 0 ; i < size ; ++i)
        {
            std::cout << A[i] << " ";
        }
        std::cout << std::endl;
    }

}

int main(int, char**)
{
    quick::elem_type Array[] = { 5, 2, 6, 8, 0, 1, 3, 2, 9, 4 };

    int size = sizeof(Array) / sizeof(Array[0]);

    quick::quicksort(Array, size);

    quick::dump(Array, size); // 0 2 2 3 4 1 5 6 8 9

    return 0;
}

но массив сортируется неправильно.
Где я туплю? Или у Кормена опечатка/ошибка?
Re: Быстрая сортировка
От: frogkiller Россия  
Дата: 21.11.07 15:06
Оценка:
Здравствуйте, <Аноним>, Вы писали:

А>Быстрая сортировка

А>Здравствуйте. В книге Кормена про алгоритмы, приведен следующий алгоритм быстрой сортировки на псевдокоде:
А>http://img3.freeimagehosting.net/uploads/8c1f866dbf.gif

А>Набил это дело на С++
А>
А>    int hoare_partition(elem_type A[], int left, int right)
А>    {
А>        elem_type pivot = A[left];
А>        int i = left - 1;
А>        int j = right + 1;

А>        while(true)
А>        {
А>            do
А>            {
А>                --j;
А>            }
А>            while(A[j] > pivot);

А>            do
А>            {
А>                ++i;
А>            }
А>            while(A[i] < pivot);

А>            if(i < j)
А>                swap(A[i], A[j]);
А>            else
А>                return j;
А>        }
А>    }
А>

А>но массив сортируется неправильно.
А>Где я туплю? Или у Кормена опечатка/ошибка?

Точно не уверен, но насколько я помню Кнута, должно быть как-то так:
    int hoare_partition(elem_type A[], int left, int right)
    {
        elem_type pivot = A[left];
        int i = left/* - 1*/;
        int j = right + 1;

        while(true)
        {
            while(A[--j] > pivot);
            while(A[++i] < pivot);

            if(i < j)
            {
                swap(A[i], A[j]);
            }
            else
            {
                swap(A[left], A[j]);
                return j;
            }
        }
        //return -1;
    }
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Re: Быстрая сортировка
От: NotImplemented США github.com/NotImplemented
Дата: 21.11.07 15:53
Оценка:
Здравствуйте, Аноним, Вы писали:

А>
А>    void quicksort(elem_type A[], int left, int right)
А>    {
А>        if(left < right)
А>        {
А>            int pivot = hoare_partition(A, left, right);
А>            quicksort(A, left, pivot /*- 1*/);
А>            quicksort(A, pivot + 1, right);
А>        }
А>    }
А>
Re[2]: Быстрая сортировка
От: frogkiller Россия  
Дата: 21.11.07 16:34
Оценка:
Здравствуйте, NotImplemented, Вы писали:

NI>Здравствуйте, Аноним, Вы писали:

А>>
А>>    void quicksort(elem_type A[], int left, int right)
А>>    {
А>>        if(left < right)
А>>        {
А>>            int pivot = hoare_partition(A, left, right);
А>>            quicksort(A, left, pivot /*- 1*/);
А>>            quicksort(A, pivot + 1, right);
А>>        }
А>>    }
А>>


В принципе логично, учитывая данную реализацию hoare_partition.

Но вот на вскидку поискал в инете — практически везде пишут с -1. При том что тупо копируют изначальный алгоритм Вот как верят в Кормена.

Кстати, нашёл ещё одину вариацию на тему Хоара (почти инверсную моему варианту):

    int hoar_partition2(elem_type A[], int left, int right)
    {
        int first = left, pivot = right--;

        while(left <= right)
        {
            while(A[left] < A[pivot])
                left++;
            while( (right>=first) && (A[right]>=A[pivot]) )
                right--;
            if(left<right)
            {
                swap(A[left],A[right]);
                left++;
            }
        }

        if(left!=pivot)
        {
            swap(A[left],A[pivot]);
        }

        return left;
    }


Но она так же делает массу лишних действий. Пока что мой вариант (т.е. Кнута, а ещё вернее, Кнут приписал его Хоару ) выглядит более эффективным.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Re[2]: Быстрая сортировка
От: Аноним  
Дата: 22.11.07 08:29
Оценка:
Здравствуйте, NotImplemented, Вы писали:

А>>
А>>    void quicksort(elem_type A[], int left, int right)
А>>    {
А>>        if(left < right)
А>>        {
А>>            int pivot = hoare_partition(A, left, right);
А>>            quicksort(A, left, pivot /*- 1*/);
А>>            quicksort(A, pivot + 1, right);
А>>        }
А>>    }
А>>


Блин, как я мог не заметить ниже по тексту указание исправить процедуру quicksort в соответствии алгоритмом разбиения.

Всем спасибо.
Re: Быстрая сортировка
От: maggot  
Дата: 23.11.07 20:47
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Быстрая сортировка

А>Здравствуйте. В книге Кормена про алгоритмы, приведен следующий алгоритм быстрой сортировки на псевдокоде:
А>

Интересно, а это работает, если в массиве есть одинаковые элементы? Мне кажется нет. Ща проверю.
Re: Быстрая сортировка
От: seimur  
Дата: 27.11.07 07:52
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Быстрая сортировка

А>Здравствуйте. В книге Кормена про алгоритмы, приведен следующий алгоритм быстрой сортировки на псевдокоде:
А>

А>Набил это дело на С++
А>
А>#include <iostream>

А>namespace quick
А>{
А>    typedef int elem_type;

А>    void swap(elem_type& a, elem_type& b)
А>    {
А>        elem_type temp = a;
А>        a = b;
А>        b = temp;
А>    }

А>    int hoare_partition(elem_type A[], int left, int right)
А>    {
А>        elem_type pivot = A[left];
А>        int i = left - 1;
А>        int j = right + 1;

А>        while(true)
А>        {
А>            do
А>            {
А>                --j;
А>            }
А>            while(A[j] > pivot);

А>            do
А>            {
А>                ++i;
А>            }
А>            while(A[i] < pivot);

А>            if(i < j)
А>                swap(A[i], A[j]);
А>            else
А>                return j;
А>        }
А>    }

А>    void quicksort(elem_type A[], int left, int right)
А>    {
А>        if(left < right)
А>        {
А>            int pivot = hoare_partition(A, left, right);
А>            quicksort(A, left, pivot - 1);
А>            quicksort(A, pivot + 1, right);
А>        }
А>    }

А>    void quicksort(elem_type A[], int size)
А>    {
А>        quicksort(A, 0, size - 1);
А>    }

А>    void dump(elem_type A[], int size)
А>    {
А>        for(int i = 0 ; i < size ; ++i)
А>        {
А>            std::cout << A[i] << " ";
А>        }
А>        std::cout << std::endl;
А>    }

А>}

А>int main(int, char**)
А>{
А>    quick::elem_type Array[] = { 5, 2, 6, 8, 0, 1, 3, 2, 9, 4 };

А>    int size = sizeof(Array) / sizeof(Array[0]);

А>    quick::quicksort(Array, size);

А>    quick::dump(Array, size); // 0 2 2 3 4 1 5 6 8 9

А>    return 0;
А>}
А>

А>но массив сортируется неправильно.
А>Где я туплю? Или у Кормена опечатка/ошибка?

#include <iostream>
#include <iterator>
#include <algorithm>

typedef int elem_type;

//
// Такой вариант функции мне больше нравиться..
//
void dump( elem_type A[], int sz )
{
std::copy( A, A + sz, std::ostream_iterator<elem_type>( std::cout, " " ) );
std::cout << std::endl;
}

int main(int argc, char* argv[])
{
int vector[] = { 5, 3, 4, 2, 6, 8, 9, 7, 1 };
int sz = sizeof( vector ) / sizeof( vector[0] );

dump( vector, sz );

return (0);
}
Теоретически нет разницы между теорией и практикой, но на практике она есть
Re[2]: Быстрая сортировка
От: Аноним  
Дата: 27.11.07 10:53
Оценка:
Здравствуйте, seimur, Вы писали:

S>// Такой вариант функции мне больше нравиться..
S>
//
S>void dump( elem_type A[], int sz )
S>{
S>    std::copy( A, A + sz, std::ostream_iterator<elem_type>( std::cout, " " ) );
S>    std::cout << std::endl;
S>}

Чем, если не секрет? Если уж заниматься ерундой, то ИМХО лучше такой вариант 
void dump2(elem_type A[], int size)
{
    std::for_each(A, A + size, std::cout << boost::lambda::_1);
    std::cout << std::endl;
}
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.