Сортировка массива по возрастанию или убыванию - 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;
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

10   голосов , оценка 3.8 из 5
Похожие ответы