Упражнения на алгоритме поиска и сортировки C # Sharp: Bogosort
Алгоритм поиска и сортировки C # Sharp: упражнение-2 с решением
Напишите программу на C # Sharp для сортировки списка элементов с помощью сортировки Bogosort.
В информатике bogosort - это особенно неэффективный алгоритм сортировки, основанный на парадигме генерации и тестирования. Алгоритм последовательно генерирует перестановки своего ввода, пока не найдет отсортированный. Это не полезно для сортировки, но может использоваться в образовательных целях, чтобы противопоставить его другим более реалистичным алгоритмам.
Существуют две версии алгоритма: детерминированная версия, которая перечисляет все перестановки, пока не достигнет отсортированной, и рандомизированная версия, которая случайным образом переставляет свои входные данные. Аналогия для работы последней версии заключается в сортировке колоды карт, подбрасывая колоду в воздух, подбирая карты случайным образом и повторяя процесс, пока колода не отсортирована. Его название происходит от слова фиктивный.
Пример решения :
C # острый код:
using System;
using System.Collections.Generic;
namespace Bogo_sort
{
class Program
{
static void Main(string[] args)
{
List<int> list = new List<int>() { 2, 1, 3, 0 };
Console.WriteLine("Sorting...");
Bogo_sort(list, true, 5);
Console.WriteLine("Press any key to exit.");
Console.ReadKey();
}
static void Bogo_sort(List<int> list, bool announce, int delay)
{
int iteration = 0;
while (!IsSorted(list))
{
if (announce)
{
Print_Iteration(list, iteration);
}
if (delay != 0)
{
System.Threading.Thread.Sleep(Math.Abs(delay));
}
list = Remap(list);
iteration++;
}
Print_Iteration(list, iteration);
Console.WriteLine();
Console.WriteLine("Bogo_sort completed after {0} iterations.", iteration);
}
static void Print_Iteration(List<int> list, int iteration)
{
Console.Write("Bogo_sort iteration {0}: ", iteration);
for (int i = 0; i < list.Count; i++)
{
Console.Write(list[i]);
if (i < list.Count)
{
Console.Write(" ");
}
}
Console.WriteLine();
}
static bool IsSorted(List<int> list)
{
for (int i = 0; i < list.Count - 1; i++)
{
if (list[i] > list[i + 1])
{
return false;
}
}
return true;
}
static List<int> Remap(List<int> list)
{
int temp;
List<int> newList = new List<int>();
Random r = new Random();
while (list.Count > 0)
{
temp = (int)r.Next(list.Count);
newList.Add(list[temp]);
list.RemoveAt(temp);
}
return newList;
}
}
}
Пример вывода:
Сортировка... Bogo_sort итерация 0: 2 1 3 0 Bogo_sort итерация 1: 3 1 0 2 Bogo_sort итерация 2: 1 2 3 0 Bogo_sort итерация 3: 0 2 3 1 Bogo_sort итерация 4: 2 1 0 3 Bogo_sort итерация 5: 2 3 3 Bogo_sort итерация 6: 3 1 2 0 Bogo_sort итерация 7: 1 3 0 2 Bogo_sort итерация 8:20 1 3 Bogo_sort итерация 9: 1 2 3 0 Bogo_sort итерация 10: 0 2 3 ---- Bogo_sort итерация 38: 1 3 3 2 Bogo_sort итерация 39: 0 1 2 3 Bogo_sort завершен после 39 итераций. Нажмите любую клавишу для выхода.
Блок - схема:
Редактор кода C # Sharp:
Внесите свой код и комментарии через Disqus.
Предыдущая: Напишите программу на C # Sharp для сортировки списка элементов с помощью сортировки Shell.
Далее: Напишите программу на C # Sharp для сортировки списка элементов с помощью Bubble sort.
Каков уровень сложности этого упражнения?
Новый контент: Composer: менеджер зависимостей для PHP , R программирования