Быстрая сортировка

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

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

1. Из массива выбирается элемент a[i]. Как правило, в качестве этого элемента берется центральный элемент массива.

2. Остальные элементы распределяются таким образом, чтобы слева от a[i] оказались все элементы, меньшие или равные a[i]. Элементы, большие или равные a[i], помещаются справа.
В результате массив будет выглядеть так:
Массив после второго шага сортировки

3. Производится проверка количества элементов в левой и правой частях массива. Если какая-либо часть (или обе части) содержит более двух элементов, то для этой части (или частей) запускается та же процедура сортировки с помощью рекурсивного вызова.

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

Класс QuickSorting, содержащий функцию быстрой сортировки, и класс Test для тестирования этой функции:

class QuickSorting {
   public static void sorting(double[] arr, long first, long last) {
      double p = arr[(last - first)/2 + first];
      double temp;
      long i = first, j = last;
      while(i <= j) {
         while(arr[i] < p && i <= last)  ++i;
         while(arr[j] > p && j >= first) --j;
            if(i <= j) {
               temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
               ++i; --j;
            }
      }
      if(j > first) sorting(arr, first, j);
      if(i < last)  sorting(arr, i, last);
   }
}

class Test {
   static void Main(string[] args) {
      double[] arr = new double[100];
      //заполняем массив случайными числами
      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 + " ");
      }
      //сортировка
      QuickSorting.sorting(arr, 0, arr.Length - 1);
      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();
   }
}

На главную

Хостинг от uCoz