Сортировка массива по возрастанию или убыванию - C (СИ)
Формулировка задачи:
Дан одномерный массив состоящий из N целых элементов. Осуществить хип сорт по возрастанию или убыванию.
P.s. как можно больше комментариев)))
Решение задачи: «Сортировка массива по возрастанию или убыванию»
textual
Листинг программы
#include <stdio.h> #include <stdlib.h> #include <time.h> void Print(int*, int); //----------------------------------------------// void DownHeap(int heap[], int i, int n) { //Просеивает элемент номер i вниз в пирамиде heap. //n -- размер пирамиды //Идея в том, что вычисляется максимальный элемент из трёх: // 1) текущий элемент // 2) левый потомок // 3) правый потомок //Если индекс текущего элемента не равен индексу максималь- // ного, то меняю их местами, и перехожу к максимальному //Индекс максимального элемента в текущей тройке элементов: int max = i; //Значение текущего элемента (не меняется): int const value = heap[i]; while (1) { //Рассматривается элемент i и его потомки i*2+1 и i*2+2 //В начале каждой итерации max == i и value == heap[i] int child = (i * 2) + 1; //Индекс левого потомка //Если есть левый потомок и он больше текущего элемента, if ((child < n) && (heap[child] > value)) { max = child; // то он считается максимальным } ++child; //Индекс правого потомка //Если есть правый потомок и он больше максимального, if ((child < n) && (heap[child] > heap[max])) { max = child; // то он считается максимальным } //Если текущий элемент является максимальным из трёх // (т.е. если он больше своих детей), то конец: if (max == i) { break; } //Меняю местами текущий элемент с максимальным: heap[i] = heap[max]; heap[max] = value; // при этом значение value будет в ячейке max, // поэтому в начале следующей итерации значение value // правильно, т.к. мы переходим именно к этой ячейке //Переходим к изменившемуся потомку i = max; } } //----------------------------------------------// void HeapSort(int heap[], int n) { //Пирамидальная сортировка массива heap. // n -- размер массива int i; //Этап 1: построение пирамиды из массива for (i = n / 2 - 1; i >= 0; --i) { DownHeap(heap, i, n); } //Этап 2: сортировка с помощью пирамиды. // Здесь под «n» понимается размер пирамиды while (n > 1) //Пока в пирамиде больше одного элемента { --n; //Отделяю последний элемент //Меняю местами корневой элемент и отделённый: int tmp = heap[0]; heap[0] = heap[n]; heap[n] = tmp; //Просеиваю новый корневой элемент: DownHeap(heap, 0, n); } } //----------------------------------------------// void Random(int* a, int n) { int i; for (i = 0; i < n; i++) { a[i] = rand() % (n * 2); } } //----------------------------------------------// void Print(int* a, int n) { int i; for (i = 0; i < n; i++) { printf("%3d ", a[i]); } printf("\n"); } //----------------------------------------------// int main(int argc, char** argv) { srand(time(NULL)); int* a = NULL; int n; printf("n: "); scanf("%d", &n); a = malloc(sizeof(int) * n); Random(a, n); Print(a, n); HeapSort(a, n); Print(a, n); return 0; }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д