Sitter och funderar på en ny sorteringsalgoritm, tänkte kolla om någon vet om det finns någon sådan.

Det är ju inte en helt ovanlig situation att en sekvens är sorterad inom vissa intervall, speciellt om man hämtar från databaser etc. Många algoritmer funkar ju väl vad gäller "nästan sorterade" sekvenser, men jag tänker nu på en specialare, lätt inspirerad av quicksort och mergesort.

Låt säga att vi har en sekvens:

[4,5,6,7,8,1,2,3]

Denna är ju korrekt sorterad i två intervall.

[4,5,6,7,8] och [1,2,3]

Sådana sekvenser är ju lätta att hitta, och det går på O(n) att göra det. Om sekvenser i allmänhet består av långa sådana intervall så handlar det ju bara om att merga dem. Man kör bara med samma algoritm som i mergesort. Vi allokerar en ny sekvens, fyller den med sekvenser mergade parvis, och fortsätter tills vi bara får en enda.

Om m är antalet sekvenser och n är antalet elemet får vi O(m*n). För låga m har vi ett linjärt beteende, för höga m får vi O(n*n).

Annat exempel:

[4,6,7,1,2,5,3,9] -> [4,6,7] & [1,2,5] & [3,9]
Mergar parvis i en ny sekvens, och låter sista vara orört:
[1,2,4,5,6,7,3,9] -> [1,2,4,5,6,7] & [3,9]
Igen:
[1,2,3,4,5,6,7,9]

I det här fallet O(n*3)

Jävlar. Jag tror jag hittade den, eller åtminstone en snarlik: http://en.wikipedia.org/wiki/Patience_sorting

Om man hittar en ny sorteringsalgoritm nu har man gjort ett bra jobb. Rätt många gubbar som i många år funderat på sådant.

Jo, naturligtvis, jag menar inte att jag tror att jag har kommit på en ny, unik ide. =)
Däremot så har jag, som så många andra, lärt mig ganska många sorteringsalgoritmer. Men alla är snabba i medelfallet, vilket alltid är "verkligen medelfallet". Man tar inte hänsyn till att vissa typer av fördelningar är betydligt vanligare än andra.

Tycker därför att det är lite märkligt att man aldrig hör talas om specialare som är bra på de vanligaste specialfallen. (snarare än att diskutera alla möjliga varianter på n^2-algoritmer).

Vanligtvis då man talar om sortering är det just grunden man går in på därför tas inga specialare upp. Visst kan det vara rimligt att ta upp andra än de klassiska men samtidigt brukar tiden vara en starkt begränsande faktor. Jag håller dock med dig om att det är intressant( tolkade dina inlägg så)

Jag menar inte specifikt kurser eller liknande, jag menar generellt. Jag har aldrig stött på specialiserade sorteringsrutiner annat än i olika typer av kataloger.

Vissa specialiserade är ju betydligt snabbare än generella algoritmer på det de är specialiserade för. Och såna typer av ordningar bör ju faktiskt vara vanligare än det generella fallet.

Oftast är ju tex QuickSort bra nog för det man vill göra.

men har dock använt tex Radix/Bucket sort för att sortera polygoner.
det är sjukt snabbt.

Radix sort är ju bra för information med mycket upprepningar om jag inte minns fel?

Men låt säga att vi vill sortera, säg, 100 000 poster av någon slags genererad information. Data genereras först med avseende på ett fält x och sen på ett annat fält y. (...eller läggs in på det sättet, etc.)

Så vi får långa grupper med samma värde på x, där y ökar:
x y
1 1
1 2
1 3
1 4
2 1
2 2
2 3
...

(Dock inte så reguljärt som i exemplet.) Att då använda min metod skulle i så fall ge en komplexitet på [Antalet olika värden på x] * [Antalet poster]. Har vi ett hyfsat lågt växande av x map antalet poster, så får vi nog ett betydligt bättre jobb med "min" variant än alla andra jag känner till.

Och det känns som det näst vanligaste specialfallet efter att ha många poster som är likadana.

man kan köra radix/bucket där man har en bucket per värde

tex om vi vill sortera intar mellan 0 och 999 , så kan vi i pseudo göra:

int[] sort(int[] arrToSort)
{
int maxValue = 1000;
int[] valueCounts = new int[maxValue];

//räkna förekomsten av varje värde
for (int i=0,i<arrToSort.Length;i++)
valueCounts[arrToSort[i]] ++;

int j=0;
int[] res = new int[arrToSort.Length];

//bygg resultat arrayen
for (int i=0;i<valueCounts.length;i++)
{
while(valueCounts[i] > 0)
{
res[j] = i;
j++;
valueCounts[i]--;
}
}

return res;
}

skillnaden här mot radix är att vi inte skapar en bucket för talen 0-9, utan en bucket för talen 0-999
så det behövs bara köras ett enda svep för sorteringen.

(ok koden var rakt ur huvet så jag kan ha missat någon del..


såhär funkar det iaf, tänk att vi vill sortera intar mellan 0 och 9

säg att vi har arrayen med:

7
3
2
6
9
9
8
3
3
5
6

11 st värden

då skapar vi först en valueCount arr med elementen 0-9

sedan börjar vi scanna vår array av värden:

7 , öka valuecount(7) ett steg
3 , öka för 3 ett steg
osv osv.

då får vi:

0 st 0or
0 st 1or
1 st 2a
3 st 3or
0 st 4or
1 st 5or
2 st 6or
1 st 7a
1 st 8a
2 st 9or

när vi nu vet exakt hur många av varje vi har så scannar vi vår värde count lista och outputtar varje siffra vi hittar där i:

2
3
3
3
5
6
6
7
8
9
9


klart..

så först ett svep i n steg, sedan ett svep i range+n steg. (där range är storleken på dina tal, tex 0-9)


så : n*2+range blir antalet itterationer

och har du då en extremt stor array , säg en milj tal som är mellan 0 och 999
så skulle du få
2000 999 itterationer för sorteringen... vilket är galet bra för en array med 1milj element som kan vara helt opartitionerad