bubble vs insertion sort - пытается написать программу, чтобы определить, какая из них более эффективна

Question

Я пытаюсь сравнить эти 2 алгоритма сортировки. Я написал консольную программу vb.net и использовал excel для создания CSV-файла из 10000 целых чисел, случайно созданных между 0 и 100000. Вставка сортировки, кажется, занимает примерно 10 раз дольше, что не может быть правильно? может ли кто-нибудь указать, где я иду не так?

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 

Answer 1

dim temp as string 

Вы объявили о своей временной переменной как string вместо integer. VB.Net с удовольствием разрешает вам делать эту неряшливую вещь, и она преобразует числовое значение в string и обратно. Это очень дорогостоящая операция.

Если вы заходите в свои варианты проекта, в разделе «Скомпилировать» сделайте себе одолжение и включите «Option Strict». Это будет запрещать неявные преобразования типов, подобные этому, и заставить вас исправить это, показывая вам, где именно вы сделали ошибку.

«Вариант Strict» отключен по умолчанию по причинам, связанным с устаревшими причинами, просто чтобы скомпилировать плохо написанный устаревший код VB без жалобы в vb.net. В противном случае нет разумной причины оставить его выключенным.

Изменение декларации

Dim temp As Integer 

показывает, что введение сортировки действительно примерно в 3-5 раз быстрее, чем в среднем пузырь.