Автор Тема: Сортировка Шелла  (Прочитано 3233 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн hellm [?]

  • Новичок
  • *
  • Сообщений: 32
  • Репутация: 1
    • Награды
Сортировка Шелла
« Создано: Февраль 28, 2014, 14:19:14 »
Описание: Сортировка Шелла для двумерного массива
Это одна из самых быстрых соритровок по отношению к классическим(пузырьковая, вставками и пр.).
Картинка:


   
  • коричневая линия: сортировка пузырьком;
  • синяя линия: шейкер-сортировка;
  • розовая линия: сортировка выбором;
  • желтая линия: сортировка вставками;
  • голубая линия: сортировка вставками со сторожевым элементом;
  • фиолетовая линия: сортировка Шелла.

тут информация к сортировке
Недостаток: неустойчивая.

Эта сортировка для ассоциативного массива, т.е. сортировка только по первой колонке по ключам. Можно передать на любую другую или даже сделать сортировку с выбором колонки.

Код/Пример:
Код: AutoIt [Выделить]
        Local $iStepD[] = [1, 4, 13, 40, 121, 364, 1093, 3280, 9841]

    For $d = UBound($iStepD) - 1 To 0 Step -1
        If $iStepD[$d] < UBound($aTemp) Then
            For $i = $iStepD[$d] To UBound($aTemp) - 1
                For $j = $i To $iStepD[$d] Step - $iStepD[$d]
                    If $aTemp[$j][0] < $aTemp[$j-$iStepD[$d]][0] Then
                        For $k = 0 To UBound($aTemp, 2) - 1
                            $t = $aTemp[$j][$k]
                            $aTemp[$j][$k] = $aTemp[$j-$iStepD[$d]][$k]
                            $aTemp[$j-$iStepD[$d]][$k] = $t
                        Next
                    EndIf
                Next
            Next
        EndIf
    Next



Материалы:
wiki
кафедра Вычислительной Техники НГТУ
Есть разные формы установки gap. Многие предлагали свои решения, ихвы найдете здесь
« Последнее редактирование: Февраль 28, 2014, 14:49:02 от hellm »

Русское сообщество AutoIt

Сортировка Шелла
« Отправлен: Февраль 28, 2014, 14:19:14 »

Оффлайн ---Zak--- [?]

  • Скриптер
  • ****
  • Сообщений: 438
  • Репутация: 111
  • Пол: Мужской
    • Награды
  • Версия AutoIt: 3.3.14.0
Re: Сортировка Шелла
« Ответ #1, Отправлен: Февраль 28, 2014, 14:42:13 »
Приветствую.

А есть ли возможность выложить полноценный пример ?

"?????????????" (4) : ==> Variable used without being declared.:
If $iStepD[$d] < UBound($aTemp) Then
If $iStepD[$d] < UBound(^ ERROR

А почему не воспользуетесь:
Код: AutoIt [Выделить]
Цитировать
Сортировать одномерный или двумерный массив в указанном диапазоне индексов используя алгоритмы quicksort/insertionsort.

Пример:
(нажмите для показа/скрытия)
« Последнее редактирование: Февраль 28, 2014, 15:05:49 от ---Zak---, Причина: Объединение сообщений »
OS: WinXp SP3 (RUS), Win7 (x86/x64)


My development:
http://autoit-script.ru/index.php/topic,11541.0.html

Оффлайн hellm [?]

  • Новичок
  • *
  • Сообщений: 32

  • Автор темы
  • Репутация: 1
    • Награды
Re: Сортировка Шелла
« Ответ #2, Отправлен: Февраль 28, 2014, 15:01:37 »
Цитировать
А есть ли возможность выложить полноценный пример ?

Разумеется. Пожалуйста.

Сортировка Шелла, с выводом результатов в виде таблицы.

Код: AutoIt [Выделить]
#include <Array.au3>
Local $x = 10
Local $aList[$x][2]

; создание массива
For $i = 0 To $x - 1
    $aList[$i][0] = Random(0, 10 , 1)
    $aList[$i][1] = Random(0, 10 , 1)
Next

_ArrayDisplay($aList, "Before")

$aList = _shellsort($aList)
_ArrayDisplay($aList, "After")

; Функция:
Func _shellsort($aTarget)

    Local $aTemp = $aTarget
    Local $iStepD[] = [1, 4, 13, 40, 121, 364, 1093, 3280, 9841]
    Local $d, $i, $j, $k, $t

    For $d = UBound($iStepD) - 1 To 0 Step -1
        If $iStepD[$d] < UBound($aTemp) Then
            For $i = $iStepD[$d] To UBound($aTemp) - 1
                For $j = $i To $iStepD[$d] Step - $iStepD[$d]
                    If $aTemp[$j][0] < $aTemp[$j-$iStepD[$d]][0] Then
                        For $k = 0 To UBound($aTemp, 2) - 1
                            $t = $aTemp[$j][$k]
                            $aTemp[$j][$k] = $aTemp[$j-$iStepD[$d]][$k]
                            $aTemp[$j-$iStepD[$d]][$k] = $t
                        Next
                    EndIf
                Next
            Next
        EndIf
    Next

    Return $aTemp

EndFunc



Добавлено: Февраль 28, 2014, 15:03:47
Цитировать
Сортировать одномерный или двумерный массив в указанном диапазоне индексов используя алгоритмы quicksort/insertionsort.

Я не настаиваю, что нужно пользоваться функцией, которую я выложил.

« Последнее редактирование: Февраль 28, 2014, 15:47:05 от hellm »

Оффлайн ---Zak--- [?]

  • Скриптер
  • ****
  • Сообщений: 438
  • Репутация: 111
  • Пол: Мужской
    • Награды
  • Версия AutoIt: 3.3.14.0
Re: Сортировка Шелла
« Ответ #3, Отправлен: Февраль 28, 2014, 15:03:59 »
Спасибо...

Чуть-чуть подправлю:
Код: AutoIt [Выделить]
$aList = _aa_sort($aList)

заменить на
Код: AutoIt [Выделить]
$aList = _shellsort($aList)


А почему не воспользуетесь ???
Код: AutoIt [Выделить]

ЗЫ: Я за любой кипишь - кроме голодовки. Чем-то полезна: не нужно включать библиотеку...

Русское сообщество AutoIt

Re: Сортировка Шелла
« Ответ #3 Отправлен: Февраль 28, 2014, 15:03:59 »

Оффлайн hellm [?]

  • Новичок
  • *
  • Сообщений: 32

  • Автор темы
  • Репутация: 1
    • Награды
Re: Сортировка Шелла
« Ответ #4, Отправлен: Февраль 28, 2014, 15:10:56 »
Цитировать
Чуть-чуть подправлю:

 :) Подправил.

Оффлайн C2H5OH [?]

  • Знаю я тут одно место с офигенными циркулями...
  • AutoIt Гуру
  • *****
  • Сообщений: 1473
  • Репутация: 332
  • Пол: Мужской
    • Награды
  • Версия AutoIt: 3.3.12.0
Re: Сортировка Шелла
« Ответ #5, Отправлен: Февраль 28, 2014, 15:11:08 »
Мне не нравится реализация.
hellm, зачем ты взял двумерный массив и применяешь к нему в лоб методы обработки одномерного массива?
Сложность твоего алгоритма S(N3/2) + O(N3/2)
S-операция сортировки, O-операция переноса строки двумерного массива.

Если бы у меня возникла задача сортировки двумерного массива по индексам, то я бы не заморачивался, выполнил пузырьковую сортировку индексов, а потом обработал бы двумерный массив.
И получил бы сложность алгоритма S(N2) + O(N)

Что лучше?...
 :think:
Рано или поздно все станет понятно, все станет на свои места и выстроится в единую красивую схему, как кружева. Станет понятно, зачем все было нужно, потому что все будет правильно.

Оффлайн hellm [?]

  • Новичок
  • *
  • Сообщений: 32

  • Автор темы
  • Репутация: 1
    • Награды
Re: Сортировка Шелла
« Ответ #6, Отправлен: Февраль 28, 2014, 15:18:44 »
C2H5OH  [?]
Цитировать
Что лучше?...

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

Кстати, забыл отметить :whistle:, что при очень больших массивах сортировка Шелла среди прочих лидер по скорости:


Хотя и не самая быстрая среди самых быстрых  ;)


Источник
« Последнее редактирование: Февраль 28, 2014, 15:28:26 от hellm »

Русское сообщество AutoIt

Re: Сортировка Шелла
« Ответ #6 Отправлен: Февраль 28, 2014, 15:18:44 »

 

Похожие темы

  Тема / Автор Ответов Последний ответ
0 Ответов
2372 Просмотров
Последний ответ Март 26, 2010, 13:37:34
от VitAl2013
2 Ответов
2414 Просмотров
Последний ответ Июнь 23, 2010, 11:55:00
от XpycT
7 Ответов
3780 Просмотров
Последний ответ Сентябрь 07, 2011, 15:24:22
от Yashied
5 Ответов
4975 Просмотров
Последний ответ Октябрь 25, 2011, 19:14:55
от dimachn
10 Ответов
3618 Просмотров
Последний ответ Июль 21, 2013, 16:49:51
от Astel064
5 Ответов
3282 Просмотров
Последний ответ Октябрь 11, 2013, 09:44:43
от madmasles
2 Ответов
1276 Просмотров
Последний ответ Январь 28, 2015, 17:59:18
от shyra1976
2 Ответов
870 Просмотров
Последний ответ Ноябрь 25, 2015, 08:21:55
от xlgrgrc
1 Ответов
481 Просмотров
Последний ответ Февраль 12, 2017, 12:22:04
от axsmak
3 Ответов
773 Просмотров
Последний ответ Август 13, 2017, 21:08:16
от Атос