Сортировка вставками

@Datebailo · Регистрация: 13.05.2016

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

Имеется код сортировки вставками:

C#

  int[] result = new int[arraySort.Length];
            for (int i = 0; i < arraySort.Length; i++)
            {
                int j = i;
                while (j > 0 && result[j - 1] > arraySort[i])
                {
                    result[j] = result[j - 1];
                    j--;
                }
                result[j] = arraySort[i];
            }
            return arraySort;

Есть ли возможность как-то ускорить процесс сортировки? Ибо когда массив около 100.000 и больше, сортировка происходит очень медленно.

@RemX · 27.11.2016, 19:29

Array.Sort(result);

@Datebailo · 27.11.2016, 19:51 **[ТС]**

RemX, а можно подробнее?

@RemX · 27.11.2016, 19:53

Datebailo, Просто вместо своей сортировки, вставь это: Array.Sort(название_массива);

@Datebailo · 27.11.2016, 20:11 **[ТС]**

RemX, cори, но фишка в том, что мне нужен именно этот способ сортировки, только, если есть возможность, то ускорить его в несколько раз.

@RemX · 27.11.2016, 20:16

Datebailo, Тогда сортировка Шелла например

C#

int step = x * y / 2; 
while (step > 0) 
{ 
for (int i = 0; i < (x * y - step); i++) 
{ 
int j = i; 
while (j >= 0 && array[j] > array[j + step]) 
{ 
int temp = array[j]; 
array[j] = array[j + step]; 
array[j + step] = temp; 
j--; 
} 
} 
step = step / 2; 
}

@Datebailo · 27.11.2016, 23:28 **[ТС]**

RemX, ничего не изменилось. Все так же, если сортировать миллион элементов, очень долго думает.

@TopLayer · 27.11.2016, 23:43

Datebailo, перефразирую ваш вопрос: "хочу чтоб медленная сортировка быстро сортировала"

.

@Datebailo · 27.11.2016, 23:45 **[ТС]**

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

@TopLayer · 27.11.2016, 23:48

Datebailo, если вы будете использовать потоки, алгоритм станет другим.

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

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

если есть возможность, то ускорить его в несколько раз.

не получится

@Yuriy_Tevt · 28.11.2016, 01:13

Алгоритм сортировки вставками на больших обьемах медленный. В рамках алгоритма можно сэкономить пару операций за счет оптимизации и будит вместо Н квадрат Н-1 квадрат, но дальше только смена алгоритма.
Можно извратиться попробовав различные полулегенды типа "i++ выполняется медленеей ++ i", но зачастую это может зависить от конфигурции и настроек среды, а выйграш в такт скушает таже среда, так что подобными извращениями можно заниматься на Асме или С, но не С#.

@Datebailo · 28.11.2016, 01:31 **[ТС]**

TopLayer, так может надо привести пример использования сортировки с помощью потоков или просто флудить?

Yuriy_Tevt, благодарность за самый лаконичный ответ.

@TopLayer · 28.11.2016, 01:38

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

мне их использовать не нужно.

А можно узнать, какую задачу вы решаете?

@Datebailo · 28.11.2016, 01:48 **[ТС]**

TopLayer, лабораторная работа в университете: отсортировать массив на 1М и больше элементов методом вставок)

@TopLayer · 28.11.2016, 05:18

Datebailo, вот это пошустрее маленько

C#

        private static unsafe int[] HisSort2(int[] arraySort)
        {
            int[] result = new int[arraySort.Length];
            fixed (int* root = &result[0])
            {
                for (int i = 0; i < arraySort.Length; i++)
                {
                    int j = i;
                    var current = root + j;
                    while (j > 0 && *(current - 1) > arraySort[i])
                    {
                        *current-- = *current;
                        j--;
                    }
                    result[j] = arraySort[i];
                }
            }
            return result;
        }

Добавлено через 5 минут
Исчо быстрее:

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

C#

        private static unsafe int[] HisSort2(int[] arraySort)
        {
            int[] result = new int[arraySort.Length];
            fixed (int* root = &result[0])
            {
                for (int i = 0; i < arraySort.Length; i++)
                {
                    int j = i;
                    var current = root + j;
                    var e = arraySort[i];
                    while (j > 0 && *(current - 1) > e)
                    {
                        *current-- = *current;
                        j--;
                    }
                    result[j] = arraySort[i];
                }
            }
            return result;
        }

Добавлено через 14 минут
Лям за 3 минуты отсортировало

@Datebailo 0 / 4 / 6 Регистрация: 13.05.2016 Сообщений: 58
	28.11.2016, 01:31 [ТС]	12
	TopLayer, так может надо привести пример использования сортировки с помощью потоков или просто флудить? Yuriy_Tevt, благодарность за самый лаконичный ответ. 0

@RemX 9 / 9 / 12 Регистрация: 26.09.2016 Сообщений: 180
	27.11.2016, 19:29	2
	Array.Sort(result); 0

@Datebailo 0 / 4 / 6 Регистрация: 13.05.2016 Сообщений: 58
	27.11.2016, 19:51 [ТС]	3
	RemX, а можно подробнее? 0

@RemX 9 / 9 / 12 Регистрация: 26.09.2016 Сообщений: 180
	27.11.2016, 19:53	4
	Datebailo, Просто вместо своей сортировки, вставь это: Array.Sort(название_массива); 0

@Datebailo 0 / 4 / 6 Регистрация: 13.05.2016 Сообщений: 58
	27.11.2016, 20:11 [ТС]	5
	RemX, cори, но фишка в том, что мне нужен именно этот способ сортировки, только, если есть возможность, то ускорить его в несколько раз. 0

@Datebailo 0 / 4 / 6 Регистрация: 13.05.2016 Сообщений: 58
	27.11.2016, 23:28 [ТС]	7
	RemX, ничего не изменилось. Все так же, если сортировать миллион элементов, очень долго думает. 0

@TopLayer 907 / 664 / 318 Регистрация: 23.10.2016 Сообщений: 1,543
	27.11.2016, 23:43	8
	Datebailo, перефразирую ваш вопрос: "хочу чтоб медленная сортировка быстро сортировала" . 0

@Datebailo 0 / 4 / 6 Регистрация: 13.05.2016 Сообщений: 58
	27.11.2016, 23:45 [ТС]	9
	TopLayer, ну, к примеру сортировку можно ускорить используя процессы, но в данной программе мне их использовать не нужно. Возможно можно использовать потоки для ускорения, если да, тогда как? Или же каким-то образом расширить код так, чтобы хоть немного было быстрее. 0

@TopLayer 907 / 664 / 318 Регистрация: 23.10.2016 Сообщений: 1,543
	27.11.2016, 23:48	10
	Datebailo, если вы будете использовать потоки, алгоритм станет другим. Добавлено через 1 минуту Сообщение от Datebailo если есть возможность, то ускорить его в несколько раз. не получится 0

@Yuriy_Tevt 9 / 9 / 5 Регистрация: 19.01.2016 Сообщений: 33
	28.11.2016, 01:13	11
	Сообщение было отмечено Datebailo как решение Решение Алгоритм сортировки вставками на больших обьемах медленный. В рамках алгоритма можно сэкономить пару операций за счет оптимизации и будит вместо Н квадрат Н-1 квадрат, но дальше только смена алгоритма. Можно извратиться попробовав различные полулегенды типа "i++ выполняется медленеей ++ i", но зачастую это может зависить от конфигурции и настроек среды, а выйграш в такт скушает таже среда, так что подобными извращениями можно заниматься на Асме или С, но не С#. 1

@TopLayer 907 / 664 / 318 Регистрация: 23.10.2016 Сообщений: 1,543
	28.11.2016, 01:38	13
	Сообщение от Datebailo мне их использовать не нужно. А можно узнать, какую задачу вы решаете? 0

	28.11.2016, 05:18

Опции темы

@Datebailo 0 / 4 / 6 Регистрация: 13.05.2016 Сообщений: 58
	28.11.2016, 01:48 [ТС]	14
	TopLayer, лабораторная работа в университете: отсортировать массив на 1М и больше элементов методом вставок) 0

Сортировка вставками

Решение