Программа пузырьковой сортировки
Я создаю программу пузырьковой сортировки, которая сортирует случайные целые числа в массиве. Предполагается, что массив может содержать до миллиона отсортированных целых чисел. Когда я доберусь до большого числа (например, 250 000), программа останется там и никогда ничего не выведет. Код ниже:
using System;
namespace SortingProject
{
class MainClass
{
public static void Main(string[] args)
{
//create an array to hold integers
int[] list = new int[50000];
//call random function to populate integer values
Random rand = new Random();
//add integers to array
for (int i = 0; i < list.Length; i++) {
list[i] = rand.Next(1,50000);
}
//call bubble sort method and input the array
BubbleSorting(list);
}
//bubble sort method and logic
public static void BubbleSorting(int[] array)
{
//initialize time start
DateTime start = DateTime.Now;
DateTime end;
end = DateTime.Now;
//initialize element integer
int element = 0;
for (int bubble = 0; bubble < array.Length; bubble++)
{
//create for loop to perform bubble sort
for (int sort = 0; sort < array.Length - 1; sort++)
{
if (array[sort] > array[sort + 1])
{
element = array[sort + 1];
array[sort + 1] = array[sort];
array[sort] = element;
}
}
}
//loop and print array contents
for (int i = 0; i < array.Length; i++)
Console.Write(array[i] + " ");
//calculate time it takes to sort array
end = DateTime.Now;
TimeSpan ts = end.Subtract(start);
Console.WriteLine(" ");
Console.WriteLine("Duration = {0} ms", ts.TotalMilliseconds);
}
}
}
Обычно я жду некоторое время, пока программа запущена, но кажется, что она зависает с большими массивами. Любая помощь о том, почему будет принята с благодарностью.
Обратите внимание, что пузырьковая сортировка составляет O (n ^ 2) по сложности времени выполнения. Это означает, что по мере увеличения размера ввода (длины списка) для вычисления ответа требуется все больше и больше времени. Вы должны увидеть сверхлинейное увеличение времени работы с большими входами. Вы пробовали какие-то другие входы, чтобы узнать, сможете ли вы найти длину, при которой он перестает работать?
для каждого элемента в массиве сделайте что-нибудь с каждым элементом в массиве, подумайте, как это масштабируется. введите в свой калькулятор, количество элементов, затем нажмите кнопку x2, посмотрите, что он делает
Есть ли код, который я мог бы использовать, чтобы показать, что программа все еще работает? Он просто сидит, поэтому трудно понять, работает ли он еще.
Вы можете разместить точки останова, чтобы понять, на что ваш код тратит все время, ИЛИ, поскольку это консольное приложение, вы можете добавить строку вроде if (bubble% 1000 == 0) Console.WriteLine ($ "Все еще выполняется: {пузырь} "); к вашему пузырю за петлей. Он не мертв, ему просто нужно больше времени на обработку.
BubbleSort очень полезен в качестве академического упражнения, чтобы показать, как работает сортировка и как ее можно реализовать на данном языке программирования. Квадратичная временная сложность, как вы обнаружили, является точной причиной того, что этот алгоритм не используется в производственном коде.
Как отмечали другие, время, которое требуется, пропорционально квадрату размера ввода; пузырьковая сортировка, сортирующая десять элементов, сделает около 100 сравнений; пузырьковая сортировка, которая сортирует миллион элементов, сделает около миллиона миллионов сравнений. Если ваша машина может выполнять миллиард сравнений в секунду, это займет около тысячи секунд. Так что вашего наблюдения следовало ожидать.
Для справки в будущем я предлагаю вам использовать класс Stopwatch, а не DateTime.Now для кода синхронизации. DateTime.Now работает с точностью до нескольких миллисекунд, что нормально для вашей ситуации, когда вы запускаете программы, которые занимают секунды, минуты или часы. Но возьмите за привычку использовать Stopwatch для своих нужд по времени, так как он намного точнее.
Ответы 1
Протестировал код, и он работает нормально (проверено 250000 значений). Как указано в комментариях, алгоритм пузырьковой сортировки не самый оптимизированный. Его сложность определяется:
for (int bubble = 0; bubble < array.Length; bubble++)
{
//create for loop to perform bubble sort
for (int sort = 0; sort < array.Length - 1; sort++)
{
\\do logic
}
}
Внешний цикл for будет выполнять N циклов. Внутренний цикл for будет выполнять N циклов. Нотация большого O будет иметь сложность N * N, поэтому у нас O (N ^ 2).
При 250000 значений будет 62 500 000 000 итераций.
Помня об этом, сложность (время, необходимое, если хотите) прямо пропорциональна количеству значений N, чем больше значений вам нужно отсортировать, тем больше времени потребуется для выполнения пузырьковой сортировки.
Может быть, вы просто недооцениваете, что время до завершения масштабирует в прямом смысле экспоненциально O (n ^ 2)?