Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/4: Рейтинг темы: голосов - 4, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 15.11.2020
Сообщений: 22

Почему быстрая сортировка работает медленнее, чем все остальные?

04.05.2023, 00:41. Показов 809. Ответов 2

Студворк — интернет-сервис помощи студентам
У меня такое задание: Составить программу, проводящую сравнительную характеристику методов сортировки массивов.
Программа должна выполнять следующие действия:
1. Производить сортировку массива соответствующими методами.
2. Иллюстрировать работу каждого метода на небольших массивах (размером до 10 элементов).
3. Производить сортировку каждым из методов случайного массива, уже отсортированного массива,
массива, отсортированного в обратном порядке. Засечь время. Размер массива при этом должен выбираться
пользователем. После проведения сортировки, вывести данные о скорости работы методов.
Метод Шелла, пирамидальная сортировка, быстрая сортировка.
Программа готова и работает, но я не могу понять, почему быстрая сортировка работает медленнее, чем все остальные, хотя написал вроде верно. В чем ошибка? + прога может съесть массив 1000000-1500000, тоже не понимаю почему так...
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
using System;
using System.Diagnostics;
 
namespace SortingMethodsComparison
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Введите размер массива: ");
            // Считывание введенного с клавиатуры значения и преобразование его в целочисленный тип данных.
            int size = int.Parse(Console.ReadLine());
 
            // Создание трех массивов типа int для каждого метода сортировки.
            int[] arrShell = new int[size];
            int[] arrHeap = new int[size];
            int[] arrQuick = new int[size];
 
            // Заполнение трех массивов случайными числами.
            Random rand = new Random();
            for (int i = 0; i < size; i++)
            {
                int num = rand.Next(100);
 
                arrShell[i] = num;
                arrHeap[i] = num;
                arrQuick[i] = num;
            }
 
        // демонстрация сортировки
        Console.WriteLine("Сортировка Шелла:");
            int[] smallArrShell = { 9, 7, 3, 8, 2, 1, 5, 4, 6 };
            ShellSort(smallArrShell);// вызов метода Шелла
            PrintArray(smallArrShell);// вывод массива
 
            Console.WriteLine("пирамидальная сортировка:");
            int[] smallArrHeap = { 9, 7, 3, 8, 2, 1, 5, 4, 6 };
            HeapSort(smallArrHeap);// вызов пирамидального метода
            PrintArray(smallArrHeap);// вывод массива
 
            Console.WriteLine("быстрая сортировка:");
            int[] smallArrQuick = { 9, 7, 3, 8, 2, 1, 5, 4, 6 };
            QuickSort(smallArrQuick, 0, smallArrQuick.Length - 1);// вызов быстрой сортировки, 0 - началов сортировки, -1 - конец сортировки
            PrintArray(smallArrQuick);// вывод массива
 
            // Измерение времени для сортировки каждого типа массива
            Stopwatch sw = new Stopwatch();// метод для измерения затраченного времени
 
            Console.WriteLine("Сортировка случайного массива с помощью сортировки Шелла:");
            sw.Start();// вызов таймера
            ShellSort(arrShell);// Вызов метода сортировки Шелла и передача ему массива для сортировки.
            sw.Stop();// остановка таймера
            Console.WriteLine($"затраченное время: {sw.ElapsedMilliseconds} ms");// отображение затраченного времени
 
            sw.Reset();// сброс таймера
 
            Console.WriteLine("сортировка случайного массива с помощью пирамидальной сортировки...");
            sw.Start();
            HeapSort(arrHeap);
            sw.Stop();
            Console.WriteLine($"затраченное время: {sw.ElapsedMilliseconds} ms");
 
            sw.Reset();
 
            Console.WriteLine("сортировка случайного массива быстрой сортировкой");
            sw.Start();
            QuickSort(arrQuick, 0, arrQuick.Length - 1);
            sw.Stop();
            Console.WriteLine($"затраченное время: {sw.ElapsedMilliseconds} ms");
 
            Console.WriteLine();
            sw.Reset();
 
            Console.WriteLine("Сортировка уже отсортированного массива методом Шелла");
            sw.Start();
            ShellSort(arrShell);
            sw.Stop();
            Console.WriteLine($"затраченное время: {sw.ElapsedMilliseconds} ms");
 
            sw.Reset();
 
            Console.WriteLine("Сортировка уже отсортированного массива с помощью пирамидальной сортировки");
            sw.Start();
            HeapSort(arrHeap);
            sw.Stop();
            Console.WriteLine($"затраченное время: {sw.ElapsedMilliseconds} ms");
 
            sw.Reset();
 
            Console.WriteLine("Сортировка уже отсортированного массива методом быстрой сортировки...");
            sw.Start();
            QuickSort(arrQuick, 0, arrQuick.Length - 1);// Вызывается метод быстрой сортировки и передается arrQuick и его границы.
            sw.Stop();
            Console.WriteLine($"затраченное время: {sw.ElapsedMilliseconds} ms");
 
            Console.WriteLine();
            sw.Reset();
 
            Console.WriteLine("Сортировка обратного массива с помощью метода сортировки Шелла....");
            Array.Reverse(arrShell);
            sw.Start();
            ShellSort(arrShell);
            sw.Stop();
            Console.WriteLine($"затраченное время: {sw.ElapsedMilliseconds} ms");
 
            sw.Reset();
 
            Console.WriteLine("Сортировка обратно отсортированного массива с помощью метода пирамидальной сортировки");
            Array.Reverse(arrHeap);
            sw.Start();
            HeapSort(arrHeap);
            sw.Stop();
            Console.WriteLine($"затраченное время: {sw.ElapsedMilliseconds} ms");
 
            sw.Reset();
 
            Console.WriteLine("Сортировка обратно отсортированного массива с помощью быстрой сортировки");
            Array.Reverse(arrQuick);
            sw.Start();
            QuickSort(arrQuick, 0, arrQuick.Length - 1);
            sw.Stop();
            Console.WriteLine($"затраченное время: {sw.ElapsedMilliseconds} ms");
        }
        static void ShellSort(int[] arr)// метод сортировки Шелла
        {
            int n = arr.Length; // n= длинне массива
            int gap = n / 2;
            while (gap > 0)
            {
                for (int i = 0; i < n - gap; i++)
                {
                    int j = i + gap;
                    int temp = arr[j];
                    while (j >= gap && arr[j - gap] > temp)
                    {
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    arr[j] = temp;
                }
                gap /= 2;
            }
        }
        static void HeapSort(int[] arr)// метод пирамидальной сортировки
        {
            int n = arr.Length;// делаем кучу
            for (int i = n / 2 - 1; i >= 0; i--)
            {
                Heapify(arr, n, i);
            }
            for (int i = n - 1; i >= 0; i--)//извлекаем элемент, текущий корень в конец массива
            {
                int temp = arr[0];
                arr[0] = arr[i];
                arr[i] = temp;
                Heapify(arr, i, 0);
            }
        }
        static void Heapify(int[] arr, int n, int i)
        {
            int largest = i;// больший элемент как корень
            int l = 2 * i + 1;// левый потомок
            int r = 2 * i + 2;// правый потомок
            if (l < n && arr[l] > arr[largest])// если левый потомок больше корня
            {
                largest = l;
            }
            if (r < n && arr[r] > arr[largest])// если корень больше, чем самый большой
            {
                largest = r;
            }
            if (largest != i)// наибольший элемент не корень
            {
                int swap = arr[i];
                arr[i] = arr[largest];
                arr[largest] = swap;
                Heapify(arr, n, largest);// поддерево
            }
        }
        static void QuickSort(int[] arr, int left, int right)// быстрая сортировка
        {
            if (left < right)
            {
                int pivot = Partition(arr, left, right);// разбиваем массив на 2 части
                QuickSort(arr, left, pivot - 1);// сортировка левой части
                QuickSort(arr, pivot + 1, right);// сортировка правой части
            }
        }
        static int Partition(int[] arr, int left, int right)
        {
            int pivot = arr[right];// выбираем последний элемент
            int i = left - 1;// индекс меньш элемента
            for (int j = left; j < right; j++)
            {
                if (arr[j] < pivot)
                {
                    i++;
                    swap(arr, i, j);
                }
            }
            swap (arr, i+1, right);
            return i + 1;// индекс опорного элемента
        }
        static void swap (int[] arr, int i, int j)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;// меняем местами элеметы массива
        }
        static void PrintArray(int[] arr)
        {
            foreach (int num in arr)
            {
                Console.Write(num + " ");
            }
            Console.WriteLine();
        }
    }
}
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
04.05.2023, 00:41
Ответы с готовыми решениями:

Почему память работает намного медленнее, чем процессор?
Как решают эту проблему?

Почему Excel 2013 работает в 25 раз медленнее чем 2010
Здравствуйте, уважаемые эксперты. Столкнулся с проблемой не могу решить. В Excel 2010 макрос работает 0,218 сек. на стареньком...

Почему Timer в одном приложении работает медленнее, чем в другом?
Привет. Есть сервер и клиент, на сервере работает таймер, каждый 50 миллисекунд он увеличивает значение переменной на 1. Когда запускается...

2
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
04.05.2023, 12:44
Цитата Сообщение от Grafert Посмотреть сообщение
почему быстрая сортировка работает медленнее, чем все остальные, хотя написал вроде верно.
Потому что выбор опорного элемента очень сильно влияет на производительность быстрой сортировки.
При выборе первого или последнего элемента, особенно если все значения в массиве одинаковые или однообразные как увас, сложность алгоритма деградирует до O(n2), т.е. быстрая сортировка работает не лучше "пузырька".
Использовать лучше случайный, середенный или медиану из первого, последнего и серединного.
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38167 / 21102 / 4307
Регистрация: 12.02.2012
Сообщений: 34,690
Записей в блоге: 14
04.05.2023, 13:48
Правильное тестирование так не проводят. Массив нужно взять большой. Выполнять сортировку несколько раз и время усреднить. Вот тогда можно будет сравнивать.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
04.05.2023, 13:48
Помогаю со студенческими работами здесь

Неправильно работает быстрая сортировка,в чём ошибка
procedure BistroV(a:array of integer;min,max:integer); //быстрая возрастание var i,j,zap,ser:integer; begin if (proverka=0) then...

Система работает всё медленнее и медленнее (Ubuntu 14)
Ноут HP PAVILION dv6-6077er Core i7 2630QM 2000 Mhz 8GB DDR3 500Gb TOSHIBA MK5061GSYN ATI Radeon HD 6770М Наверное, уже в...

Почему VB выполняется намного медленнее, чем VBA?
Сделал макрос на VBA в CoreDraw (перебирает объекты, проверяет их свойства итд). Попытался перенести его на VB6. Все работает, но раз в...

Почему одномерные массивы работают медленнее, чем трехмерные
Всегда думал, что работать с многомерными массивами очень тяжелое дело, поскольку когда-то на курсах мне сказали, что операция...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Новые блоги и статьи
http://iceja.net/ математические сервисы
iceja 20.01.2026
Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов
iceja 18.01.2026
Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока
igorrr37 16.01.2026
/ * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит переходные токи и напряжения на элементах схемы. . . .
Восстановить юзерскрипты Greasemonkey из бэкапа браузера
damix 15.01.2026
Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11
Jel 10.01.2026
Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает?
Neotwalker 09.01.2026
В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru