Оптимизация быстрой сортировки

@ANDANTINO · Регистрация: 22.04.2015

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

Форумчане, помогите чем сможете, преподаватель дал задание реализовать свою быстрою сортировку по медиане из трех над массивом строк объемом 50 Мб. Все вроде бы сделал, а он сказал, что она должна работать еще быстрее чем сейчас. На моем компьютере она прошла примерно за 38 секунд. Просто нет идей как заставить работать ее быстрее. Может кто-то предложит вариант оптимизации чтобы она работала еще быстрее. Буду очень благодарен, так как у самого идей нет.

Основной код:

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
 Stopwatch all = new Stopwatch();
            all.Start();
            OpenFileDialog openFileDialog1 = new OpenFileDialog();
            openFileDialog1.InitialDirectory = Environment.GetFolderPath(Environment.SpecialFolder.DesktopDirectory);
            openFileDialog1.Filter = "txt files (*.txt)|*.txt";
            openFileDialog1.RestoreDirectory = true;
            if (openFileDialog1.ShowDialog() == DialogResult.OK)
            {
                string str = File.ReadAllText(openFileDialog1.FileName, Encoding.Default);
                string[] masNumbers = str.Split(new char[] { ' ', '\n', '\r', '?', '!', ',', '.', '»', '«', ';', ':', '"', '„', '“', '…', '—', '_' }, StringSplitOptions.RemoveEmptyEntries);
                Stopwatch time = new Stopwatch();
                time.Start();
                Task _task = Task.Factory.StartNew(() => Sort<string>.QSort(masNumbers));
                _task.Wait();
                time.Stop();
                StreamWriter writer = new StreamWriter(Environment.GetFolderPath(Environment.SpecialFolder.DesktopDirectory) + @"\SortedFile.txt", true, Encoding.Unicode);
                for (int i = 0; i < masNumbers.Length; i++)
                {
                    writer.Write($"{masNumbers[i]} ");
                }
                all.Stop();
                long all_time = all.ElapsedMilliseconds;
                long timer = time.ElapsedMilliseconds;
                MessageBox.Show($"Сортировка завершена. Времени затрачено на сортировку: {timer} миллисекунд. Времени затрачено всего: {all_time} миллисекунд.", "Оповещение", MessageBoxButtons.OK, MessageBoxIcon.Information);

Вот код быстрой сортировки:

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
public static class Sort<T> where T : IComparable
    {
        public static void QSort(T[] a)
        {
            QuickSort(a, 0, a.Length - 1);
        }
        private static void QuickSort(T[] keys, int left, int right)
        {
            do
            {
                int a = left;
                int b = right;
                int m = a + ((b - a) >> 1);
                CompareSwap(keys, a, m);
                CompareSwap(keys, a, b);
                CompareSwap(keys, m, b);
                T p = keys[m];
 
                do
                {
                    while (keys[a].CompareTo(p) < 0) ++a;
                    while (p.CompareTo(keys[b]) < 0) --b;
                    if (a > b) break;
                    if (a < b)
                    {
                        T t = keys[a]; keys[a] = keys[b]; keys[b] = t;
                    }
                    a++;
                    b--;
                }
                while (a <= b);
                if (b - left <= right - a)
                {
                    if (left < b)
                    {
                        QuickSort(keys, left, b);
                    }
                    left = a;
                }
                else
                {
                    if (a < right)
                    {
                        QuickSort(keys, a, right);
                    }
                    right = b;
                }
            }
            while (left < right);
        }
        private static void CompareSwap(T[] keys, int a, int b)
        {
            if ((a != b) && (keys[a].CompareTo(keys[b])) > 0)
            {
                T t = keys[a]; keys[a] = keys[b]; keys[b] = t;
            }
        }
    }
}

@afront · 08.05.2016, 10:25

Fastest safe sorting algorithm implementation
http://stackoverflow.com/quest... ementation

Добавлено через 56 минут
Кроме того, на codeproject.com есть несколько статей с обсуждением Quick Sort алгоритма применительно к c#

@ANDANTINO · 08.05.2016, 14:44 **[ТС]**

afront, не могли бы вы мне подсказать одну вещь. На codeproject.com есть пример где показана QuickSortWithBubbleSort, там есть момент с условием на выбор сортировки.
http://www.codeproject.com/scr... x?aid=6033
Где в моем коде можно поставить такое условие, только чтобы сильно его не менять.
У самого не получается либо в условие не попадает или программа зависает. Буду очень благодарен, если сможете показать прям в моем коде. Заранее спасибо.

@afront · 08.05.2016, 15:31

Посмотрите, здесь есть пример QuickSortWithBubbleSort
http://www.codeproject.com/Art... BubbleSort

@ANDANTINO · 08.05.2016, 16:00 **[ТС]**

afront, скажите, что я делаю не так по сравнению с тем примером, что вы дали?
Он просто зависает и все, я так понял опять не там условие стоит? Если так, куда его поставить, чтобы все заработало?

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
private static void QuickSort(T[] keys, int left, int right)
        {
            int a = left;
            int b = right;
 
            if (right-left<=20)
            {
                BubbleSort(keys, left, right);
            }
 
            do
            {
                int m = a + ((b - a) >> 1);
                CompareSwap(keys, a, m);
                CompareSwap(keys, a, b);
                CompareSwap(keys, m, b);
                T p = keys[m];
 
                do
                {
                    while (keys[a].CompareTo(p) < 0) ++a;
                    while (p.CompareTo(keys[b]) < 0) --b;
                    if (a > b) break;
                    if (a < b)
                    {
                        T t = keys[a]; keys[a] = keys[b]; keys[b] = t;
                    }
                    a++;
                    b--;
                }
                while (a <= b);
                if (b - left <= right - a)
                {
                    if (left < b)
                    {
                        QuickSort(keys, left, b);
                    }
                    left = a;
                }
                else
                {
                    if (a < right)
                    {
                        QuickSort(keys, a, right);
                    }
                    right = b;
                }
            }
            while (left < right);
        }

@afront · 08.05.2016, 17:01

посмотрите в дебагере, скорее всего зацикливается где то

Добавлено через 10 минут
сделайте отдельный тест с не большим количеством чисел и проверьте все

@ANDANTINO · 09.05.2016, 08:41 **[ТС]**

Вот все таки сделал, добавил переход на другую сортировку при малом кол-ве элементов. Вторая сортировка вставкой, но можно заменить и на любую другую. Выигрыш по времени составил 9 сек, с 38 до 29 сек. Может можно и больше, но я не экспериментировал дальше. Нужно менять число элементов IsortMax для выхода из одной сортировки для перехода в другую, это и даст уменьшение времени.

Ну и конечно же спасибо afront за помощь.

Код программы ниже.

Кликните здесь для просмотра всего текста

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
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
 
namespace Быстрая_сортировка
{
    public partial class Form1 : Form
    {
        private string str = String.Empty;
        private string[] masNumbers;
        private long all_time = 0, timer = 0;
        private Stopwatch all = new Stopwatch();
        private Stopwatch time = new Stopwatch();
        private OpenFileDialog openFileDialog1 = new OpenFileDialog();
        private StreamWriter writer = new StreamWriter(Environment.GetFolderPath(Environment.SpecialFolder.DesktopDirectory) + @"\SortedFile.txt", true, Encoding.Unicode);
        public Form1()
        {
            InitializeComponent();
            openFileDialog1.InitialDirectory = Environment.GetFolderPath(Environment.SpecialFolder.DesktopDirectory);
            openFileDialog1.Filter = "txt files (*.txt)|*.txt";
            openFileDialog1.RestoreDirectory = true;
        }
 
        private void button1_Click(object sender, EventArgs e)
        {
            all.Start();
            if (openFileDialog1.ShowDialog() == DialogResult.OK)
            {
                str = File.ReadAllText(openFileDialog1.FileName, Encoding.Default);
                masNumbers = str.Split(new char[] { ' ', '\n', '\r', '?', '!', ',', '.', '»', '«', ';', ':', '"', '„', '“', '…', '—', '_' }, StringSplitOptions.RemoveEmptyEntries);
                time.Start();
                Task _task = Task.Factory.StartNew(() => Sort<string>.QSort(masNumbers));
                _task.Wait();
                time.Stop();
                for (int i = 0; i < masNumbers.Length; i++)
                {
                    writer.Write($"{masNumbers[i]} ");
                }
                all.Stop();
                all_time = all.ElapsedMilliseconds;
                timer = time.ElapsedMilliseconds;
                MessageBox.Show($"Сортировка завершена. Времени затрачено на сортировку: {timer} миллисекунд. Времени затрачено всего: {all_time} миллисекунд.", "Оповещение", MessageBoxButtons.OK, MessageBoxIcon.Information);
            }
        }
    }
 
    public static class Sort<T> where T : IComparable<T>
    {
        private const int IsortMax = 60;
        public static void QSort(T[] mas)
        {
            QuickSort(mas, 0, mas.Length - 1);
            InsertionSort(mas, 0, mas.Length - 1);
        }
        private static void QuickSort(T[] keys, int left, int right)
        {
            do
            {
                int a = left;
                int b = right;
                int m = a + ((b - a) >> 1);
                CompareSwap(keys, a, m);
                CompareSwap(keys, a, b);
                CompareSwap(keys, m, b);
                T p = keys[m];
 
                do
                {
                    while (keys[a].CompareTo(p) < 0) ++a;
                    while (p.CompareTo(keys[b]) < 0) --b;
                    if (a > b) break;
                    if (a < b)
                    {
                        T t = keys[a];
                        keys[a] = keys[b];
                        keys[b] = t;
                    }
                    a++;
                    b--;
                } while (a <= b);
                if (b - left <= right - a)
                {
                    if (left < b)
                    {
                        QuickSort(keys, left, b);
                    }
                    left = a;
                }
                else
                {
                    if (a < right)
                    {
                        QuickSort(keys, a, right);
                    }
                    right = b;
                }
            }
            while (right - left >= IsortMax);
        }
        private static void InsertionSort(T[] keys, int left, int right)
        {
            for (int i = left + 1; i <= right; ++i)
            {
                T buffer = keys[i];
                int j = i;
                while (j > left && keys[j - 1].CompareTo(buffer) > 0)
                {
                    keys[j] = keys[j - 1];
                    --j;
                }
                keys[j] = buffer;
            }
        }
        private static void CompareSwap(T[] keys, int a, int b)
        {
            if ((a != b) && (keys[a].CompareTo(keys[b])) > 0)
            {
                T t = keys[a]; keys[a] = keys[b]; keys[b] = t;
            }
        }
    }
}

Новые блоги и статьи Все статьи Все блоги /
Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .
Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .

@afront 1498 / 1213 / 821 Регистрация: 29.02.2016 Сообщений: 3,631
	08.05.2016, 10:25
	Fastest safe sorting algorithm implementation http://stackoverflow.com/quest... ementation Добавлено через 56 минут Кроме того, на codeproject.com есть несколько статей с обсуждением Quick Sort алгоритма применительно к c# 0

@ANDANTINO 5 / 5 / 1 Регистрация: 22.04.2015 Сообщений: 57
	08.05.2016, 14:44 [ТС]
	afront, не могли бы вы мне подсказать одну вещь. На codeproject.com есть пример где показана QuickSortWithBubbleSort, там есть момент с условием на выбор сортировки. http://www.codeproject.com/scr... x?aid=6033 Где в моем коде можно поставить такое условие, только чтобы сильно его не менять. У самого не получается либо в условие не попадает или программа зависает. Буду очень благодарен, если сможете показать прям в моем коде. Заранее спасибо. 0

@afront 1498 / 1213 / 821 Регистрация: 29.02.2016 Сообщений: 3,631
	08.05.2016, 15:31
	Сообщение было отмечено ANDANTINO как решение Решение Посмотрите, здесь есть пример QuickSortWithBubbleSort http://www.codeproject.com/Art... BubbleSort 1

@afront 1498 / 1213 / 821 Регистрация: 29.02.2016 Сообщений: 3,631
	08.05.2016, 17:01
	посмотрите в дебагере, скорее всего зацикливается где то Добавлено через 10 минут сделайте отдельный тест с не большим количеством чисел и проверьте все 0

Оптимизация быстрой сортировки

Решение