Newsgroup: it.comp.lang.visual-basic
Titolo: Insertion Sort

Ciao a tutti,
qualcuno sa dove posso reperire un esempio di codice per l'algoritmo di
Insertion Sort in Visual Basic o al limite in C (purche' non troppo complicato
;-))?
In generale mi servirebbe fare qualche prova con algoritmi di ordinamento
iterativi da usare al posto del Quick Sort (ricorsivo) che uso ora; lo applico
ripetutamente (qualche migliaia di chiamate) su array numerici non piu' grandi
di 200 elementi e temo che in questo caso l'overhead dovuto alle chiamate
ricorsive sia eccessivo rispetto a quello che otterrei con un ciclo... o
sbaglio?
Grazie
--
Luca Dormio
l...@sig-la.com
ldo...@tin.it

 ha scritto nel messaggio
news:89gnkt$ip2$1...@fe1.cs.interbusiness.it...


 Insertion Sort in Visual Basic o al limite in C (purche' non troppo complicato
In coda. Dovrei averlo anche in VB, se ci tieni.
Ho anche i moduli per MergeSort, BubbleSort, SelectionSort
ShellSort; VB o C.
***** INSERTION SORT ******
// Numbers in array data[] are sorted by insertion sort.
// First, value at data[floorIdx] is moved to temp.
// Then value in temp is inserted to first location data[currentIdx]
// where data[curentIdx-1] <= temp.
// The insertion is repeated for 1 <= floorIdx <= data.length - 1.
public class InsertSort {
  static int data[] = { 3, 2, 4, 5, 1, 10, 9, 7, 6, 8 };  // initial data
  static int temp;                // value to be inserted
  static int floorIdx;            // index of value to be inserted
  static int currentIdx = 0;      // index used to find location for insertion
  static void dataPrint() {       // print array content
     System.out.print("run() executed: floorIdx = " + floorIdx
                                       + ", data = ");
      for (int i = 0; i < data.length; i++) {
        System.out.print(data[i]);    // print each value in data[]
        if (i < data.length - 1) System.out.print(", ");
      };
      System.out.println("");
   }
  public static void main(String argv[])
    System.out.println("Sorting (re)started");
    floorIdx = 0;    // floorIdx increases from 1 to data.length - 1
    dataPrint();
    for (floorIdx++; floorIdx < data.length; floorIdx++) {  // perform sorting
      temp = data[floorIdx];  // move value to be inserted to temp
      currentIdx = floorIdx;  // currentIdx decreases from floorIdx to 0
      for ( ; currentIdx >= 0; currentIdx--) {
        if (currentIdx == 0 || data[currentIdx-1] <= temp) {
          data[currentIdx] = temp;  // insert value in temp
          break;
        } else {
          data[currentIdx] = data[currentIdx-1];  // move current value down
        }
      }
      dataPrint();
    }
    System.out.println("Sorting completed");


 > ;-))?


ShellSort; VB o C.
[SNIP]
Grazie mille!!
sono molto interessato anche agli altri, se li hai gia' pronti in VB sarebbe
splendido altrimenti non c'e' problema; con questo livello di C me la riesco a
cavare...
Ciao


piů veloce, anzi!
[SNIP]
Veramente non c'e' un motivo particolare, salvo il fatto che "per sentito dire"
sapevo essere uno di quelli non ricorsivi... l'ho visto in un programma C che
stavo usando come riferimento ma li' veniva applicato su strutture molto
complicate e mi si sono un po' incrociati gli occhi... se potessi trovare degli
esempi perlomeno in C piu' malleabile (tipo quello che ha postato Jimi) sarei a
posto.
Qualsiasi algoritmo mi va bene, tanto devo comunque fare le prove sul campo...
Grazie


> sono molto interessato anche agli altri, se li hai gia' pronti in VB
Te li posto qui, magari servono ad altri.
***************************
Public Sub BubbleSortNumbers(iArray As Variant)
Dim lLoop1 As Long
Dim lLoop2 As Long
Dim lTemp As Long
   For lLoop1 = UBound(iArray) To LBound(iArray) Step -1
      For lLoop2 = LBound(iArray) + 1 To lLoop1
      If iArray(lLoop2 - 1) > iArray(lLoop2) Then
         lTemp = iArray(lLoop2 - 1)
         iArray(lLoop2 - 1) = iArray(lLoop2)
         iArray(lLoop2) = lTemp
         Bcnt = Bcnt + 1
      End If
      Next lLoop2
   Next lLoop1
End Sub
***************************
Public Sub SelectionSortNumbers(vArray As Variant)
Dim lLoop1 As Long
Dim lLoop2 As Long
Dim lMin As Long
Dim lTemp As Long
   For lLoop1 = LBound(vArray) To UBound(vArray) - 1
      lMin = lLoop1
      For lLoop2 = lLoop1 + 1 To UBound(vArray)
      If vArray(lLoop2) < vArray(lMin) Then
         lMin = lLoop2
      End If
      Next lLoop2
      lTemp = vArray(lMin)
      vArray(lMin) = vArray(lLoop1)
      vArray(lLoop1) = lTemp
   Next lLoop1
End Sub
***************************
Public Sub ShellSortNumbers(vArray As Variant)
Dim lLoop1 As Long
Dim lHold As Long
Dim lHValue As Long
Dim lTemp As Long
Dim SHcnt As Integer
   lHValue = LBound(vArray)
   Do
       lHValue = 3 * lHValue + 1
   Loop Until lHValue > UBound(vArray)
   Do
      lHValue = lHValue / 3
      For lLoop1 = lHValue + LBound(vArray) To UBound(vArray)
         lTemp = vArray(lLoop1)
         lHold = lLoop1
         Do While vArray(lHold - lHValue) > lTemp
                vArray(lHold) = vArray(lHold - lHValue)
                lHold = lHold - lHValue
               If lHold < lHValue Then Exit Do
               Loop
               vArray(lHold) = lTemp
         Next lLoop1
   Loop Until lHValue = LBound(vArray)
End Sub
***************************
Public Sub QuickSortNumbers(iArray As Variant, l&, r&)
'iArray() The iArray to sort
'l& First element of iArray to start sort
'r& Last element of iArray to start sort
Dim i&, j&
Dim X
Dim Y
   i& = l&
   j& = r&
   X = iArray((l& + r&) / 2)
   While (i& <= j&)
      While (iArray(i&) < X And i& < r&)
         i& = i& + 1
      Wend
      While (X < iArray(j&) And j& > l&)
         j& = j& - 1
      Wend
      If (i& <= j&) Then
         Y = iArray(i&)
         iArray(i&) = iArray(j&)
         iArray(j&) = Y
         i& = i& + 1
         j& = j& - 1
      End If
   Wend
   If (l& < j&) Then QuickSortNumbers iArray, l&, j&
   If (i& < r&) Then QuickSortNumbers iArray, i&, r&
End Sub


Perfetto; grazie ancora!
Ciao


Per quel che ne so, ci sono algoritmi che 'nel modo piu' naturale'
vengono codificati in modo ricorsivo, ma nulla lo impone veramente e
possono essere sempre (non giuro che sia sempre vero) in modo iterativo.
Di solito la procedura iterativa e' piu' lunga da scrivere (giusta),
piu' rapida da 'debuggare' e MOLTO piu' rapida in esecuzione.
gs

Eccoti una versione di Quicksort ITERATIVO, anche
se a mio avviso, prima che riempi lo stack
con un algoritmo quicksort...considera che non
conta la dimensione delle strutture dati che
ordini, ma solo il numero delle stesse.
In VB3 io ho usato Quicksort su qualche migliaio
di elementi e non ho mai avuto problemi.
In ogni caso eccolo (per array di single,
nell'array Vet).
private sub QuickSortIt (byref Vet[] as single, byval l as integer, byval r
as integer)
dim i as integer, j as integer
dim x as single
dim tempswap as single
dim stacklen as integer
dim stackl[1 to 50] as integer
dim stackr[1 to 50] as integer
stacklen=1
stackl[stacklen]=l
stackr[stacklen]=r
do
    l=stackl[stacklen]
    r=stackr[stacklen]
    stacklen=stacklen-1
    i=l
    j=r
    x=Vet[(l+r)\2]
    do
        do while x>Vet[i]
            i=i+1
        loop
        do while Vet[j]>x
            j=j-1
        loop
        if i<=j then
            if Vet[i]<>Vet[j] then
                tempswap=Vet[i]
                Vet[i]=Vet[j]
                Vet[j]=tempswap
            end if
            i=i+1
            j=j-1
        end if
    loop until i>j
    if l<j then
        stacklen=stacklen+1
        stackl[stacklen]=l
        stackr[stacklen]=j
    end if
    if i<r then
        stacklen=stacklen+1
        stackl[stacklen]=i
        stackr[stacklen]=r
    end if
loop until stacklen=0
end sub
L'ho tradotta al volo dal Pascal, quindi puo' darsi
che abbia fatto qualche errore di sintassi (in particolare
la divisione che c'e' e' quella intera).
Non so quanto sia efficiente tuttavia. In particolare gli
indici di Stackl e stackr devono essere parametrizzati
in base al numero di elementi di Vet, anche se 50 ti
permette di gestire, se non sbaglio, fino alla 2^50
elementi...credo che bastino :-))
CiaO!
Andrea De Togni

di elementi e non ho mai avuto problemi.
[SNIP]
Grazie anche a te, lo aggiungo al "pacco" che mi ha mandato Jimi.
Come dicevo, il numero e la grandezza degli elementi non mi creano problemi
(mediamente dovrei essere sulla trentina di valori), il problema sono invece le
migliaia di chiamate che devo fare alla routine...sto gia' facendo delle prove
con gli altri algoritmi e, per ora, quello piu' soddisfacente e' ShellSort.


 elementi...credo che bastino :-))
Visto che mi pare di aver capito che qualcuno ne fa collezione ecco la mia
traduzione PASCAL/VB4 della "Versione non ricorsiva di Quicksort". Il
parametro v_PArray e' un eventuale vettore che torna le posizioni ordinate
di v_Array, utile quando non si vuole alterare quest'ultimo. Mi sembra anche
particolarmente efficiente. Tutte le considerazioni in proposito sono
espresse brillantemente nel testo citato.
' Niklaus Wirth
' _Algoritmi + Strutture Dati = Programmi_
' Tecniche Nuove, Milano 1987.
'   2 ORDINAMENTI
'   2.2 Ordinamento di array
'   2.2.6 Ordinamento per partizione
'
Private Sub Quicksort( _
  ByRef v_Array As Variant _
, Optional ByRef v_PArray As Variant _
)
Const PLEFT   As Integer = 0
Const PRIGHT  As Integer = 1
Dim i_C       As Integer
Dim i_N       As Integer
Dim i_Stack() As Integer
Dim i_Left    As Integer
Dim i_Right   As Integer
Dim i         As Integer
Dim j         As Integer
Dim v         As Variant
Dim v_Temp    As Variant
Dim b         As Boolean
  Let b = IsMissing(v_PArray)
  Let i_C = 1
  Let i_N = ((UBound(v_Array) - LBound(v_Array)) \ 6) + 1
  If i_N > i_C Then
    ReDim i_Stack(PLEFT To PRIGHT, i_C To i_N)
  Else
    ReDim i_Stack(PLEFT To PRIGHT, i_C To i_C)
  End If
  Let i_Stack(PLEFT, i_C) = LBound(v_Array)
  Let i_Stack(PRIGHT, i_C) = UBound(v_Array)
  Do
    Let i_Left = i_Stack(PLEFT, i_C)
    Let i_Right = i_Stack(PRIGHT, i_C)
    Let i_C = i_C - 1
    Do
      Let i = i_Left
      Let j = i_Right
      If b Then
        Let v = v_Array((i_Left + i_Right) \ 2)
      Else
        Let v = v_Array(v_PArray((i_Left + i_Right) \ 2))
      End If
      Do
        If b Then
          Do While v_Array(i) < v
            Let i = i + 1
          Loop
        Else
          Do While v_Array(v_PArray(i)) < v
            Let i = i + 1
          Loop
        End If
        If b Then
          Do While v < v_Array(j)
            Let j = j - 1
          Loop
        Else
          Do While v < v_Array(v_PArray(j))
            Let j = j - 1
          Loop
        End If
        If i <= j Then
          GoSub Swap_QuickSort
          Let i = i + 1
          Let j = j - 1
        End If
      Loop Until i > j
      If (j - i_Left) < (i_Right - i) Then
        If i < i_Right Then
          Let i_C = i_C + 1 'GoSub CAdd1_QuickSort
          Let i_Stack(PLEFT, i_C) = i
          Let i_Stack(PRIGHT, i_C) = i_Right
        End If
        Let i_Right = j
      Else
        If (i_Left < j) Then
          Let i_C = i_C + 1 'GoSub CAdd1_QuickSort
          Let i_Stack(PLEFT, i_C) = i_Left
          Let i_Stack(PRIGHT, i_C) = j
        End If
        Let i_Left = i
      End If
    Loop Until i_Left >= i_Right
  Loop Until i_C = 0
Exit_QuickSort:
  Exit Sub
CAdd1_QuickSort:
  Let i_C = i_C + 1
  If i_C > UBound(i_Stack, 2) Then
    ReDim Preserve i_Stack( _
        LBound(i_Stack, 1) To UBound(i_Stack, 1) _
      , LBound(i_Stack, 2) To i_C)
  End If
  Return
Swap_QuickSort:
  If b = True Then
    Let v_Temp = v_Array(i)
    Let v_Array(i) = v_Array(j)
    Let v_Array(j) = v_Temp
  Else
    Let v_Temp = v_PArray(i)
    Let v_PArray(i) = v_PArray(j)
    Let v_PArray(j) = v_Temp
  End If
  Return
End Sub
--
Ciao.
Maurizio