+ Rispondi al messaggio
Visualizzazione dei risultati da 1 a 7 su 7

Ordinamento bubblesort più lento rispetto all'ordinamento semplice

  1. #1
    mitikuzzo98 non è in linea Novello
    Ciao a tutti sono sempre io. Apro questo thread sempre in base allo stesso programma perchè una volta che mi sembrava finito, mi rendo conto che fra i due ordinamenti (bubblesort e semplice) il primo è piu lento rispetto al secondo e dovrebbe essere al contrario, qualcuno sa dirmi come mai?

    namespace WindowsFormsApplication1
    {
        public partial class Form1 : Form
        {
            public Form1()
            {
                InitializeComponent();
                preparelistViewAst();
            }
    
     private void swap (ListViewItem item1, ListViewItem item2)
            {
                string dep = item1.Text; // valore di i va nel deposito
                item1.Text = item2.Text; // i prende il valore di l/i +1
                item2.Text = dep;        // i/ i+1 prende il valore del deposito
            }
    
            private void ordinaBubbleSort()
            {
                int nswap = 0;
                int n;
                n = 1;
    
                while (n != 0)
                {               
                    n = 0;
                    for (int i = 0; i < (listView1.Items.Count-1); i++)
                    {
                        lblArrow1.Top = i * 21 + 12;
                        lblArrow2.Top = (i + 1) * 21 + 12;
                        registra(listView1.Items[i], listView1.Items[i + 1]);
                        System.Threading.Thread.Sleep(100);
    
                        if (int.Parse(listView1.Items[i].Text) > int.Parse(listView1.Items[i + 1].Text))
                        {
    
                            swap(listView1.Items[i], listView1.Items[i+1]);                                                
                            listView1.Refresh();
    
                            swap(listViewAst.Items[i], listViewAst.Items[i + 1]);
                            listViewAst.Refresh();                        
                            n++;
                            nswap++;
                            
                        }
                        lbl2.Text = nswap.ToString();
    
                    }
                }
            }
    
            private string getStringOfChar(int n, string s)
            {
                string str = "";
                for (int i = 1; i <= n; i++)
                {
                    str = str + s;
                }
                return str;
    
            }
    
            private void preparelistViewAst()
            {
                int n;
    
                for (int i = 0; i <= (listView1.Items.Count - 1); i++) 
                {
                    n = int.Parse(listView1.Items[i].Text);
                    listViewAst.Items.Add(getStringOfChar(n,"*"));
                }
            }
    
                private void ordinaSemplice()
                {
                    int nswap = 0;
                    for (int i = 0; i < (listView1.Items.Count -1 ); i++)
                    {   
                        for (int l = i + 1; l < (listView1.Items.Count); l++)
                        {
                            System.Threading.Thread.Sleep(100);
                            lblArrow1.Top = i * 21 + 12;
                            lblArrow2.Top = l * 21 + 12;
                            registra(listView1.Items[i], listView1.Items[l]);
    
                        if (int.Parse(listView1.Items[i].Text) > int.Parse(listView1.Items[l].Text))
                            {
                                
                                swap(listView1.Items[i], listView1.Items[l]);                                                                                                           
                                listView1.Refresh();
    
                                swap(listViewAst.Items[i], listViewAst.Items[l]);
                                listViewAst.Refresh();                            
                                nswap++;
    
                            }
                            lbl2.Text = nswap.ToString();
                                                  
                                
                        }
                    }
                 }
    
            private void btn1_Click(object sender, EventArgs e)
            {
                if (radioBtnS.Checked == true)
                {
                    radioBtnB.Checked = false;                
                    ordinaSemplice();             
                }
    
                if (radioBtnB.Checked == true)
                {
                    radioBtnS.Checked = false;
                    ordinaBubbleSort();
                }
    
            }        
    
           private void registra (ListViewItem regi1, ListViewItem regi2)
            {                       
                txtBox1.AppendText("confronto " + regi1.Text + " con " + regi2.Text + Environment.NewLine);                       
                            
            }
        }
        }
    

  2. #2
    L'avatar di bumm
    bumm non è in linea Topo di biblioteca Ultimo blog: [VB2010] ComboBox ed Enumeratori
    magari per via di :

    System.Threading.Thread.Sleep(100);


    oltre alla discutibile implementazione... Come fai le misurazioni? Visto che coinvolgi gli elementi della UI il risultato potrebbe essere non attendibile.
    ℹ️ Leggi di più su bumm ...

  3. #3
    mitikuzzo98 non è in linea Novello
    Quote Originariamente inviato da bumm Visualizza il messaggio
    magari per via di :

    System.Threading.Thread.Sleep(100);


    oltre alla discutibile implementazione... Come fai le misurazioni? Visto che coinvolgi gli elementi della UI il risultato potrebbe essere non attendibile.
    Il system.threading.sleep(100) è stato messo per una questione estetica per mostrare all'utente i cambi mentre il programma è in esecuzione. Se lo togliessi dovrei toglierlo anche sull'ordinamento semplice e quindi dopo la cosa non cambia, oltre al fatto che sarebbe veloce il cambio e non è quello che mi aspetto...

    Comunque cosa intendi per come fai le misurazioni?
    Cosa c'è di male nelle implementazioni?

  4. #4
    L'avatar di bumm
    bumm non è in linea Topo di biblioteca Ultimo blog: [VB2010] ComboBox ed Enumeratori
    Quote Originariamente inviato da mitikuzzo98 Visualizza il messaggio
    Comunque cosa intendi per come fai le misurazioni?

    hai parlatodi velocità. hai affermato che un algoritmo è più veloce dell'altro. ti chiedo come hai controllato la velocità?

    Quote Originariamente inviato da mitikuzzo98 Visualizza il messaggio
    Cosa c'è di male nelle implementazioni?
    non puoi confrontare le velocità di una ferrari e una "panda" mettemdoli insieme su una strada con traffico murato.

    per fare confronto dovresri usare solo le variabili, collezioni e cicli( no elementi della UI, sleep e altro) per misurare la velocità bisogna prendere il tempo prima di fare sort e dopo. poi bisogna confrontare i timespan ricevuti.
    ma nel tuo caso che tempo misureresti? sai quanto tempo serve per fare refresh di una listview? e una componente UI, che contiene i tuoi dati e va redisegnato completamente(pixel per pixel) durante il refresh, quindi dovrebbe essere misurata per sapere la velocità dell'algoritmo?
    ℹ️ Leggi di più su bumm ...

  5. #5
    mitikuzzo98 non è in linea Novello
    Quote Originariamente inviato da bumm Visualizza il messaggio
    hai parlatodi velocità. hai affermato che un algoritmo è più veloce dell'altro. ti chiedo come hai controllato la velocità?



    non puoi confrontare le velocità di una ferrari e una "panda" mettemdoli insieme su una strada con traffico murato.

    per fare confronto dovresri usare solo le variabili, collezioni e cicli( no elementi della UI, sleep e altro) per misurare la velocità bisogna prendere il tempo prima di fare sort e dopo. poi bisogna confrontare i timespan ricevuti.
    ma nel tuo caso che tempo misureresti? sai quanto tempo serve per fare refresh di una listview? e una componente UI, che contiene i tuoi dati e va redisegnato completamente(pixel per pixel) durante il refresh, quindi dovrebbe essere misurata per sapere la velocità dell'algoritmo?
    La velocità la misuro approssimativamente con il cronometro del telefono. Avendo il thread.sleep, attivo il timer contemporaneamente al click del bottone che aziona il programma e lo interrompo quando i numeri sono ordinati e i tempi sono: circa 16 secondi per il bubblesort e 12 per l'ordinamento semplice (e trattandosi di 4 secondi e essendo pochi ho iniziato ad indagare).. Ho provato anche prima di aprire il thread ad avviarlo senza il thread.sleep e ci sono 7 secondi per il bubble e 4 per il semplice.. Io adesso ammetto la mia ignoranza.. Io sono ancora uno studente e quando il mio professore ci ha fatto inserire lo sleep ci ha fatto inserire anche il refresh altrimenti si buggava il programma dato che i valori o scomparivano e ricomparivano ordinati oppure non si muovevano fino a che non si fosse completato l'ordinamento. Sono consapevole comunque che le implementazioni aggiunte rallentino l'algoritmo ma comunque sono inserite in entrambi gli ordinamenti.. Quindi come viene rallentato uno allo stesso modo è rallentato anche l'altro... Aggiungo una mia osservazione: ovvero che se lo sleep lo metto fuori l'if come nel codice riportato ci mette di più che se lo metto all'interno dell'if (prima di "n++"). Chiedo scusa per l'ignoranza in anticipo

  6. #6
    L'avatar di bumm
    bumm non è in linea Topo di biblioteca Ultimo blog: [VB2010] ComboBox ed Enumeratori
    Ecco un esempio di come io misurerei due tipi di sort:


    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace ConsoleApplication1
    {
    class Program
    {
    const int ARRAY_LEN = 20000;
    static void Main(string[] args)
    {
    int[] arrayToSort = generateNewArray();
    int[] arrayToSort2 = new int[ARRAY_LEN];
    arrayToSort.CopyTo(arrayToSort2,0);

    DateTime start = DateTime.Now;
    BubbleSort(arrayToSort);
    Console.WriteLine("BubbleSorted in {0}", DateTime.Now.Subtract(start));

    start = DateTime.Now;
    QuickSort(arrayToSort2, 0, ARRAY_LEN);
    Console.WriteLine("QuickSorted in {0}", DateTime.Now.Subtract(start));

    Console.Read();
    }



    public static void BubbleSort(int[] arr)
    {
    int i;
    int j;
    int temp;

    for (i = (arr.Length - 1); i >= 0; i--)
    {
    for (j = 1; j <= i; j++)
    {
    if (arr[j - 1] > arr[j])
    {
    temp = arr[j - 1];
    arr[j - 1] = arr[j];
    arr[j] = temp;
    }
    }
    }
    }

    static int Partition(int[] list, int left, int right)
    {
    int start = left;
    int pivot = list[start];
    left++;
    right--;

    while (true)
    {
    while (left <= right && list[left] <= pivot)
    left++;

    while (left <= right && list[right] > pivot)
    right--;

    if (left > right)
    {
    list[start] = list[left - 1];
    list[left - 1] = pivot;

    return left;
    }


    int temp = list[left];
    list[left] = list[right];
    list[right] = temp;

    }
    }

    static void QuickSort(int[] list, int left, int right)
    {
    if (list == null || list.Count() <= 1)
    return;

    if (left < right)
    {
    int pivotIdx = Partition(list, left, right);
    QuickSort(list, left, pivotIdx - 1);
    QuickSort(list, pivotIdx, right);
    }
    }
    public static int[] generateNewArray()
    {

    Random randNum = new Random();
    int[] arr = Enumerable
    .Repeat(0, ARRAY_LEN)
    .Select(i => randNum.Next(0, ARRAY_LEN))
    .ToArray();
    return arr;
    }
    }
    }

    ℹ️ Leggi di più su bumm ...

  7. #7
    mitikuzzo98 non è in linea Novello
    Quote Originariamente inviato da bumm Visualizza il messaggio
    Ecco un esempio di come io misurerei due tipi di sort:


    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace ConsoleApplication1
    {
    class Program
    {
    const int ARRAY_LEN = 20000;
    static void Main(string[] args)
    {
    int[] arrayToSort = generateNewArray();
    int[] arrayToSort2 = new int[ARRAY_LEN];
    arrayToSort.CopyTo(arrayToSort2,0);

    DateTime start = DateTime.Now;
    BubbleSort(arrayToSort);
    Console.WriteLine("BubbleSorted in {0}", DateTime.Now.Subtract(start));

    start = DateTime.Now;
    QuickSort(arrayToSort2, 0, ARRAY_LEN);
    Console.WriteLine("QuickSorted in {0}", DateTime.Now.Subtract(start));

    Console.Read();
    }



    public static void BubbleSort(int[] arr)
    {
    int i;
    int j;
    int temp;

    for (i = (arr.Length - 1); i >= 0; i--)
    {
    for (j = 1; j <= i; j++)
    {
    if (arr[j - 1] > arr[j])
    {
    temp = arr[j - 1];
    arr[j - 1] = arr[j];
    arr[j] = temp;
    }
    }
    }
    }

    static int Partition(int[] list, int left, int right)
    {
    int start = left;
    int pivot = list[start];
    left++;
    right--;

    while (true)
    {
    while (left <= right && list[left] <= pivot)
    left++;

    while (left <= right && list[right] > pivot)
    right--;

    if (left > right)
    {
    list[start] = list[left - 1];
    list[left - 1] = pivot;

    return left;
    }


    int temp = list[left];
    list[left] = list[right];
    list[right] = temp;

    }
    }

    static void QuickSort(int[] list, int left, int right)
    {
    if (list == null || list.Count() <= 1)
    return;

    if (left < right)
    {
    int pivotIdx = Partition(list, left, right);
    QuickSort(list, left, pivotIdx - 1);
    QuickSort(list, pivotIdx, right);
    }
    }
    public static int[] generateNewArray()
    {

    Random randNum = new Random();
    int[] arr = Enumerable
    .Repeat(0, ARRAY_LEN)
    .Select(i => randNum.Next(0, ARRAY_LEN))
    .ToArray();
    return arr;
    }
    }
    }

    Ti ringrazio per la disponiblità, solo ora ho potuto leggere la risposta. Comunque premetto che la mia è un applicazione windows form non console.. Così andrei solo in confusione essendo principiante e comunque rivedendo il progetto e rileggendo il thread ho capito di essermi espresso male. Il problema che rallenta il bubblesort non è per lo sleep o refresh ma bensì perchè l'algoritmo controlla numeri che palesemente sono già controllati dato che ogni ciclo posiziona il numero più grande in fondo, il mio codice li controlla ugualmente al ciclo dopo.. Arrivati a questo punto il mio problema ufficiale è: come posso ottimizzare il mio bubblesort indicando che ogni ciclo deve ridurre di uno la casella da controllare?

+ Rispondi al messaggio

Potrebbero interessarti anche ...

  1. Ordinamento crescente Order by e ordinamento numero Max.
    Da raamino73 nel forum Microsoft SQL Server
    Risposte: 3
    Ultimo Post: 19-04-2013, 17:12
  2. Ordinamento ListBox
    Da Marina nel forum Visual Basic .Net
    Risposte: 9
    Ultimo Post: 18-05-2008, 10:54
  3. Ordinamento Datagrid
    Da Marina nel forum Visual Basic .Net
    Risposte: 9
    Ultimo Post: 19-04-2008, 08:37
  4. [MySQL]Ordinamento
    Da net-addiction nel forum MySQL
    Risposte: 4
    Ultimo Post: 12-06-2006, 10:01
  5. [C/C++] Ordinamento di una tabella
    Da pc82 nel forum C/C++
    Risposte: 4
    Ultimo Post: 13-04-2005, 11:16