CODEWITHSUNDEEP
vb.netperformancesortingbubble-sortinsertion-sort
Ron Southin
Ron Southin

Reputation: 55

bubble vs insertion sort - trying to write a program to determine which is more efficient

i'm trying to compare these 2 sort algorithms. I've written a vb.net console program and used excel to create a csv file of 10000 integers randomly created between 0 and 100000. Insertion sort seems to take approx 10x longer which can't be correct can it? can anyone point out where i'm going wrong?

module Module1

Dim unsortedArray(10000) As integer

sub main
    dim startTick as long
    dim endTick as long

    loadDataFromFile
    startTick = date.now.ticks
        insertionsort
    endTick = date.now.ticks
    console.writeline("ticks for insertion sort = " & (endTick-startTick))  

    loadDataFromFile
    startTick = date.now.ticks
        bubblesort  
    endTick = date.now.ticks
    console.writeline("ticks for bubble sort = " & (endTick-startTick))
end sub

sub bubbleSort
    dim temp as integer 
    dim swapped as boolean 

    dim a as integer = unsortedArray.getupperbound(0)-1
    do 
        swapped=false
        for i = 0 to a
            if unsortedArray(i)>unsortedArray(i+1) then
                temp=unsortedArray(i)
                unsortedArray(i)=unsortedArray(i+1)
                unsortedArray(i+1)=temp
                swapped=true
            end if
        next i
        'a = a - 1          
    loop until not swapped
end sub

sub insertionSort()


    dim temp as string
    dim ins as integer
    dim low as integer = 0
    dim up as integer = unsortedArray.getupperbound(0)

    console.writeline()

    for i = 1 to up
        temp = unsortedArray(i)
        ins = i-1

        while (ins >= 0) andalso (temp < unsortedArray(ins))
            unsortedArray(ins+1) = unsortedArray(ins)
            ins = ins -1
        end while

        unsortedArray(ins+1) = temp
    next
end sub


sub loadDataFromFile()
    dim dataItem as integer                 

    fileopen(1,FileIO.FileSystem.CurrentDirectory & "\10000.csv", openmode.input)
    'set up to loop through each row in the array
    for i = 0 to 9999   
            input(1,dataItem)
            'save that data item in correct array positon
            unsortedArray(i) = dataItem
    next i
    fileclose(1)    
end sub

Upvotes: 3

Views: 145

Answers (1)

J...
J...

Reputation: 31443

dim temp as string

You've declared your temporary variable as a string instead of an integer. VB.Net is perfectly happy to allow you to do this sort of sloppy thing, and it will convert the numeric value to a string and back. This is a very expensive operation.

If you go into your project options, under "Compile", do yourself a favour and turn on "Option Strict". This will disallow implicit type conversions like this and force you to fix it, showing you exactly where you made the error.

"Option Strict" is off by default for legacy reasons, simply to allow badly written legacy VB code to be compiled without complaint in vb.net. There is otherwise no sane reason to leave it turned off.

Changing the declaration to 

 Dim temp As Integer

reveals that the insertion sort is indeed about 3-5 times faster than the bubble on average.

Upvotes: 1

Related Questions