Bubble Sort Program

Question

I am creating a bubble sort program which sorts random integers in an array. The array is supposed to be able to hold up to a million sorted integers. When I get to a high number (for example, 250,000) the program will sit there and never output anything. Code is below:

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

I usually wait for awhile while the program is running but it seems to be freezing with larger arrays. Any help on why would be greatly appreciated.

Answer 1

Tested the code and it runs fine (tested 250000 values). As pointed in the comments The Bubble Sort algorithm is not the most optimized one. Its complexity is given by:

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

The outer for loop will do N loops. The inner for loop will do N loops. The big O notation will have a complexity of N*N , therefore we have O(N^2).

With 250000 values there will be 62,500,000,000 iterations.

Keeping that in mind the complexity (time taken if you will) is directly proportional to the number of values N, the more values you need to sort the longer the Bubble sort will take to complete.