Увод у Хеап Сорт ин Ц
Разврставање је техника која се односи на редослед елемената на основу различитих својстава. (Својства попут уређења података у узлазном, силазном или абецедном реду). Један главни пример сортирања о коме можемо размишљати је наручивање предмета током куповине на мрежи. Можемо се односити на цене, популарност, најновије и тако даље. Дакле, постоји много техника за ово позиционирање елемената сортирањем. У овој теми ћемо сазнати о групи сортирања гомиле Ц.
Овде ћемо научити једну од најчешћих техника сортирања, сортирање хеапама, кроз програмски језик Ц.
Логика за Хеап Сорт
Како у ствари можемо да изводимо хрпу врста? Хајде да проверимо у наставку.
Прво, гомила је једна од структура података заснованих на дрвећу. Дрво укључено овде је увек Комплетно Бинарно Дрво. Постоје две врсте гомиле
- Мин - Хеап: Опћенито распоређени у узлазном редослиједу, то јест ако елемент надређеног чвора има вриједност мању од вриједности надређених елемената чвора.
- Мак - Хеап: Опћенито распоређени у силазном редослиједу, то јест ако надређени елемент чвора има вриједност више од оне надређених елемената чвора.
Кораци за сорту хеап-а
- Једном када се добију неорторисани подаци о листи, елементи се организују у структури података хеап или на основу креирања мин-хеап или мак-хеап.
- Први елемент с горње листе додан је у наш низ
- Поново се формира техника структуре података главе као и први корак, а опет се подиже највиши елемент или најмање елемент и додаје се у наш низ.
- Понављајући кораци помажу нам да добијемо низ са сортираном листом.
Програм за сортирање хеаппа у Ц
#include
int main()
(
int h(20), num, i, j, root, t, x;
printf("Enter number of elements :");
scanf("%d", &num);
printf("\nEnter the elements : ");
for (i = 0; i < num; i++)
scanf("%d", &h(i));
// build max heap
for(i=0;i (
x=i;
do
(
root = (x - 1) / 2;
if (h(root) < h(x))
(
t = h(root);
h(root) = h(x);
h(x) = t;
)
x = root;
) while (x != 0);
)
printf("Heap array formed is: ");
for (i = 0; i < num; i++)
printf("%d\t ", h(i));
for (j = num - 1; j >= 0; j--)
(
t = h(0);
h(0) = h(j);
h(j) = t;
root = 0;
do
(
x = 2 * root + 1;
if ((h(x) < h(x + 1)) && x < j-1)
x++;
if (h(root) (
t = h(root);
h(root) = h(x);
h(x) = t;
)
root = x;
) while (x < j);
)
printf("\nThe sorted array is : ");
for (i = 0; i < num; i++)
printf("\t %d", h(i));
)#include
int main()
(
int h(20), num, i, j, root, t, x;
printf("Enter number of elements :");
scanf("%d", &num);
printf("\nEnter the elements : ");
for (i = 0; i < num; i++)
scanf("%d", &h(i));
// build max heap
for(i=0;i (
x=i;
do
(
root = (x - 1) / 2;
if (h(root) < h(x))
(
t = h(root);
h(root) = h(x);
h(x) = t;
)
x = root;
) while (x != 0);
)
printf("Heap array formed is: ");
for (i = 0; i < num; i++)
printf("%d\t ", h(i));
for (j = num - 1; j >= 0; j--)
(
t = h(0);
h(0) = h(j);
h(j) = t;
root = 0;
do
(
x = 2 * root + 1;
if ((h(x) < h(x + 1)) && x < j-1)
x++;
if (h(root) (
t = h(root);
h(root) = h(x);
h(x) = t;
)
root = x;
) while (x < j);
)
printf("\nThe sorted array is : ");
for (i = 0; i < num; i++)
printf("\t %d", h(i));
)#include
int main()
(
int h(20), num, i, j, root, t, x;
printf("Enter number of elements :");
scanf("%d", &num);
printf("\nEnter the elements : ");
for (i = 0; i < num; i++)
scanf("%d", &h(i));
// build max heap
for(i=0;i (
x=i;
do
(
root = (x - 1) / 2;
if (h(root) < h(x))
(
t = h(root);
h(root) = h(x);
h(x) = t;
)
x = root;
) while (x != 0);
)
printf("Heap array formed is: ");
for (i = 0; i < num; i++)
printf("%d\t ", h(i));
for (j = num - 1; j >= 0; j--)
(
t = h(0);
h(0) = h(j);
h(j) = t;
root = 0;
do
(
x = 2 * root + 1;
if ((h(x) < h(x + 1)) && x < j-1)
x++;
if (h(root) (
t = h(root);
h(root) = h(x);
h(x) = t;
)
root = x;
) while (x < j);
)
printf("\nThe sorted array is : ");
for (i = 0; i < num; i++)
printf("\t %d", h(i));
)
Прво тражимо од корисника да унесе број елемената који су узети за сортирање, а затим кориснику дозвољава да унесе различите елементе које треба сортирати.
Придржани кораци
- Следеће на шта се ми фокусирамо је креирање хеап низа, у овом случају мак-хеап низа.
- Главни услов за добијање мак - хеап низа је провјерити да ниједна вриједност родитељског чвора није мања од његове надређене вриједности чвора. Размењиваћемо се док не постигнемо то стање.
- Главна предност у овом комплетном бинарном стаблу је у томе што се левом и десном подређеном чворишту родитељског чвора може приступити са вредностима 2 (и) + 1 и 2 * (и) + 2 вредности. Где сам родитељски чвор.
- Дакле, на тај начин овде постављамо наш коријенски чвор који садржи максималну вриједност на крајњем десном мјесту чворова листа. А онда поново слиједећи исти поступак, тако да сљедећи максимални број сада постаје роот чвор.
- Пратићемо исти поступак све док у низу хрпа не остане само један чвор.
- А онда, сређујемо низ хепа како би формирали савршени сортирани низ у све већем редоследу.
- На крају исписујемо сортирани низ у излазу.
Излаз:
Излаз је приложен испод.
Дозволите да вам покажем сликовни приказ догађаја:
- Унесени подаци су прво представљени у облику једнодимензионалног низа на следећи начин.
- Сликовни приказ формираног бинарног стабла је следећи:
- Сада ћемо се претворити у мак хеап пазећи да су сви надређени чворови увек већи од подређених чворова. Као што је споменуто у излазу под низом сортираним низом, сликовни приказ би био:
- Након тога, заменити ћемо коријенски чвор екстремним чвором лишћа, а затим га избрисати са стабла. Чвор лишћа би био корен сада и поново исти поступак који је уследио да би поново добио највиши елемент у корену
- Дакле, у овом случају се са овог стабла бришу 77 цифара и стављају у наш сортирани низ и процес се понавља.
Наведено смо видели за формирање максимума. Исти процес се такође бави и формацијом низова мин. Као што је горе речено, једина разлика је у односу између елемената родитеља и подређеног чвора.
Можете ли да покушате да формирате врсту хрпе у силазном редоследу?
Закључак
Иако постоји много техника сортирања, сорта гомиле се сматра једном од бољих техника сортирања због своје временске и просторне сложености. Временска сложеност за све најбоље, просечне и најгоре случајеве је О (нлогн), где је сложеност у најбољем случају боља од сложености најгорег случаја Куицксорт-а, а сложеност простора је О (1).
Препоручени чланци
Ово је водич за Хеап Сорт ин Ц. Овде смо расправљали о логици и Кораци за сортирање хеапмента са узорком кода и исписом, заједно са сликовним приказима. Можда ћете такође погледати следеће чланке да бисте сазнали више -
- Хеап Сорт ин Јава
- Избор сортирања у Јави
- Палиндроме ин Ц програм
- Обрасци у Ц програмирању
- Поредај по групи са Ц ++ (алгоритам)
- Хеап Сорт ин Питхон
- Ц Програмирање множења матрице