Sortér 2 dimensionelt array

Hvordan vil du have det sorteret ?

Sortere rækker efter 1. kolonne ? Eller ?

I så fald kan man jo bare sortere manuelt.

Eksempel:

using System;

class MainClass
{
    private const int N = 10;
    private const int M = 3;
    private const int KEY = 0; // second dimenaion that we sort after 0=first column
    private static Random rng = new Random();
    private static void Init(int[,] a)
    {
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < M; j++)
            {
                a[i,j] = rng.Next(1000);
            }
        }
    }
    private static void Write(int[,] a)
    {
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < M; j++)
            {
                Console.Write(" " + a[i,j]);
            }
            Console.WriteLine();
        }
    }
    private static void Sort(int[,] a)
    {
        for(int i = 0; i < N; i++)
        {
            for(int i2 = (i + 1); i2 < N; i2++)
            {
                if(a[i,KEY] > a[i2,KEY])
                {
                    int tmp;
                    for(int j = 0; j < M; j++)
                    {
                        tmp = a[i,j];
                        a[i,j] = a[i2,j];
                        a[i2,j] = tmp;
                    }
                }
            }
        }
    }
    public static void Main(string[] args)
    {
        int[,] a = new int[N,M];
        Init(a);
        Console.WriteLine("Unsorted:");
        Write(a);
        Console.WriteLine("Sorted:");
        Sort(a);
        Write(a);
    }
}

Hvis du skal sorteres meget så skal der bruges en bedre sorterings algoritme
end den O(n^2) i den kode.

Selvføgelig.. tak!

Regner ca med at have max 100 rows * ca 1 million
Det vil side 1 million dokumanter der skal gennemlæses.. For hver dokument arbejder jeg med max et array på 100 rows.

Er det for meget, eller tror du jeg skal bruge noget a'la quicksort?

Med 1 million sorteringer af 100 element arrays, så vil quicksort ikke
være meget (om overhovedet) hurtigere end en primitiv sort.

Med 100 sorteringer af 1 million element arrays vil forskellen have
været enorm.

Eller mener du et 1 million x 100 2D array ?

Regner med ca. 1 million * 100 2d array..
Dvs. Første dokument's 100 rows sortered
Andet dokument's 100 rows sortered
osv

Det bliver da et heftigt array.

1 million x 100 x 4 byte = 400 MB !

Men jeg er stadivæk ikke helt klar over om jeg har forstået det rigtigt.

Du har et array:

[0,0] ... [0,99]
  .        .
  .        .
  .        .
[999999,0] ... [999999,99]

Vil du sortere den ene million rækker efter en af kolonnerne ?

Eller vil du sortere hver række (af 100 elementer) uafhængigt af
hinanden ?

Unskyld.. Det er mig der ikke lige foklarer det ordentligt.

Jeg har en applikation der skal åbne et dokumant af gangen.
Det dokumant indeholder et array på [100,2]
Derefter sloetter jeg alt, og åbner endnu et array osv osv.
Så mit array blir ca [100,2] per gang.

Nå.

Så tror jeg bare at du skal bruge metoden fra mit oprindelig eksempel.

ok, det vil jeg så gøre .. Jeg takker mange for hjælpen!

Nu nævnte petermjensen quick-sort, så bare lige for at få det slået fast, så er quick-sort ikke nødvendigvis specielt hurtig... Rent faktisk kører den i worst-case O(n^2) - måske ikke lige noget at råbe hurra for... worst-case er når det der skal sorteres allerede er sorteret.

Hvis man vil benytte quick-sort er det derfor vigtigt, at man benytter randomized quick-sort, som giver den ønskede sorteringstid på O(n log n).

Det er rigtigt at quicksort degenerere til O(n^2) i worst case.

Det er ikke helt rigtigt at allerede sorteret er worst case.

Det afhænger af valg af pivot element.

Hvis man vælger første eller sidste element som pivot element, så
er allerede sorteret worst case.

Hvis man f.eks. vælger midterste element som pivot element, så
er der ingen problemer med allerede sorteret.

Jeg kan ikke forestille mig at nogen seriøs quicksort bruge første
eller sidste element som pivot element - af samme årsag.

Hvis du altid benytter f.eks. midterste element kan der vel også forekomme situationer hvor den kører O(n^2) - så er worst-case dog ikke når den er sorteret. Hvis du derimod vælger et random pivot, vil du generelt få den bedste udførselstid.

Uanset hvordan du vælger pivot element er der altid det samme antal
worst case rækkefølger.

Først, sidste, midterste eller random.

Random er bare speciel ved at worst case ikke er ens fra kørsel til kørsel.

Korrekt. Men sandsynligheden for worst-case er ikke nær så stor ved et random pivot som ved et fast pivot. Rent faktisk kan det bevises, at sandsynligheden for O(n log n) ved randomized quick-sort er ret høj.

Desværre er jeg ikke specielt god til sandsynlighedsteori, så jeg kan nok ikke lige komme med den helt store afhandling her... Under alle omstændigheder kan vi nok godt blive enige om, at der findes en del naive implementationer på nettet af quick-sort, som benytter første/sidste element som pivot - og det var sådan set mest det jeg ville advare mod :-)

Nej - jeg tror faktisk at sandsyneligheden for worst case er præcis den
samme ved random pivot som ved f.eks. midterste element pivot.

Sandsyneligheden for at random data skulle nærme sig worst case er i
begge tilfælde forsvindende lille.

Midterste element pivot har den svaghed at worst case data kan konstrueres
af et program.

Men du har helt ret i at forbløffende få er opmærksomme på mekanikken
i valg af pivot.

Tja, du har nok ret - det var i hvert fald også sådan jeg umiddelbart ville mene det skulle være... Men de der sandsynlighedsteoretikere kommer til tider med nogle ret mærkelige påstande som man ikke umiddelbart lige forstår, og som man kun kan få til at passe hvis man bruger deres egne formler :-)

F.eks. kan de bevise at uheld altid kommer 2,7 (PI) efter hinanden... så det med at ét uheld sjældent kommer alene, mener de at kunne bevise er sandt - de kommer simpelthen 2,7 efter hinanden.

Desuden er det ofte sådan, at hvis de propper et tilfældigt tal ind i en algoritme kører den hurtigere (af grunde som er total ukendte for mig)...