Реализации алгоритмов/Сортировка/Быстрая: различия между версиями
Содержимое удалено Содержимое добавлено
Val5-94 (обсуждение | вклад) |
|||
Строка 4:
В качестве опорного элемента следует выбирать случайный элемент массива, чтобы получить гарантированное время сортировки <math>\Theta(n \log n)</math> в среднем. В случае, если использование случайных чисел нежелательно, в качестве опорного элемента можно выбрать, например, элемент в середине массива, но такие алгоритмы всё равно будут работать за <math>\Theta(n^2)</math> времени на некоторых специально-сконструированных массивах.
==
Работает для произвольного массива из n целых чисел.
<source lang="vb.net" line="1">
Sub QSort(ByRef arr As Variant, ByVal iLbound As Integer, iUbound As Integer)
Dim iL As Integer, iU As Integer
Dim iVal As Integer, iSwap As Integer
iL = iLbound: iU = iUbound
iVal = arr((iLbound + iUbound) \ 2)
Do While iL <= iU
Do While arr(iL) < iVal And iL < iUbound
iL = iL + 1
Loop
Do While iVal < arr(iU) And iU > iLbound
iU = iU - 1
Loop
If iL <= iU Then
iSwap = arr(iL)
arr(iL) = arr(iU)
arr(iU) = iSwap
iL = iL + 1
iU = iU - 1
End If
Loop
If iLbound < iU Then
Call QSort(arr, iLbound, iU)
End If
If iL < iUbound Then
Call QSort(arr, iL, iUbound)
End If
End Sub
</source>
Исходный вызов функции qs для массива из n элементов будет иметь следующий вид.
<source lang="cpp">
qs(a, 0, n-1);
</source>
==[[C Sharp|C#]]==
<source lang="csharp">
int partition (int[] array, int start, int end)
{
int temp;//swap helper
int marker = start;//divides left and right subarrays
for ( int i = start; i <= end; i++ )
{
if ( array[i] < array[end] ) //array[end] is pivot
{
temp = array[marker]; // swap
array[marker] = array[i];
array[i] = temp;
marker += 1;
}
}
//put pivot(array[end]) between left and right subarrays
temp = array[marker];
array[marker] = array[end];
array[end] = temp;
return marker;
}
void quicksort (int[] array, int start, int end)
{
if ( start >= end )
{
return;
}
int pivot = partition (array, start, end);
quicksort (array, start, pivot-1);
quicksort (array, pivot+1, end);
}
</source>
==[[Язык Си в примерах|C]]==
Работает для произвольного массива из n целых чисел.
| |||