StoneHaos

praktika_1_sort

Mar 18th, 2021 (edited)
67
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6.  
  7. namespace _1.netf {
  8.     class Program {
  9.  
  10.         static void read(string s, out int value) {
  11.             Console.Write(s);
  12.             value = Convert.ToInt32(Console.ReadLine());
  13.         }
  14.  
  15.         static void PrintArray(int[] arr) {
  16.             foreach (int elem in arr) {
  17.                 Console.Write($"{elem} ");
  18.             }
  19.             Console.WriteLine();
  20.         }
  21.  
  22.         static void Swap(ref int a, ref int b) {
  23.             int tmp = a;
  24.             a = b;
  25.             b = tmp;
  26.         }
  27.  
  28.         static void Countingsort(int[] arr, int min_value, int max_value) {
  29.             int count = max_value - min_value + 1;
  30.             int[] counts = new int[count];
  31.             for (int i = 0; i < count; ++i)
  32.                 counts[i] = 0;
  33.             for (int i = 0; i < arr.Length; ++i)
  34.                 counts[arr[i] - min_value]++;
  35.             int b = 0;
  36.             for (int i = 0; i < count; ++i) {
  37.                 for (int j = 0; j < counts[i]; ++j) {
  38.                     arr[b++] = i + min_value;
  39.                 }
  40.             }
  41.         }
  42.  
  43.         static void Countingsort(int[] arr, int max_value) {
  44.             Countingsort(arr, 0, max_value);
  45.         }
  46.  
  47.         static void Bucketsort(int[] arr, int min_value, int max_value, int count) {
  48.             int value = (max_value - min_value + 1) / count;
  49.  
  50.             Console.WriteLine(value);
  51.  
  52.             List<int>[] buckets = new List<int>[count];
  53.             for (int i = 0; i < count; ++i)
  54.                 buckets[i] = new List<int>();
  55.             for (int i = 0; i < arr.Length; ++i) {
  56.                 int id = (arr[i] - min_value) / value;
  57.                 if (id >= count)
  58.                     id = count - 1;
  59.                 //Console.WriteLine($"> id = {id}, value = {value}, arr[i] = {arr[i]}");
  60.                 buckets[id].Add(arr[i]);
  61.             }
  62.             for (int i = 0; i < count; ++i)
  63.                 buckets[i].Sort();
  64.             int b = 0;
  65.             for (int i = 0; i < count; ++i) {
  66.                 foreach (int elem in buckets[i]) {
  67.                     arr[b] = elem;
  68.                     b++;
  69.                 }
  70.             }
  71.         }
  72.  
  73.         static void Heapify(int[] arr, int len, int i) {
  74.             while (true) {
  75.                 int l = 2 * i + 1;
  76.                 int r = 2 * i + 2;
  77.                 int g = i;
  78.                 if (l < len && arr[l] > arr[g])
  79.                     g = l;
  80.                 if (r < len && arr[r] > arr[g])
  81.                     g = r;
  82.                 if (g != i) {
  83.                     Swap(ref arr[i], ref arr[g]);
  84.                     i = g;
  85.                 }
  86.                 else {
  87.                     break;
  88.                 }
  89.             }
  90.         }
  91.  
  92.         static void Heapsort(int[] arr) {
  93.             for (int i = arr.Length - 1; i >= 0; -- i) {
  94.                 Heapify(arr, arr.Length, i);
  95.             }
  96.             for (int i = arr.Length - 1; i > 0; -- i) {
  97.                 Swap(ref arr[i], ref arr[0]);
  98.                 Heapify(arr, i, 0);
  99.             }
  100.         }
  101.  
  102.         static void Main(string[] args) {
  103.             int min, max, len, count;
  104.             Random rnd = new Random();
  105.  
  106.             read("Введите минимальное значение: ", out min);
  107.             read("Введите максимальное значение: ", out max);
  108.             read("Введите длину: ", out len);
  109.  
  110.             int[] arr = new int[len];
  111.             int[] arr_backup = new int[len];
  112.             for (int i = 0; i < len; ++i)
  113.                 arr[i] = rnd.Next(min, max + 1);
  114.             arr.CopyTo(arr_backup, 0);
  115.  
  116.  
  117.  
  118.             //Сортировка подсчётом
  119.             Console.WriteLine("Сортировка подсчётом: ");
  120.             Console.WriteLine("Массив до сортировки подсчётом:");
  121.             PrintArray(arr);
  122.             Console.WriteLine();
  123.  
  124.             Countingsort(arr, min, max);
  125.  
  126.             Console.WriteLine("Массив после сортировки подсчётом:");
  127.             PrintArray(arr);
  128.             Console.WriteLine();
  129.  
  130.             //Блочная сортировка
  131.             Console.WriteLine("Блочная сортировка:");
  132.             read("Введите количество блоков: ", out count);
  133.  
  134.             arr_backup.CopyTo(arr, 0);
  135.  
  136.             Console.WriteLine("Массив до блочной сортировки:");
  137.             PrintArray(arr);
  138.             Console.WriteLine();
  139.  
  140.             Bucketsort(arr, min, max, count);
  141.  
  142.             Console.WriteLine("Массив после блочной сортировки:");
  143.             PrintArray(arr);
  144.             Console.WriteLine();
  145.  
  146.             //Пирамидальная сортировка
  147.             Console.WriteLine("Пирамидальна сортировка: ");
  148.             arr_backup.CopyTo(arr, 0);
  149.  
  150.             Console.WriteLine("Массив до пирамидальной сортировки:");
  151.             PrintArray(arr);
  152.             Console.WriteLine();
  153.  
  154.             Heapsort(arr);
  155.  
  156.             Console.WriteLine("Массив после пирамидальной сортировки:");
  157.             PrintArray(arr);
  158.             Console.WriteLine();
  159.         }
  160.     }
  161. }
  162.  
RAW Paste Data