Algoritmi - Altro nuovo algoritmo di ordinamento

Forum - Algoritmi - Altro nuovo algoritmo di ordinamento

tuttodiMC (Normal User)
Expert

Messaggi: 327
Iscritto: 29/10/2012

Postato alle 15:29
Mercoledì, 13/11/2013

Salve a tutti ho pensato di crearmi un algoritmo di ordinamento che ho chiamato Higher Sort. Premetto che è uscito dalla mia testa e se quindi lo trovate scritto da qualche altra parte sappiate che non l'ho copiato.
Ho però un problema con questo. Intanto ecco il codice c#:

Codice sorgente - presumibilmente C++

public static int[] HigherSort(ref int[] matrice)
        {
            int[] m = matrice;
            int ordinati = 1;
            while (ordinati <= m.Length - 1)
            {
                int max = 0, maxPos = 0;
                for (int i = 0; i < m.Length - ordinati; i++)
                {
                    if (m[i] > max)
                    {
                        maxPos = i;
                        max = m[i];
                    }
                }
                int tmp = m[m.Length - ordinati];
                m[m.Length - ordinati++] = m[maxPos];
                m[maxPos] = tmp;
                for (int i = 0; i < m.Length - 1; i++)
                {
                    if (m[i] > m[i + 1])
                    {
                        tmp = m[i];
                        m[i] = m[i + 1];
                        m[i + 1] = tmp;
                    }
                }
            }
            return m;
        }

Come si può notare è una variante del Bubble Sort, ma lo è perché se non ci fosse l'ultimo ciclo for, una coppia dell' array sarebbe disordinata. Io voglio rimuovere questo ostacolo, ma non ho intenzione di diffondere questo algoritmo. Data la seguente matrice: { 23, 53, 1, 7, 32, 96, 0, 2, 4, 6, 3 };
il risultato senza il ciclo for è:
0
1
2
4
3
6
7
23
32
53
96
mentre con l'ultimo ciclo il 4 ed il 3 sono invertiti e quindi si trovano nelle giuste posizioni. Come mai? Da dove può derivare il problema?

HeDo (Founder Member)
Guru^2

Messaggi: 2765
Iscritto: 21/09/2007

Postato alle 10:33
Giovedì, 14/11/2013

asd, riuscire a fare una variante più lenta del bubble sort ce ne vuole di impegno

tuttodiMC (Normal User)
Expert

Messaggi: 327
Iscritto: 29/10/2012

Postato alle 14:26
Giovedì, 14/11/2013

Magari se avessi letto che voglio rimuovere proprio questo, non avresti sprecato un post per dirmi cio che gia sapevo

pierotofy (Admin)
Guru^2

Messaggi: 6230
Iscritto: 04/12/2003

Postato alle 22:49
Giovedì, 14/11/2013

Probabilmente i limiti dettati dalla variabile ordinati saranno sbagliati. Il metodo migliore per capire dove hai sbagliato e' di usare un debugger e seguire passo per passo l'esecuzione della funzione.

Occhio che questa funzione (senza il bubble sort) non funzionera' con numeri negativi...

{ 23, -53, 1, 7, 32, -96, 0, 2, -4, 6, 3 }

Il mio blog: https://piero.dev

tuttodiMC (Normal User)
Expert

Messaggi: 327
Iscritto: 29/10/2012

Postato alle 11:25
Venerdì, 15/11/2013

Ho risolto. Il problema era stupido: nel ciclo for il contatore non deve essere minore ma deve essere minore o uguale a m.Length - ordinati.
Adesso verificherò se funge con i numeri negativi e al limite faro un riadattamento.

EDIT: verificato l'algoritmo. Funziona anche con numeri negativi. 8-)

Ultima modifica effettuata da tuttodiMC il 15/11/2013 alle 11:40

nessuno (Normal User)
Guru^2

Messaggi: 6402
Iscritto: 03/01/2010

Postato alle 14:56
Sabato, 16/11/2013

Ma non sarai veramente convinto di avere "inventato" qualcosa? Spero veramente che non sia cosi' ...

Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
---
Il grande studioso italiano Bruno de Finetti ( uno dei padri fondatori del moderno Calcolo delle probabilità ) chiamava il gioco del Lotto Tassa sulla stupidità.

tuttodiMC (Normal User)
Expert

Messaggi: 327
Iscritto: 29/10/2012

Postato alle 18:30
Sabato, 16/11/2013

si lo so è identico al naive sort

pierotofy (Admin)
Guru^2

Messaggi: 6230
Iscritto: 04/12/2003

Postato alle 23:54
Sabato, 16/11/2013

Il mio blog: https://piero.dev