Головна

Пирамидалы сұрыптау алгоритмі (Heap_sort) және оның ерекшеліктері

  1. D) изоморфты және аморфты
  2. RADIX әдісімен сұрыптау алгоритмі.
  3. Азақстан Ұлттық банкінің өкілеттілігі және құқықтары
  4. Азақстан Ұлттық Банкінің міндеттері мен функциялары және оларды Агенттікпен бөлісуі.
  5. Азақстандағы бокситтың және алюминий тотығын өндіретін басқа шикізатардың қорлары
  6. Айналма қисықтардың негізгі элементтерінің есебі және оларды бөлу.
  7. Аккордық енбекақының мәнін ашыңыз, оның негізгі ерекшеліктері қандай?

Сұрыптау (Сортировка; sorting) - массив элементтерін белгілі бір заңдылықпен орындарын ауыстырып реттеупроцессін айтамыз. Мысалы, сандар массивін өсуі, кемуі бойынша сұрыптау, жолдар массивін алфавит бойынша сұрыптау және тағы басқа. Сұрыптау мақсаты - көптеген сұрыпталған обьектінің ішінен белгілі бір элементті іздеуді оңайлату. Ақпараттық жүйелерде мәліметтерді сұрыптаудың маңызы өте зор.

Пирамидалық сұрыптау алгоритмі таңдаумен сұрыптау алгоритмі классына жатады. Бірақ бұл алгоритмнің өзінің ерекше қасиеті бар. Біріншіден, бастапқы массив бинарлы ағашпен беріледі. Бұл бинарлы ағаш құрылысы жағынан ерекшеленіп келеді, ондай ағаштарды толықтау ағаштар деп атайды.

Реттеу процессі екі этаптан тұрады. Бірінші этапта пирпмида тәріздес ағаш түзіледі. 1-этаптың нәтижесі келесі қасиетге ие пирамида болады: ағаш түбірінен қорытынды төбеге шығатын кез-келген жолында түйіндер кемімелі, дәлелдеп айтқанда өспелі емес ретпен орналасады; пирамида ағаштың жоғарыдан төменге, сол жақтан оңға қарай түзіледі. 2-этапта құрылған ағаш-пирамидасында түйінд/іне бекітілген.

Массив элементтеріне түпкілікті реттеуге пайдаланылады. Бұл этапта пирамиданың элементтерін реттеу бағыты пирамиданың оң жағынан солға қарай, төменнен жоғарыға қарай қажет болған жағдайда алмастырылады. Екінші этап бірінші фазадан тұрады. Бірінші фазада массивтің реттелмеген бөлігіндегі ағымдық максималды элемент (бұл фазада оның пирамиданың төбесінде орналасқанын ұмытпау керек) пирамиданың төменгі оң бұрышында орналасқан элементпен алмастырылады. Сөйтіп ағымдық максималды элемент реттелген массивте өзінің орнын табады. Осыдан кейін бұл максималды элемент те, оның орны да реттеуге қарастырылмайды. 2-этаптың 1-фазасының нәтижесінде пирамиданың төбесінде, яғни ағаштың түбірінде, оның құрылысының бұзылуына кездесеміз. Сондықтан 2-фазада өзгенген пирамиданың құрылысы қайтадан құралады.

static void HeapSort(int[] a)

{

int i;

int temp;

for (i = a.Length / 2 - 1; i >= 0; i--)

{

shiftDown(a, i, a.Length);

}

for (i = a.Length - 1; i >= 1; i--)

{

temp = a[0];

a[0] = a[i];

a[i] = temp;

shiftDown(a, 0, i);

}

}

static void shiftDown(int[] a, int i, int j)

{

bool done = false;

int maxChild;

int temp;

while ((i * 2 + 1 < j) && (!done))

{

if (i * 2 + 1 == j - 1)

maxChild = i * 2 + 1;

else if (a[i * 2 + 1] > a[i * 2 + 2])

maxChild = i * 2 + 1;

Else

maxChild = i * 2 + 2;

if (a[i] < a[maxChild])

{

temp = a[i];

a[i] = a[maxChild];

a[maxChild] = temp;

i = maxChild;

}

Else

{

done = true;

}

}

}

 



RADIX әдісімен сұрыптау алгоритмі. | Жұп-тақ әдісімен сұрыптау алгоритмін сипаттаңыз.

Жоғарғы деңгейдегі өндірістік әмбебап және арнайы ЭЕМ, Арнайы есептегіш комплекстер архитектурасын көрсетіңіз. | Математикалық модельдердің есептеу техникасында қолдану рөлін көрсетіңіз. Классификациясын жазыңыз. | Арнайы есептеуіш комплекстер архитектурасы. | Көпіршіктер әдісімен сұрыптау алгоритмін сипаттаңыз. Көпіршіктер әлісін flag-ті пайдаланып оңтайландырыңыз. | Ою әдісімен сұрыптау алгоритмін сипаттаңыз. | Таңдау әдісімен сұрыптау алгоритмін сипаттаңыз. | Біріктіру әдісімен сұрыптау алгоритмін сипаттаңыз. | Тез сұрыптау әдісінің алгоритмін сипаттаңыз. | Шелл әдісімен сұрыптау алгоритмін сипаттаңыз. | Шайқау әдісімен сұрыптау алгоритмі. |

© 2016-2022  um.co.ua - учбові матеріали та реферати