Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- using System.Threading.Tasks;
- namespace _1.netf {
- class Program {
- static void read(string s, out int value) {
- Console.Write(s);
- value = Convert.ToInt32(Console.ReadLine());
- }
- static void PrintArray(int[] arr) {
- foreach (int elem in arr) {
- Console.Write($"{elem} ");
- }
- Console.WriteLine();
- }
- static void Swap(ref int a, ref int b) {
- int tmp = a;
- a = b;
- b = tmp;
- }
- static void Countingsort(int[] arr, int min_value, int max_value) {
- int count = max_value - min_value + 1;
- int[] counts = new int[count];
- for (int i = 0; i < count; ++i)
- counts[i] = 0;
- for (int i = 0; i < arr.Length; ++i)
- counts[arr[i] - min_value]++;
- int b = 0;
- for (int i = 0; i < count; ++i) {
- for (int j = 0; j < counts[i]; ++j) {
- arr[b++] = i + min_value;
- }
- }
- }
- static void Countingsort(int[] arr, int max_value) {
- Countingsort(arr, 0, max_value);
- }
- static void Bucketsort(int[] arr, int min_value, int max_value, int count) {
- int value = (max_value - min_value + 1) / count;
- Console.WriteLine(value);
- List<int>[] buckets = new List<int>[count];
- for (int i = 0; i < count; ++i)
- buckets[i] = new List<int>();
- for (int i = 0; i < arr.Length; ++i) {
- int id = (arr[i] - min_value) / value;
- if (id >= count)
- id = count - 1;
- //Console.WriteLine($"> id = {id}, value = {value}, arr[i] = {arr[i]}");
- buckets[id].Add(arr[i]);
- }
- for (int i = 0; i < count; ++i)
- buckets[i].Sort();
- int b = 0;
- for (int i = 0; i < count; ++i) {
- foreach (int elem in buckets[i]) {
- arr[b] = elem;
- b++;
- }
- }
- }
- static void Heapify(int[] arr, int len, int i) {
- while (true) {
- int l = 2 * i + 1;
- int r = 2 * i + 2;
- int g = i;
- if (l < len && arr[l] > arr[g])
- g = l;
- if (r < len && arr[r] > arr[g])
- g = r;
- if (g != i) {
- Swap(ref arr[i], ref arr[g]);
- i = g;
- }
- else {
- break;
- }
- }
- }
- static void Heapsort(int[] arr) {
- for (int i = arr.Length - 1; i >= 0; -- i) {
- Heapify(arr, arr.Length, i);
- }
- for (int i = arr.Length - 1; i > 0; -- i) {
- Swap(ref arr[i], ref arr[0]);
- Heapify(arr, i, 0);
- }
- }
- static void Main(string[] args) {
- int min, max, len, count;
- Random rnd = new Random();
- read("Введите минимальное значение: ", out min);
- read("Введите максимальное значение: ", out max);
- read("Введите длину: ", out len);
- int[] arr = new int[len];
- int[] arr_backup = new int[len];
- for (int i = 0; i < len; ++i)
- arr[i] = rnd.Next(min, max + 1);
- arr.CopyTo(arr_backup, 0);
- //Сортировка подсчётом
- Console.WriteLine("Сортировка подсчётом: ");
- Console.WriteLine("Массив до сортировки подсчётом:");
- PrintArray(arr);
- Console.WriteLine();
- Countingsort(arr, min, max);
- Console.WriteLine("Массив после сортировки подсчётом:");
- PrintArray(arr);
- Console.WriteLine();
- //Блочная сортировка
- Console.WriteLine("Блочная сортировка:");
- read("Введите количество блоков: ", out count);
- arr_backup.CopyTo(arr, 0);
- Console.WriteLine("Массив до блочной сортировки:");
- PrintArray(arr);
- Console.WriteLine();
- Bucketsort(arr, min, max, count);
- Console.WriteLine("Массив после блочной сортировки:");
- PrintArray(arr);
- Console.WriteLine();
- //Пирамидальная сортировка
- Console.WriteLine("Пирамидальна сортировка: ");
- arr_backup.CopyTo(arr, 0);
- Console.WriteLine("Массив до пирамидальной сортировки:");
- PrintArray(arr);
- Console.WriteLine();
- Heapsort(arr);
- Console.WriteLine("Массив после пирамидальной сортировки:");
- PrintArray(arr);
- Console.WriteLine();
- }
- }
- }
RAW Paste Data
Copied