VPF::Быстрая сортировка - Форум программистов

kurzon

Дата 29.10.2007, 19:54 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 307
Регистрация: 12.8.2007

Репутация: -8
Всего: -11

Быстрая сортировка
Как рекурсивно вызвать?

[/quote]

Код


static class QuickSorting
    {
        public static void Sort<T>(T[] array, Comparison<T> comparison)
        {

            int i = 0, j = array.Length;        // поставить указатели на исходные места
            T temp, p;

            p = array[array.Length >> 1];        // центральный элемент

            // процедура разделения
            do
            {
                while (comparison(array[i],p)>0) i++;
                while (comparison(array[j],p)>0) j--;

                if (i <= j)
                {
                    temp = array[i];
                    array[i] = array[j]; 
                    array[j] = temp;
                    i++; j--;
                }
            } while (i <= j);


            // рекурсивные вызовы, если есть, что сортировать 
            if (j > 0) Sort<T>(array, j);
            if (array.Length > i) Sort<T>(array + i, array.Length - i);


        }
    }

Пожалуста исправте ошибки?

Zapozidon

Дата 29.10.2007, 20:38 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 26.8.2007

Репутация: 1
Всего: 1

Навскидку: насколько я понимаю все это дело (quicksort), то функцию нужно вызывать с дополнительными параметрами начало и конец сортируемого массива. И вызывать функцию нужно с значениями этих параметров 0 и Length-1. Так что, во-первых, строчка

Код


int i = 0, j = array.Length;

прямо в рекурсивной функции не катит.
Второе. Смотрим, на что ругается компилятор. Последние две строчки хороши в чистых С, но не тут.

Код


 if (j > 0) Sort<T>(array, j);
 if (array.Length > i) Sort<T>(array + i, array.Length - i);

Это надо поменять на рекурсивный вызов Sort, но используя новые параметры, о которых говорилось выше.
А вообще-то [google]Тыкать сюда[/google].
P.S.:в связи отсутствием студии и ограниченостью времени выложить код не могу, советую спионерить по ссылке.

thomas

Дата 29.10.2007, 21:30 (ссылка)

(нет голосов)

Загрузка ...

Доцент... почти

Профиль
Группа: Завсегдатай
Сообщений: 1385
Регистрация: 3.10.2006
Где: " Сказочное королевство"

Репутация: 6
Всего: 65

kurzon,

Цитата

Как рекурсивно вызвать?

Так

Код


private void Quicksort(int Li, int Re)
        {
            int get1, get2;
            int Hli=Li; int Hre=Re;
            int mid=Tabel[(Hli+Hre)/2];
            while(Hli<=Hre)
            {
                while((get1=Tabel[Hli])<mid)
                {
                    Hli++;
                }
                while((get2=Tabel[Hre])>mid)
                {
                    Hre--;
                }
                if(Hli<=Hre)
                {
                    verwissel(Hli,Hre);
                    Hli++; Hre--;
                }
            }
            if(Li<Hre)
            {
                Quicksort(Li,Hre); // вот тут она родимая и вызывается РЕКУРСИВНО!!!
            }
            if(Hli<Re)
            {
                Quicksort(Hli, Re); // вот тут она родимая и вызывается РЕКУРСИВНО!!!
            } 

        }

Добавлено через 1 минуту и 16 секунд
Плюс функция "местами поменять"

Код


private void verwissel(int ind1, int ind2)
        {
            int hulp=Tabel[ind1];
            Tabel[ind1]=Tabel[ind2];
            Tabel[ind2]=hulp;
        }

Добавлено через 3 минуты и 30 секунд
Да массив обьявляли глобально

Код


int[]Tabel;

--------------------

Крепко жму горло, искренне ваш Thomas. (С)vingrad
Некоторые сорта флоры буквально за одно мгновение превращают нас в фауну!
Проблемы негров шерифа не волнуют.

HalkaR

Дата 29.10.2007, 23:32 (ссылка)

(нет голосов)

Загрузка ...

Пуфыстый назгул

Профиль
Группа: Экс. модератор
Сообщений: 2132
Регистрация: 8.12.2002
Где: В Москве

Репутация: 14
Всего: 42

Просто так для информации (на всякий случай, не желая никого обидеть) сообщу, что стандартный метод сортировки в C# использует quicksort

Код


List<int> a =new List<int>();
a.Sort(delegate(int a1, int a2) { return Comparer<int>.Default.Compare(a1, a2); });

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Общие вопросы по .NET и C# \| Следующая тема »