Qual è il modo più elegante di ordinare le bolle in C#?

Question

Può essere pulito?

using System; 
class AscendingBubbleSort 
{  
    public static void Main() 
    { 
     int i = 0,j = 0,t = 0; 
     int []c=new int[20]; 
     for(i=0;i<20;i++) 
     { 
      Console.WriteLine("Enter Value p[{0}]:", i); 
      c[i]=int.Parse(Console.ReadLine()); 
     } 
     // Sorting: Bubble Sort 
     for(i=0;i<20;i++) 
     { 
      for(j=i+1;j<20;j++) 
      { 
       if(c[i]>c[j]) 
       { 
        Console.WriteLine("c[{0}]={1}, c[{2}]={3}", i, c[i], j, c[j]); 
        t=c[i]; 
        c[i]=c[j]; 
        c[j]=t; 
       } 
      } 
     } 
     Console.WriteLine("bubble sorted array:"); 
     // sorted array output 
     for(i=0;i<20;i++) 
     { 
      Console.WriteLine ("c[{0}]={1}", i, c[i]); 
     } 
    } 
} 

Answer 1

Quello che hai incollato non c'è un bubble sort. È una specie di "forza bruta" ma non è un tipo di bolla. Ecco un esempio di un generico bubble sort. Utilizza un comparatore arbitrario, ma consente di ometterlo, nel qual caso viene utilizzato il confronto predefinito per il tipo pertinente. Analizzerà qualsiasi implementazione (non di sola lettura) di IList<T>, che include gli array. Leggi il link qui sopra (su Wikipedia) per avere un'idea più chiara del funzionamento di bubble sort. Nota come su ogni ciclo passiamo dall'inizio alla fine, ma confrontiamo solo ogni oggetto con il suo vicino. È ancora un algoritmo di ordinamento O (n), ma in molti casi sarà più veloce della versione che hai fornito.

public void BubbleSort<T>(IList<T> list) 
{ 
    BubbleSort<T>(list, Comparer<T>.Default); 
} 

public void BubbleSort<T>(IList<T> list, IComparer<T> comparer) 
{ 
    bool stillGoing = true; 
    while (stillGoing) 
    { 
     stillGoing = false; 
     for (int i = 0; i < list.Count-1; i++) 
     { 
      T x = list[i]; 
      T y = list[i + 1]; 
      if (comparer.Compare(x, y) > 0) 
      { 
       list[i] = y; 
       list[i + 1] = x; 
       stillGoing = true; 
      } 
     } 
    } 
} 

Answer 2

Personalmente preferisco questo:

string foo [] = new string[] {"abc", "def", "aaa", "feaf", "afea" }; 
Array.Sort(foo); 

Ma questo è solo me. L'ordinamento è un problema risolto, perché reinventare la ruota?

Answer 3

Penso che il tuo algoritmo in ok, ma vorrei mettere la funzionalità di ordinamento in una classe e un metodo separati.

Answer 4

Il modo più elegante per ordinare in C# è

Array.Sort(object[]) 

che funzionerà ovunque tranne che in problemi a casa, dove l'insegnante ti ha chiesto di attuare il non-elegante algoritmo bubble sort. ;-)

Answer 5

• avrei usato uno scambio methed per scambiare i due elementi di matrice. (dettagli su come scrivere il metodo di swap lasciato come compito a casa!)

• Si dovrebbe pensare al caso in cui le voci sono già in ordine

• si dovrebbe leggere su Insertion sort per più marchi :-)

• Piuttosto che la lettura dei dati di test da tastiera, vedere se si può imparare a utilizzare NUnit

Answer 6

La maggior parte delle persone non sarebbe preoccuparsi di fare una bolla sorta elegante. In genere, però, trovo che facendo questo:

for (int i = 0; i < items.Length; i++) { 
    Item item = items[i]; 
    // do something with item 
} 

è sia più elegante e più gestibile di fare questo:

Item item; 
int i; 
for (i = 0; i < items.Length; i++) { 
    item = items[i]; 
    // do something with item 
} 

In altre parole, dichiarare le variabili all'interno del più piccolo applicabile scope. Altrimenti potresti trovarti a fare qualcosa con i o item in qualche altro punto del codice e quindi utilizzarli di nuovo dove non dovresti essere.

Answer 7

Nel complesso, non c'è niente di sbagliato nell'implementazione del bubble sort.Se fossi facendo una revisione del codice vero e proprio, mi piacerebbe fare le seguenti modifiche:

Scegliere i nomi delle variabili più descrittivi

Perché è la matrice appena chiamato c?

Minimizzare portata variabile

tutte le variabili sono dichiarate nella parte superiore della funzione. A meno che questo non sia un requisito per i compiti a casa o uno standard di codifica, è più idiomatico dichiarare le variabili "vicine" al luogo in cui vengono utilizzate, preferibilmente in modo da avere il più piccolo raggio di azione possibile.

Quindi, eliminare la prima riga che legge int i = 0,j = 0,t = 0;. Dichiarare ciclo contatori in linea:

for(int i = 0; i < 20; i++) 

E dichiarare la variabile temporanea in zone dove l'usato:

   Console.WriteLine("c[{0}]={1}, c[{2}]={3}", i, c[i], j, c[j]); 
       int t=c[i]; 
       c[i]=c[j]; 
       c[j]=t; 

Eliminare limiti di matrice hard-coded.

questo:

for(i=0;i<20;i++) 

Diventa questo:

for(i = 0; i < c.Length; i++) 

Answer 8

Credo che ci sia un miglioramento della answer proposto da Jon Skeet. Dopo ogni ciclo, il numero di iterazioni dovrebbe escludere l'ultimo elemento elaborato nella precedente iterazione. Quindi, ecco il codice:

public void BubbleSortImproved<T>(IList<T> list) 
{ 
    BubbleSortImproved<T>(list, Comparer<T>.Default); 
} 

public void BubbleSortImproved<T>(IList<T> list, IComparer<T> comparer) 
{ 
    bool stillGoing = true; 
    int k = 0; 
    while (stillGoing) 
    { 
     stillGoing = false; 
     //reduce the iterations number after each loop 
     for (int i = 0; i < list.Count - 1 - k; i++) 
     { 
      T x = list[i]; 
      T y = list[i + 1]; 
      if (comparer.Compare(x, y) > 0) 
      { 
       list[i] = y; 
       list[i + 1] = x; 
       stillGoing = true; 
      } 
     } 
     k++; 
    } 
} 

Answer 9

int[] array = {4,5,7,1,8};   

int n1, n2; 
bool stillgoing = true; 

while (stillgoing) 
{ 
    stillgoing = false; 
    for (int i = 0; i < (array.Length-1); i++) 
    {     
     if (array[i] > array[i + 1]) 
     { 
      n1 = array[i + 1]; 
      n2 = array[i]; 

      array[i] = n1; 
      array[i + 1] = n2; 
      stillgoing = true; 
     } 
    } 
} 
for (int i = 0; i < array.Length; i++) 
{ 
    Console.WriteLine(array[i]); 
} 

Ha preso alcune idee da Jon Skeet ...

Answer 10

public int[] BubbleSortInAesc(int[] input) 
    { 
     for (int i = input.Length; i > 0; i--) 
     { 
      for (int j = 0; j < i-1; j++) 
      { 
       if (input[j] > input[j + 1]) 
       { 
        //Swap the numbers 
        input[j] = input[j + 1]+input[j]; 
        input[j + 1] = input[j] - input[j + 1]; 
        input[j] = input[j] - input[j + 1]; 
       } 
      } 
     } 
     return input; 
    }