Home > Blockchain >  Why is Bubble Sort in C# slower than JavaScript for me?
Why is Bubble Sort in C# slower than JavaScript for me?

Time:03-13

I am new to C# and have been playing around with it. I implemented a bubble sort in C# expecting it to be faster than JavaScript since it is a compiled language, but I am getting much slower speeds.

I am sorting 100,000 numbers.

In C# I am getting a speed of approximately: 1 minute and 30 seconds

C# Code:

using System.Diagnostics;

public class Program {

    public static void Main(string[] args) {

        List<int> randoms = generateRandoms(0, 1000000, 100000);
        Console.WriteLine(randoms.Count);

        Stopwatch stopWatch = new Stopwatch();
        
        stopWatch.Start();
        bubbleSort(randoms);
        stopWatch.Stop();
        TimeSpan timeSpan = stopWatch.Elapsed;
        Console.WriteLine("Total processing time... {0:00}:{1:00}:{2:00}.{3:000}", timeSpan.Hours, timeSpan.Minutes, timeSpan.Seconds, timeSpan.Milliseconds);
        Console.Read();
    }

    static List<int> generateRandoms(int min, int max, int amount) {

        Random rnd = new Random();
        List<int> randoms = new List<int>();

        for (int i = 0; i < amount; i  ) {
            int r = rnd.Next(min, max 1);
            randoms.Add(r);
        }

        return randoms;
    }


    static List<int> bubbleSort(List<int> list) {
        //Bubble sort
        for (int i = 0; i < list.Count; i  ) {
            for (int j = 0; j < list.Count - i - 1; j  ) {
                if (list[j] > list[j 1]) {
                    int temp = list[j];
                    list[j] = list[j 1];
                    list[j 1] = temp;
                }
            }
        }

        return list;
    }


    static void print(List<int> list) {
        for (int i = 0; i < list.Count; i  ) {
            Console.WriteLine(list[i]);
        }
    }
}

In JavaScript I am getting approximately: 30 seconds

JavaScript Code:

function bubbleSort(array) {

    for (let i = 0; i < array.length; i  ) {
        for (let j = 0; j < array.length-i-1; j  ) {

            if (array[j] > array[j 1]) {
                [array[j], array[j 1]] = [array[j 1], array[j]];
            }
        }
    }
}

function generateRandoms(min, max, n) {
    const arr = [];
    for (let i = 0; i < n; i  ) {
        arr.push(Math.floor(Math.random() * (max-min 1)   min));
    }

    return arr;
}

const array = generateRandoms(0, 1000000, 100000);
console.log(array.length);

const start = new Date();
bubbleSort(array);
const end = new Date();

console.log(`Performance: ${end - start}ms`);

I figured it had to do with the "List" data structure in C#, but after looking into the documentation, it appears all operations I am using in the bubbleSort function are O(1)

Does anyone have an idea why the speeds are much worse in C# for me? I am using .Net v6.0.201. I am also using VSCode for both programs.

CodePudding user response:

C# is as fast if not a little faster than JS when building in release mode. At least on my computer.

Total processing time... 00:01:00.611 : debug bin

Total processing time... 00:00:19.586 : release bin

CodePudding user response:

I figured it had to do with the "List" data structure in C#, but after looking into the documentation, it appears all operations I am using in the bubbleSort function are O(1)

O(1) isn't necessarily fast, it's just constant. Changing the C# code to use an array roughly doubles its speed. Not certain exactly why that is (List uses arrays under the hood) but IIRC arrays are sometimes able to elide bounds checks.

Also, your C# swap is doing a bit more work than your JS swap; you can replace this:

int temp = list[j];
list[j] = list[j 1];
list[j 1] = temp;

with this:

(list[j], list[j 1]) = (list[j 1], list[j]);

The two languages are closer after those changes, but JS still wins; I'm not certain why.

Update: C# is faster for me if I remember to compile in Release mode.

  • Related