Реализации алгоритмов/Сортировка/Пирамидальная: различия между версиями
Содержимое удалено Содержимое добавлено
→К переименованию: Использован шаблон. |
|||
Строка 1:
{{К переименованию | 2014-05-02 | Реализации алгоритмов/Сортировка/Пирамидальная}}
{{wikipedia|Пирамидальная сортировка}}
Строка 134 ⟶ 136 :
for ( int i = 0; i < n; ++i ) { a[i] = n - i; cout << a[i] << " "; }
//заполняем массив для наглядности.
//-----------сортировка------------//
//сортирует по-возрастанию. чтобы настроить по-убыванию,
//поменяйте знаки сравнения в строчках, помеченных /*(знак)*/
int sh = 0; //смещение
Строка 148 ⟶ 150 :
if( ( a[i + sh] > /*<*/ a[i * 2 + 1 + sh] ) || ( a[i + sh] > /*<*/ a[i * 2 + 2 + sh] ) )
{
if ( a[i * 2 + 1 + sh] < /*>*/ a[i * 2 + 2 + sh] )
{
iswap( a[i + sh], a[i * 2 + 1 + sh] );
b = true;
}
else if ( a[i * 2 + 2 + sh] < /*>*/ a[ i * 2 + 1 + sh])
{
iswap( a[ i + sh], a[i * 2 + 2 + sh]);
Строка 160 ⟶ 162 :
}
//дополнительная проверка для последних двух элементов
//с помощью этой проверки можно отсортировать пирамиду
//состоящую всего лишь из трех элементов
if( a[i*2 + 2 + sh] < /*>*/ a[i*2 + 1 + sh] )
{
iswap( a[i*2+1+sh], a[i * 2 +2+ sh] );
Строка 177 ⟶ 179 :
}
}
if (!b) sh++; //смещение увеличивается, когда на текущем этапе
//сортировать больше нечего
if ( sh + 2 == n ) break;
} //конец сортировки
cout << endl << endl;
for ( int i = 0; i < n; ++i ) cout << a[i] << " ";
Строка 269 ⟶ 271 :
== C# (другой вариант) ==
<big><source lang="csharp">
public class Heap<T>
{
private T[] _array; //массив сортируемых элементов
private int heapsize;//число необработанных элементов
private IComparer<T> _comparer;
public Heap(T[] a, IComparer<T> comparer){
_array = a;
heapsize = a.Length;
_comparer = comparer;
}
public void HeapSort(){
build_max_heap();//Построение пирамиды
Строка 287 ⟶ 289 :
_array[0] = _array[i];
_array[i] = temp;
heapsize--;//Уменьшим число необработанных элементов
max_heapify(0);//Восстановление свойства пирамиды
}
}
private int parent (int i) { return (i-1)/2; }//Индекс родительского узла
private int left (int i) { return 2*i+1; }//Индекс левого потомка
private int right (int i) { return 2*i+2; }//Индекс правого потомка
//Метод переупорядочивает элементы пирамиды при условии,
//что элемент с индексом i меньше хотя бы одного из своих потомков, нарушая тем самым свойство невозрастающей пирамиды
private void max_heapify(int i){
Строка 304 ⟶ 306 :
int lagest = i;
if (l<heapsize && _comparer.Compare(_array[l], _array[i])>0)
lagest = l;
if (r<heapsize && _comparer.Compare(_array[r], _array[lagest])>0)
lagest = r;
Строка 312 ⟶ 314 :
_array[i] = _array[lagest];
_array[lagest] = temp;
max_heapify(lagest);
}
}
//метод строит невозрастающую пирамиду
private void build_max_heap(){
int i = (_array.Length-1)/2;
while(i>=0){
max_heapify(i);
i--;
}
}
}
Строка 339 ⟶ 341 :
IntComparer myComparer = new IntComparer();//Класс, реализующий сравнение
Heap<int> heap = new Heap<int>(arr, myComparer);
heap.HeapSort();
}
Строка 495 ⟶ 497 :
def heapSort(li):
"""Сортирует список в возрастающем порядке с помощью алгоритма пирамидальной сортировки"""
def downHeap(li, k, n):
new_elem = li[k]
Строка 507 ⟶ 509 :
k = child
li[k] = new_elem
size = len(li)
for i in range(size//2-1,-1,-1):
Строка 521 ⟶ 523 :
<big><source lang="python">
def heapsort(s):
sl = len(s)
def swap(pi, ci):
if s[pi] < s[ci]:
s[pi], s[ci] = s[ci], s[pi]
def sift(pi, unsorted):
i_gt = lambda a, b: a if s[a] > s[b] else b
while pi*2+2 < unsorted:
gtci = i_gt(pi*2+1, # heapify
for i in range((sl/2)-1, -1, -1):
for i in range(sl-1, 0, -1):
</source></big>
| |||