Сортировка квадратичным выбором

48 35 44 17 23 33 41 10 14 20 22 30 5 12 6 17

Массив разбивается на части по sqrt(n)

48 35 44 17 | 23 33 41 10 | 14 20 22 30 | 5 12 6 17

В каждой группе отыскивается максимальный элемент.

48 35 44 17 | 23 33 41 10 | 14 20 22 30 | 5 12 6 17

Из этих элементов формируется новая группа

48 41 30 17

В ней отыскивается максимальный

48 41 30 17

Он будет максимальным в массиве

48

Этот элемент извлекается

На следующем шаге 48 не учитывается, находится предпоследний: 44 и т.д. Число элементов в группах уменьшается, поэтому отыскивать максимальный проще.

Время работы: N*sqrt(N)

Пример: Сгенерировать массив случайных чисел от 100-1001, и отсортировать его методом квадратичного выбора.

1. public static void Main(string[] args)

2.     {

3.         int N = 10;

4.

5.         //определяем количество групп

6.         int groups = (int) Math.Round(Math.Sqrt(N));

7.

8.         //генерируем массив случайных чисел

9.         Random r = new Random();

10.         int[] A = new int[N];

11.         for (int i = 0; i < N; i++)

12.         {

13.             A[i] = r.Next(100, 1001);

14.         }

15.

16.         //создаем рабочий массив

17.         int[][] W = new int[groups][];

18.

19.         //делим массив на группы

20.         int count = 0;

21.         for (int i = 0; i < groups; i++)

22.         {

23.             //количество элементов в группе

24.             int n = N/groups;

25.             //если есть остаток - увеличиваем n

26.             if (i < N%groups)

27.             {

28.                 n++;

29.             }

30.             W[i] = new int[n];

31.             //вносим элементы в рабочий массив

32.             for (int j = 0; j < n; j++)

33.             {

34.                 W[i][j] = A[j + count];

35.             }

36.             count += n;

37.         }

38.

39.         //вспомогательный массив

40.         int[] B = new int[groups];

41.

42.         //заполнение вспомогательного массива

43.         for (int i = 0; i < groups; i++)

44.         {

45.             //Находим наименьшее и заменяем его на int.MaxValue

46.             B[i] = Min(W[i]);

47.         }

48.

49.         //выходной массив

50.         int[] C = new int[N];

51.

52.         for (int i = 0; i < N; i++)

53.         {

54.             //находим минимум во вспомогательном массиве

55.             int index = MinIndex(B);

56.             //выводим минимум

57.             C[i] = B[index];

58.             //заполняем вспомогательный массив

59.             B[index] = Min(W[index]);

60.         }

61.

62.         //вывод

63.         Console.WriteLine("Исходный массив:");

64.         Console.WriteLine(string.Join(",", A));

65.         Console.WriteLine("Отсортированный массив:");

66.         Console.WriteLine(string.Join(",", C));

67.     }

68.

69.     private static int Min(int[] array)

70.     {

71.         int index = MinIndex(array);

72.         int min = array[index];

73.         array[index] = int.MaxValue;

74.         return min;

75.     }

76.

77.     private static int MinIndex(int[] array)

78.     {

79.         int min = array[0];

80.         int index = 0;

81.         for (int i = 1; i < array.Length; i++)

82.         {

83.             if (min > array[i])

84.             {

85.                 min = array[i];

86.                 index = i;

87.             }

88.         }

89.         return index;

90.     }

Сортировка подсчётом

Алгоритм сортировки подсчетом прост. Подсчитывается количество вхождений всех элементов из диапазона в сортируемый массив, и потом выводятся элементы нужное количество раз. В данной реализации не используется массив сортируемых элементов. После считывания очередного элемента, увеличение счетчика происходит сразу же. Реализация данного алгоритма на C#: using System; using System.Collections.Generic; using System.Linq; using System.Text;

namespace Sort { class Program { static void Main() { int k = 100; // Считываем размер массива, // который необходимо отсортировать int size; size = Convert.ToInt32(Console.ReadLine()); // Динамически выделяем память под // хранение массива размера size int[] c = new int[k]; //считываем строку string str = Console.ReadLine(); //разбиваем по пробелам string[] mas = str.Split(' ');

//строим массив с for (int i = 0; i < size; i++) { c[int.Parse(mas[i])]++; } //бежимся по всему отрезку //с 0 до k-1 for (int i = 0; i < k; i++) { //выводим i c[i] раз for (int j = 0; j < c[i]; j++) { Console.Write(i); Console.Write(' '); } } } } }

3. Сортировка выбором – возможно, самый простой в реализации алгоритм сортировки. Как и в большинстве других подобных алгоритмов, в его основе лежит операция сравнения. Сравнивая каждый элемент с каждым, и в случае необходимости производя обмен, метод приводит последовательность к необходимому упорядоченному виду.

Идея алгоритма очень проста. Пусть имеется массив A размером N, тогда сортировка выбором сводится к следующему:

 

1. берем первый элемент последовательности A[i], здесь i – номер элемента, для первого i равен 1;

2. находим минимальный (максимальный) элемент последовательности и запоминаем его номер в переменную key;

3. если номер первого элемента и номер найденного элемента не совпадают, т. е. если key?1, тогда два этих элемента обмениваются значениями, иначе никаких манипуляций не происходит;

4. увеличиваем i на 1 и продолжаем сортировку оставшейся части массива, а именно с элемента с номером 2 по N, так как элемент A[1] уже занимает свою позицию;

 

 

С каждым последующим шагом размер подмассива, с которым работает алгоритм, уменьшается на 1, но на способ сортировки это не влияет, он одинаков для каждого шага.

 

public void SelectionSort(int[] arr)

{

int min, temp;

int length = arr.Length;

 

for (int i = 0; i < length - 1; i++)

{

min = i;

 

for (int j = i + 1; j < length; j++)

{

if (arr[j] < arr[min])

{

min = j;

}

}

 

if (min!= i)

{

temp = arr[i];

arr[i] = arr[min];

arr[min] = temp;

}

}

}