Пирамидальная сортировка

На главную
Содержание

Пошаговое описание алгоритма

1. Построение пирамиды
Пирамида представляет собой дерево, в котором каждый узел имеет не более двух потомков, причем узел всегда больше или равен своим потомкам (таким образом, на вершине дерева всегда находится наибольший элемент).

Если в исходном массиве n элементов, то последние (n / 2) элемента становятся основанием пирамиды (эти элементы являются листьями дерева, т.е. у них нет потомков, поэтому для них вышеуказанное правило выполняется автоматически).

Удобнее всего поместить пирамиду в массив. При этом распределение индексов массива по узлам дерева будет выглядеть так (на этом рисунке все цифры - это индексы элементов массива, а ни в коем случае не значения этих элементов):
Индексирование узлов дерева

Таким образом, для того, чтобы каждый узел дерева был больше своих потомков, каждый элемент массива a[i] должен быть больше или равен элементам a[2 * i + 1] и a[2 * i + 2].

2. Сортировка
В этой части алгоритма мы перемещаем в конец массива максимальный элемент, затем исключаем его из дальнейшего процесса сортировки. Поскольку максимальный элемент всегда находится на вершине пирамиды, мы должны поменять местами элементы a[0] и a[n-1] (т.е. последний элемент). Причем элемент a[n-1] необходимо добавлять так, чтобы не нарушился порядок пирамиды (при этом пирамиду придется частично перестроить). Далее мы будем рассматривать массив только до (n-2)-го элемента.
На следующем шаге мы меняем местами a[0] и a[n-2] и далее рассматриваем массив только до (n-3)-го элемента. Повторяем всю эту процедуру до тех пор, пока в рассматриваемой части массива не останется один элемент.

Реализация на C#

Класс PyramidSorting, содержащий функцию пирамидальной сортировки, и класс Test для тестирования этой функции:


class PyramidSorting {
   //add 1 element to the pyramid
   static int add2pyramid(double[] arr, int i, int N) {
      int imax;
      double buf;
      if((2*i+2) < N) {
         if(arr[2*i+1] < arr[2*i+2]) imax = 2 * i + 2;
         else imax = 2 * i + 1;
      }
      else imax = 2 * i + 1;
      if(imax >= N) return i;
      if(arr[i] < arr[imax]) {
         buf = arr[i];
         arr[i] = arr[imax];
         arr[imax] = buf;
         if(imax < N/2)i = imax;
      }
      return i;
   }
   public static void sorting(double[] arr, int len) {
      //step 1: building the pyramid
      for(int i = len/2 - 1; i >= 0; --i) {
         long prev_i = i;
         i = add2pyramid(arr, i, len);
         if(prev_i != i) ++i;
      }

      //step 2: sorting
      double buf;
      for(int k = len-1; k > 0; --k) {
         buf = arr[0];
         arr[0] = arr[k];
         arr[k] = buf;
         int i = 0, prev_i = -1;
         while(i != prev_i) {
            prev_i = i;
            i = add2pyramid(arr, i, k);
         }
      }
   }
}

class Test {
   static void Main(string[] args) {
      double[] arr = new double[100];

      //fill the array with random numbers
      Random rd = new Random();
      for(int i = 0; i < arr.Length; ++i) {
         arr[i] = rd.Next(1, 101);
      }
      System.Console.WriteLine("The array before sorting:");
      foreach(double x in arr) {
         System.Console.Write(x + " ");
      }
      PyramidSorting.sorting(arr, arr.Length);
      System.Console.WriteLine("\n\nThe array after sorting:");
      foreach(double x in arr) {
         System.Console.Write(x + " ");
      }
      System.Console.WriteLine("\n\nPress the <Enter> key");
      System.Console.ReadLine();
   }
}

Функция add2pyramid() добавляет один элемент к пирамиде, перестраивая ее таким образом, чтобы не нарушалось правило, согласно которому узел не может быть меньше своих потомков.
Функция sorting() отвечает непосредственно за сортировку.

На главную

Хостинг от uCoz