I am working on a project that compares the time bubble and selection sort take. I made two separate programs and combined them into one and now bubble sort is running much faster than selection sort. I checked to make sure that the code wasn't just giving me 0s because of some conversion error and was running as intended. I am using System.Diagnostics; to measure the time. I also checked that the machine was not the problem, I ran it on Replit and got similar results.

{
    class Program
    {
       public static int s1 = 0;
       public static int s2 = 0;
        static decimal bubblesort(int[] arr1)
        {
            int n = arr1.Length;
            var sw1 = Stopwatch.StartNew();
            for (int i = 0; i < n - 1; i  )
            {
                for (int j = 0; j < n - i - 1; j  )
                {
                    if (arr1[j] > arr1[j   1])
                    {
                        int tmp = arr1[j];
                        // swap tmp and arr[i] int tmp = arr[j];
                        arr1[j] = arr1[j   1];
                        arr1[j   1] = tmp;
                        s1  ;
                    }
                }
            }
            sw1.Stop();
            // Console.WriteLine(sw1.ElapsedMilliseconds);
            decimal a = Convert.ToDecimal(sw1.ElapsedMilliseconds);
            return a;
        }

        static decimal selectionsort(int[] arr2)
        {
            int n = arr2.Length;
            var sw1 = Stopwatch.StartNew();
            for (int e = 0; e < 1000; e  )
            {

                for (int x = 0; x < arr2.Length - 1; x  )
                {
                    int minPos = x;
                    for (int y = x   1; y < arr2.Length; y  )
                    {
                        if (arr2[y] < arr2[minPos])
                            minPos = y;
                    }
                    if (x != minPos && minPos < arr2.Length)
                    {
                        int temp = arr2[minPos];
                        arr2[minPos] = arr2[x];
                        arr2[x] = temp;
                        s2  ;
                    }
                }

            }
            sw1.Stop();
           // Console.WriteLine(sw1.ElapsedMilliseconds);
            decimal a = Convert.ToDecimal(sw1.ElapsedMilliseconds);
            return a;
        }
        static void Main(string[] args)
        {
            Console.WriteLine("Enter the size of n");
            int n = Convert.ToInt32(Console.ReadLine());
            Random rnd = new System.Random();
            decimal bs = 0M;
            decimal ss = 0M;
            int s = 0;
            int[] arr1 = new int[n];
            int tx = 1000; //tx is a variable that I can use to adjust sample size
            decimal tm = Convert.ToDecimal(tx);

            for (int i = 0; i < tx; i  )
            {

                for (int a = 0; a < n; a  )
                {
                    arr1[a] = rnd.Next(0, 1000000);
                }

                

                ss  = selectionsort(arr1);
                bs  = bubblesort(arr1);
            }

            bs = bs / tm;
            ss = ss / tm;

            Console.WriteLine("Bubble Sort took "   bs   " miliseconds");
            Console.WriteLine("Selection Sort took "   ss   " miliseconds");


        }
    }
}

What is going on? What is causing bubble sort to be fast or what is slowing down Selection sort? How can I fix this?

CodePudding user response：

It looks like you're passing in the sorted array into Bubble Sort. Because arrays are passed by reference, the sort that you're doing on the array is editing the same contents of the array that will be eventually passed into bubble sort.

Make a second array and pass the second array into bubble sort.

CodePudding user response：

To solve your intial problem you just need to copy your arrays, you can do this easily with ToArray();

Creates an array from a IEnumerable.

ss  = selectionsort(arr1.ToArray());
bs  = bubblesort(arr1.ToArray());

However lets learn how to do a more reliable benchmark with BenchmarkDotNet

• BenchmarkDotNet Nuget
• Official Documentation

Given

public class Sort
{
   public static void BubbleSort(int[] arr1)
   {
      int n = arr1.Length;
      for (int i = 0; i < n - 1; i  )
      {
         for (int j = 0; j < n - i - 1; j  )
         {
            if (arr1[j] > arr1[j   1])
            {
               int tmp = arr1[j];
               // swap tmp and arr[i] int tmp = arr[j];
               arr1[j] = arr1[j   1];
               arr1[j   1] = tmp;
            }
         }
      }
   }

   public static void SelectionSort(int[] arr2)
   {
      int n = arr2.Length;
      for (int x = 0; x < arr2.Length - 1; x  )
      {
         int minPos = x;
         for (int y = x   1; y < arr2.Length; y  )
         {
            if (arr2[y] < arr2[minPos])
               minPos = y;
         }

         if (x != minPos && minPos < arr2.Length)
         {
            int temp = arr2[minPos];
            arr2[minPos] = arr2[x];
            arr2[x] = temp;
         }
      }

   }
}

Benchmark Code

[SimpleJob(RuntimeMoniker.Net50)]
[MemoryDiagnoser()]
public class SortBenchmark
{

   private int[] data;

   [Params(100, 1000)]
   public int N;

   [GlobalSetup]
   public void Setup()
   {
      var r = new Random(42);

      data = Enumerable
         .Repeat(0, N)
         .Select(i => r.Next(0, N))
         .ToArray();
   }

   [Benchmark]
   public void Bubble() => Sort.BubbleSort(data.ToArray());

   [Benchmark]
   public void Selection() => Sort.SelectionSort(data.ToArray());
}

Usage

static void Main(string[] args)
{
   BenchmarkRunner.Run<SortBenchmark>();
}

Results

Summary

What have we learnt? Your Bubble sort code is slower ¯\_(ツ)_/¯