Программа Bubble Sort - PullRequest
Новая
       9

Программа Bubble Sort

0 голосов
/ 19 ноября 2018

Я создаю программу пузырьковой сортировки, которая сортирует случайные целые числа в массиве.Предполагается, что массив может содержать до миллиона отсортированных целых чисел.Когда я получу большое число (например, 250000), программа будет сидеть там и никогда ничего не выводить.Код ниже: 

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);
        }
    }
    }

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

1 Ответ

0 голосов
/ 19 ноября 2018

Протестировал код и он работает нормально (проверено 250000 значений). Как указано в комментариях, алгоритм Bubble Sort не самый оптимизированный. Его сложность определяется как: 

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, чем больше значений вам нужно отсортировать, тем больше времени займет сортировка Bubble.

...