1 прост подход за сорт.без мест.на елем.е да
поддържаме индексен масив с ключове-те в елем.,достъпни само за сравн.Нека сорт.елем. са в масива data[0],…,data[N-1] и не искаме да ги местим.За да постигнем ефекта на сорт.,използ.
втори масив а от индексите на елем.Започ.с иниц.на a[i]=i, за i=0,…,N-1.Целта на сорт.е да пренаредим
индекс.масив а,така че а[0] да дава индекса на елем.данни с най-малък ключ,и т.н.Така манипулираме индексите вместо записите.
Др.възмож.е да използ.
указатели,т.е.реализ
указателна сорт.За сорт.на масив от елем. указ.сорт.е ⬄на индексната но
с адресите на масива,добавени към вс.индекс.Указ. сорт обаче е по-обща,защото указ.мд сочат навсякъде,а сорт.елем.не е необх.да са фик-сирани по размер.Ако
а е масив от указ. към ключове,тогава викането на сорт.ф-я ще доведе до това,че указ.ще се пренаредят така че ако се обръщаме към тях последов., ще достигнем до ключовете в сорт.ред. Ре-ализ.сравн.като следваме указ.,а размените релиз.чрез размяна на указ.
Глав.причина да използ.индекси или указ. е да избегнем вмешателство в сорт.данни. Мд сорт.файл даже ако всичко което имаме е достъп до него само за четене.Даже с ня-колко масива от индекси или указ.мд сорт. 1 файл по няколко ключа.
Пирамидална сортировка.Базирани на пирамида алгоритми.Конвертиране в пирамида.Сортиране в пирамида.
Един метод който усъвършенства метода на пряката селекция е метода на пирамидалното сортиране. За да говорим обаче за този метод е нужно да
построим структура от данни , която да позволява избирането на най-малкия елемент със сложност О(logn) а не с O(n). Тогава общото време на бързодействието ще е n*O(n*logn) = O(n*logn).
Тази структура също така трябва да позволява бързо да се вкарват нови елементи (за да може да се построи бързо от изходния масив) и да се премахва максималния елемент(той ще се помества във вече сортираната част на масива – неговия десен край).
И така пирамида (Heap) се нарича бинарно дърво с височина k, в което:
Всички възли имат дълбочина k или k-1
При това ниво k-1 е напълно заето, а ниво k е запълнено частично от ляво надясно
Изпълнено е свойството на пирамидата: всеки елемент е по-малък или равен на родителя си
Построяването на пирамидата може да започне от a[k]...a[n], k = [size/2]. Тази част на масива удовлетворява свойството на пирамидата, тъй като не съществуват индекси i,j: i = 2i+1 ( или j = 2i+2 ). Просто заради това че тези индекси са извън границата на масива.
Следва да се отбележи че е неправилно да се казва че a[k]..a[n] се явява пирамида ако се разглежда самостоятелно. Това,
говорейки конкретно, не е вярно: елементтите му могат да са произволни. Свойството на пирамидата се съхранява само в границите на изходния масив a[0]...a[n].
По нататък ще разширяваме част от масива, която има това полезно свойство, като добавяме един елемент на всяка стъпка. Този елемент ще е онзи който предхожда готовата част.
