Quick Sort, рекурсия

@Lordik192 · Регистрация: 13.10.2012

Студворк — интернет-сервис помощи студентам

Помогите пожалуйста с рекурсией, пишу Быструю Сортировку, все нормально работает до второго вызова рекурсии

C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace qSort
{
    class Program
    {
        static void qSort(int[] array, int start, int end)
        {
 
            if (start >= 0 && end > start)
            {
                
                int k = 1;
 
                while (start != end)
                {
                    if (k % 2 == 0)
                    {
                        if (array[start] > array[end])
                        {
                            int x = array[start];
                            array[start] = array[end];
                            array[end] = x;
 
                            end--;
                            k++;
                        }
                        else
                            start++;
                    }
                    else
                        if (array[start] > array[end])
                        {
                            int x = array[start];
                            array[start] = array[end];
                            array[end] = x;
 
                            start++;
                            k++;
                        }
                        else
                            end--;
 
                }
 
               
                qSort(array, 0, start - 1);
 
                qSort(array, end + 1, array.Length - 1);
 
 
            }
            else
            {
                return;
            }
        }
 
 
        static void Main()
        {
            int[] array = {5,2,1,7,4,8,1};
            qSort(array, 0, array.Length-1 );
            foreach (int i in array)
                Console.Write(i);
        }
    }
}

@Smems · 15.10.2013, 15:21

Lordik192, зачем такие извращения?

C#

int[] array = { 5, 2, 1, 7, 4, 8, 1 };
Array.Sort(array);
foreach (int i in array)
    Console.Write(i);

@valera_21 · 15.10.2013, 15:23

Не по теме:

Сообщение от Smems

Lordik192, зачем такие извращения?

мне кажется, что такие извращения нужны преподавателям :D

@Lordik192 · 15.10.2013, 15:25 **[ТС]**

у меня задание в университете по алгоритмам, нужно самостоятельно реализовать

@tezaurismosis · 15.10.2013, 15:32

Smems, хорошо что добрый дядя из Microsoft написал метод сортировки, а если дяди потом не будет, как Lordik192 будет код писать?

@Smems · 15.10.2013, 15:39

Не по теме:

tezaurismosis, вы ещё скажите, что не нужно пользоваться готовыми библиотеками, паттернами и т.д. И компилятор свой нужно писать. А вдруг все исчезнут? Я же не знаю, для чего товарищу Lordik192. Вдруг он не знает про готовые методы.

А по делу: Lordik192, вот вам алгоритмы, пользуйтесь.

@Spectral-Owl · 15.10.2013, 15:45

не уверен что этот алгоритм можно причислить к быстрым (по моему их вообще штуки 3 общеизвестных), но он всяко быстрее чем изначальный со встроенными While() =)

C#

        static void qSort(int[] array, int start)
        {
            if (start < array.Length)
            {
                int min = array[start];
 
                for(int i=start; i < array.Length; i++)
                    if (min > array[i])
                    {
                        min = array[i];
                        array[i] = array[start];
                        array[start] = min;
                    }
 
                qSort(array, ++start);
            }
            else return;
        }
 
 
        static void Main()
        {
            int[] array = { 5, 2, 1, 7, 4, 8, 1 };
            qSort(array, 0);
            foreach (int i in array)
                Console.Write(i);
 
            Console.ReadLine();
        }
    }

@Lordik192 · 15.10.2013, 15:49 **[ТС]**

спасибо, я их уже видел, когда искал код с qsort, но мне интересно самому ее написать, и сравнить различие в скорости выполнения. Но у меня вышла проблема с рекурсией в моем методе и мне интересно, что в ней не так, все еще надеюсь, что кто-то поможет.

Добавлено через 2 минуты

Сообщение от Spectral-Owl

не уверен что этот алгоритм можно причислить к быстрым (по моему их вообще штуки 3 общеизвестных), но он всяко быстрее чем изначальный со встроенными While() =)

C#

        static void qSort(int[] array, int start)
        {
            if (start < array.Length)
            {
                int min = array[start];
 
                for(int i=start; i < array.Length; i++)
                    if (min > array[i])
                    {
                        min = array[i];
                        array[i] = array[start];
                        array[start] = min;
                    }
 
                qSort(array, ++start);
            }
            else return;
        }
 
 
        static void Main()
        {
            int[] array = { 5, 2, 1, 7, 4, 8, 1 };
            qSort(array, 0);
            foreach (int i in array)
                Console.Write(i);
 
            Console.ReadLine();
        }
    }

Спасибо, но я сейчас разбираюсь именно с qSort, а Вы мне предлагаете нечто другой алгоритм

@Spectral-Owl · 15.10.2013, 16:13

проблема в том, что алгоритм не работает © КЭП

просто подумай сам, после первого вызова алгоритма срабатывает цикл While(), который даже не хочу понимать что делает, после того цикл пройдёт наконец по всем эллементам, и по моему даже не по одному разу, этот же метод сортировки вызывается ещё 2 раза, в каждом из которых присуствует как цикл While(), так и ещё пара вызовов этого же метода...

Добавлено через 4 минуты
по коду:
это явно китайский подход:

C#

if (k % 2 == 0)
                    {
                        if (array[start] > array[end])
                        {
                            int x = array[start];
                            array[start] = array[end];
                            array[end] = x;
 
                            end--;
                            k++;
                        }
                        else
                            start++;
                    }
                    else
                        if (array[start] > array[end])
                        {
                            int x = array[start];
                            array[start] = array[end];
                            array[end] = x;
 
                            start++;
                            k++;
                        }
                        else
                            end--;

делает то-же самое, а места занимает в 2 раза меньше:

C#

if (array[start] > array[end])
                    {
                        int x = array[start];
                        array[start] = array[end];
                        array[end] = x;
 
                        
                        k++;
                    }
                    else
                    {
                        if (k % 2 == 0) start++;
                        else end--;
                    }

Добавлено через 6 минут
как я уже упоминал, даже еслиб это работало, оно слишком ужасно:

Сообщение от Lordik192

C#

1 2	qSort(array, 0, start - 1); qSort(array, end + 1, array.Length - 1);

а вообще, минимально изменённый ваш код вот:

C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace qSort
{
    class Program
    {
        static void qSort(int[] array, int start, int end)
        {
 
            if (start >= 0 && end > start)
            {
                while (start <= end)
                {
                    if (array[start] > array[end])
                    {
                        int x = array[start];
                        array[start] = array[end];
                        array[end] = x;
                    }
                    else start++;
                }
                qSort(array, 0, --end);
            }
            else
            {
                return;
            }
        }
 
 
        static void Main()
        {
            int[] array = { 5, 2, 1, 7, 4, 8, 1 };
            qSort(array, 0, array.Length-1);
            foreach (int i in array)
                Console.Write(i);
 
            Console.ReadLine();
        }
    }
}

почему не нужно сначала проходить циклом по всем эллементам массива, а потом вызывать этот же метод рекурсивно ещё 2(!) раза вам предподаватель расскажет, я такое даже представить не мог)

@tezaurismosis · 15.10.2013, 16:22

Не по теме:

Smems, такую чушь пороть не буду, это неверный вывод из моих слов. Программист должен знать как работают алгоритмы, компиляторы и пр. поэтому студентов заставляют их изучать и писать. Ну а по поводу того, что вы не сразу поняли, что это студент ... пусть будет так. :mda:

@Lordik192 · 15.10.2013, 16:24 **[ТС]**

мой цикл While() выполняет нахождение абсолютной позиции элементом и поэтому он выполняется в самом начале, цикл проходит через все элементы лишь единожды. То что у меня "китайский" подход это не удивительно, я его только начал писать и еще не оптимизировал.

По поводу двойного рекурсивного вызова, то алгоритм qSort сам собой подразумевает разбиение массива на 2 части и отдельную их сортировку, то что Вы предлагаете не совсем соответствует алгоритму, который я стремлюсь реализовать

@Spectral-Owl · 15.10.2013, 16:42

хм... по правде говоря терзаюсь сомнениями, куда же вас послать, то ли на фриланс, то ли к терапевту...
вам указали где ошибка, вам указали пару вариантов решения проблемы, а вы весь такой "а я хочу по другоооому..."

@Lordik192 1 / 1 / 0 Регистрация: 13.10.2012 Сообщений: 28
	15.10.2013, 16:24 [ТС]	11
	мой цикл While() выполняет нахождение абсолютной позиции элементом и поэтому он выполняется в самом начале, цикл проходит через все элементы лишь единожды. То что у меня "китайский" подход это не удивительно, я его только начал писать и еще не оптимизировал. По поводу двойного рекурсивного вызова, то алгоритм qSort сам собой подразумевает разбиение массива на 2 части и отдельную их сортировку, то что Вы предлагаете не совсем соответствует алгоритму, который я стремлюсь реализовать 0

@valera_21
	15.10.2013, 15:23 #3
	Не по теме: Сообщение от Smems Lordik192, зачем такие извращения? мне кажется, что такие извращения нужны преподавателям :D 0

@Lordik192 1 / 1 / 0 Регистрация: 13.10.2012 Сообщений: 28
	15.10.2013, 15:25 [ТС]	4
	у меня задание в университете по алгоритмам, нужно самостоятельно реализовать 0

@tezaurismosis Администратор 9413 / 4699 / 759 Регистрация: 17.04.2012 Сообщений: 9,542 Записей в блоге: 14
	15.10.2013, 15:32	5
	Smems, хорошо что добрый дядя из Microsoft написал метод сортировки, а если дяди потом не будет, как Lordik192 будет код писать? 0

@Smems 154 / 153 / 29 Регистрация: 21.05.2010 Сообщений: 338
	15.10.2013, 15:39	6
	Не по теме: tezaurismosis, вы ещё скажите, что не нужно пользоваться готовыми библиотеками, паттернами и т.д. И компилятор свой нужно писать. А вдруг все исчезнут? Я же не знаю, для чего товарищу Lordik192. Вдруг он не знает про готовые методы. А по делу: Lordik192, вот вам алгоритмы, пользуйтесь. 1

@tezaurismosis
	15.10.2013, 16:22 #10
	Не по теме: Smems, такую чушь пороть не буду, это неверный вывод из моих слов. Программист должен знать как работают алгоритмы, компиляторы и пр. поэтому студентов заставляют их изучать и писать. Ну а по поводу того, что вы не сразу поняли, что это студент ... пусть будет так. :mda: 0

@Spectral-Owl 606 / 581 / 157 Регистрация: 29.06.2010 Сообщений: 1,620
	15.10.2013, 16:42	12
	хм... по правде говоря терзаюсь сомнениями, куда же вас послать, то ли на фриланс, то ли к терапевту... вам указали где ошибка, вам указали пару вариантов решения проблемы, а вы весь такой "а я хочу по другоооому..." 0