Quick Sort, рекурсия

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

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

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

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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#
1
2
3
4
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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
        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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
        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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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

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

Новые блоги и статьи Все статьи Все блоги /
SwiftUI Data Flow: Передача данных между представлениями mobDevWorks 23.03.2025 При первом знакомстве со SwiftUI кажется, что фреймворк предлагает избыточное количество механизмов для передачи данных: @State, @Binding, @StateObject, @ObservedObject, @EnvironmentObject и другие. . . .	Моки в Java: Сравниваем Mockito, EasyMock, JMockit Javaican 23.03.2025 Как протестировать класс, который зависит от других сложных компонентов, таких как базы данных, веб-сервисы или другие классы, с которыми и так непросто работать в тестовом окружении? Для этого и. . .	Архитектурные паттерны микросервисов: ТОП-10 шаблонов ArchitectMsa 22.03.2025 Популярность микросервисной архитектуры объясняется множеством важных преимуществ. К примеру, она позволяет командам разработчиков работать независимо друг от друга, используя различные технологии и. . .	Оптимизация рендеринга в Unity: Сортировка миллиона спрайтов GameUnited 22.03.2025 Помните, когда наличие сотни спрайтов в игре приводило к существенному падению производительности? Время таких ограничений уходит в прошлое. Сегодня геймдев сталкивается с задачами совершенно иного. . .	Образование и практика Igor3D 21.03.2025 Добрый день А вот каково качество/ эффективность ВУЗовского образования? Аналитическая геометрия изучается в первом семестре и считается довольно легким курсом, что вполне справедливо. Ну хорошо,. . .
Lazarus. Таблица с объединением ячеек. Massaraksh7 21.03.2025 Понадобилась представление на экране таблицы с объединёнными ячейками. И не одной, а штук триста, и все разные. На Delphi я использовал для этих целей TStringGrid, и то, кривовато получалось. А в. . .	Async/await в Swift: Асинхронное программирование в iOS mobDevWorks 20.03.2025 Асинхронное программирование долго было одной из самых сложных задач для разработчиков iOS. В течение многих лет мы сражались с замыканиями, диспетчеризацией очередей и обратными вызовами, чтобы. . .	Колмогоровская сложность: Приёмы упрощения кода ArchitectMsa 20.03.2025 Наверное, каждый программист хотя бы раз сталкивался с кодом, который напоминает запутанный лабиринт — чем дальше в него погружаешься, тем сложнее найти выход. И когда мы говорим о сложности кода, мы. . .	PostgreSQL в Kubernetes: Подготовка кластера и настройка Mr. Docker 20.03.2025 Когда доходит до контейнеризации баз данных и особенно таких требовательных к ресурсам системах как PostgreSQL, многие команды до сих пор колеблются, прежде чем перенести их в контейнерную. . .	C++26: Индексирование пакетов и метапрограммирование bytestream 20.03.2025 Эволюция C++ продолжается стремительными темпами – каждый новый стандарт приносит функциональность, о которой мы мечтали годами. Звучит слишком громко? Если вы когда-либо боролись с вариадическими. . .

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

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

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

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

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

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

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