Что нового

Сортировка Шелла

hellm

Новичок
Сообщения
32
Репутация
1
Описание: Сортировка Шелла для двумерного массива
Это одна из самых быстрых соритровок по отношению к классическим(пузырьковая, вставками и пр.).
Картинка:
16.gif


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

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

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

Код/Пример:
Код:
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. Многие предлагали свои решения, ихвы найдете здесь
 

---Zak---

Скриптер
Сообщения
455
Репутация
120
Приветствую.

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

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

А почему не воспользуетесь:
Код:
_ArraySort

Сортировать одномерный или двумерный массив в указанном диапазоне индексов используя алгоритмы quicksort/insertionsort.

Пример:
Код:
Local $avArray[5][3] = [ _
[5, 20, 8], _
[4, 32, 7], _
[3, 16, 9], _
[2, 35, 0], _
[1, 19, 6]]

_ArrayDisplay($avArray, "Массив перед сортировкой" )
_ArraySort($avArray, 0, 0, 0, 0)
_ArrayDisplay($avArray, "Массив после сортировки по возрастанию в колонке 0" )
_ArraySort($avArray, 0, 0, 0, 1)
_ArrayDisplay($avArray, "Массив после сортировки по возрастанию в колонке 1" )
_ArraySort($avArray, 0, 0, 0, 2)
_ArrayDisplay($avArray, "Массив после сортировки по возрастанию в колонке 2" )
 
Автор
H

hellm

Новичок
Сообщения
32
Репутация
1
А есть ли возможность выложить полноценный пример ?

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

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

Код:
#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



Добавлено:
Сообщение автоматически объединено:

Сортировать одномерный или двумерный массив в указанном диапазоне индексов используя алгоритмы quicksort/insertionsort.

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

---Zak---

Скриптер
Сообщения
455
Репутация
120
Спасибо...

Чуть-чуть подправлю:
Код:
$aList = _aa_sort($aList)

заменить на
Код:
$aList = _shellsort($aList)


А почему не воспользуетесь ???
Код:
_ArraySort


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

C2H5OH

AutoIT Гуру
Сообщения
1,473
Репутация
333
Мне не нравится реализация.
hellm, зачем ты взял двумерный массив и применяешь к нему в лоб методы обработки одномерного массива?
Сложность твоего алгоритма S(N3/2) + O(N3/2)
S-операция сортировки, O-операция переноса строки двумерного массива.

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

Что лучше?...
:scratch:
 
Автор
H

hellm

Новичок
Сообщения
32
Репутация
1
C2H5OH [?]

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

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


Хотя и не самая быстрая среди самых быстрых ;)
big.random.speedgraph.2.gif


Источник
 
Верх