Søg
Avatar billede -mundi- Nybegynder
12. november 2004 - 08:38 Der er 17 kommentarer og
1 løsning

Hvilken sorterings algoritme bruger Array.sort ?

Når man kalder et arrays sort metode, hvilken sorteringsmetode bruges så ?

Jeg har et array med 160 elementer, hvis jeg kalder sort(myrowcompare) laver den ca 1660 sammenligninger hvilket jeg synes er lige i overkanten,.
Avatar billede -mundi- Nybegynder
12. november 2004 - 08:46 #1
Hov glemte det vigtigste :-)
http://www.4guysfromrolla.com/webtech/012799-1.shtml
Hvordan hulen får jeg quicksort til at fungere på et array hvor jeg kan bruge min egen rowcompare ? Dog kun hvis array ikke bruger quicksort allerede
Avatar billede olebole Juniormester
12. november 2004 - 09:20 #2
<ole>

1660 lyder ikke usandsynligt. Du kan altid skrive en funktion mySort(a, b) og referere til den i JS' sort-metode a.sort(mySort)
Hvis vi gør det samme som sort() pr. default gør, vil det se sådan ud:

function mySort(a, b) {
    if (a < b) return -1;
    if (a > b) return 1;
    return 0;
}

var a = ["Et", "To", "Tre", "Fire", "Fem", "Seks", "Syv", "Otte", "Ni", "Ti"];
a.sort(mySort);
alert( a.join(" :: ") );

Vil du sortere flerdimensionale arrays, kan du se princippet i disse to eksempler:

<script type="text/JavaScript">
var aMatrix = [];
aMatrix[0] = ["brun", "789"];
aMatrix[1] = ["sort", "234"];
aMatrix[2] = ["orange", "512"];
aMatrix[3] = ["gul", "734"];

function mySort2(a, b) {
    if (a[0] < b[0]) return -1;
    if (a[0] > b[0]) return 1;
    return 0;
}
function mySort3(a, b) {
    if (a[1] < b[1]) return -1;
    if (a[1] > b[1]) return 1;
    return 0;
}

aMatrix.sort(mySort2);
var s = "";
for (x in aMatrix) {
    s += x + " => " + aMatrix[x] + "\n";
}
alert(s);

aMatrix.sort(mySort3);
var s = "";
for (x in aMatrix) {
    s += x + " => " + aMatrix[x] + "\n";
}
alert(s);
</script>

/mvh
</bole>
Avatar billede olebole Juniormester
12. november 2004 - 09:24 #3
OBS: Vær opmærksom på, at der er problemer med tegn som æ, ø og å. JS baserer sammenligningen på tegnenes keyCode - og der kommer disse tre tegn ikke i samme rækkefølge, som vi bruger i det danske alfabet
Avatar billede -mundi- Nybegynder
12. november 2004 - 09:31 #4
Med mindre der er et eller andet jeg har misforstået , så synes jeg den kalder mySort3 omkring 1800 gange i nedenstående eksempel ?

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">

<html>
<head>
    <title>Untitled</title>
</head>

<body>
<script type="text/JavaScript">
var aMatrix = [];
var counter =0;

aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);
aMatrix.push(["gul", "734"]);
aMatrix.push(["brun", "789"]);
aMatrix.push(["sort", "234"]);
aMatrix.push(["orange", "512"]);

function mySort2(a, b) {
    if (a[0] < b[0]) return -1;
    if (a[0] > b[0]) return 1;
    return 0;
}
function mySort3(a, b) {
    counter++;
    if (a[1] < b[1]) return -1;
    if (a[1] > b[1]) return 1;
    return 0;
}

aMatrix.sort(mySort3);
alert(counter);
</script>


</body>
</html>
Avatar billede olebole Juniormester
12. november 2004 - 09:41 #5
... og ...?
Avatar billede -mundi- Nybegynder
12. november 2004 - 09:42 #6
Det må da kunne gøres bedre ? :-)
Avatar billede olebole Juniormester
12. november 2004 - 09:49 #7
Tja, JavaScript er jo netop berømt for sin umådeligt effektive array-håndtering - men hvis du mener, du kan gøre det bedre, så skal du da gøre det  :)
Avatar billede -mundi- Nybegynder
12. november 2004 - 09:50 #8
jamen det er jo derfor jeg spørger kloge hoveder som dig om hvordan man gør :-) Ud med sproget
Avatar billede olebole Juniormester
12. november 2004 - 10:08 #9
Jeg har brugt sort til at sortere forskellige tabel baserede grid-interfaces og fil-træer - fra ganske simple til yderst komplekse - og jeg har altid været ganske fornøjet med effektiviteten.
Først oppe i flere tusinde rækker begynder det at knibe og da er det ikke datasorteringen, men DOM-flytningerne, m.m, der trækker tænder ud.

Uden at skulle kaste mig ud i mine støvede minder om kombinatorik, vil jeg da ikke mene, 1800 sammenligninger lyder spor urealistisk, som værende noget af det bedste, der kan gøres.
Avatar billede -mundi- Nybegynder
12. november 2004 - 10:18 #10
Det er tilgangen til DOM elementerne der tager tid, så jeg tænkte at man kunne reducere antallet af sammenligninger for at få en bedre performance. Det kunne være jeg skulle kigge på at cache værdierne i DOM elementerne istedet for at hive dem ud ved hver sammenligning. Med andre ord, optimere mine rowcomparefunktioner
Avatar billede -mundi- Nybegynder
12. november 2004 - 10:40 #11
Smider du et svar ? Jeg har nogen point jeg skal af med :-)
Avatar billede olebole Juniormester
12. november 2004 - 10:43 #12
Jamen, det er helt elementært. Når man laver den slags interfaces, opbygger man et JS-objekt med alle data og manipulerer på det og derefter opbygger en visuel repræsentation i HTML.
Alle forespørgsler på data skal naturligvis også foregå ned i JS-objektet og ikke ved at rode rundt i DOM'en på HTML-elementerne. Det eneste, der bruges af HTML'en, er elementernes events og id'er.
HTML'en bør kun være en grænseflade mellem brugeren og applikationen med de data, der skal behandles. Det fremmer muligheden for at opbygge en robust JS-applikation væsentligt.
Bruger man HTML'en til at opbevare data og som en væsentlig del af 'maskinen', er der sat vand over til en ustabil applikation  :)

Jeg har i øvrigt lige checket et array med præcis samme indhold i PHP og sorteret med PHP's usort() og en direkte oversat mySort-funktion.
Jeg må med store øjne erkende, at PHP kun bruger 926 kald til mySort().

Jeg er hermed en tophue fattigere - og en ulden smag i munden rigere  :o|

Jeg er dog ikke sikker på, jeg selv orker at rode med en ny algoritme  :)
Avatar billede -mundi- Nybegynder
12. november 2004 - 10:50 #13
Njaaa , det må blive en dag med meget dårligt vejr, småsnue og ingen kone eller unger hjemme man begiver sig i kast med den slags :-)
Avatar billede olebole Juniormester
12. november 2004 - 12:58 #14
Prøvede lige en anden JS quick-sort algoritme, jeg fandt på nettet. Den kaldte sammenlignings funktionen over 3.500 gange!  :)

Nu er det jo heller ikke kun et spørgsmål om, hvormange sammenligningskald der foretages, som er interessant. Måden, hvorpå data store's i hukommelsen under sorteringen, er mindst ligeså interessant ... og hvordan sammenligningerne foretages, m.m.
Der er en del parametre at tage hensyn til, når performance skal beregnes og afvejes.
Avatar billede -mundi- Nybegynder
12. november 2004 - 13:01 #15
jeg har cachet værdierne i nogen objecter i et array, så nu flyver det bare derudaf. Det var DOM der sløvede det hele, men det er jo åbenlyst, her i bagklogskabens timer
Avatar billede -mundi- Nybegynder
23. november 2004 - 00:19 #16
smider du et svar olebole ?
Avatar billede olebole Juniormester
23. november 2004 - 00:24 #17
Det glæder mig, du fandt ud af, hvordan den slags skal laves. Du kan formodentlig også se, det er en langt mere robust måde at kode sådan noget på  ;o)
Avatar billede -mundi- Nybegynder
23. november 2004 - 08:02 #18
Ja, det gav mig lige det sidste skub :-)
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Webudvikling kurser
Vi tilbyder markedets bedste kurser inden for webudvikling
Se alle Webudvikling kurser

Flere spørgsmål fra JavaScript kategorien

Titel Indlæg Oprettet Seneste aktivitet
problem med download i <a href=" " download> tag i JavaScript Af Peer i JavaScript 5 27/04/202620:09 03/05/202613:59
Validering af filnavn i formular Af Strawberry i JavaScript 8 14/04/202610:11 20/04/202611:14
Mangler et JavaScript til htm side med iframe i Joomla5 Af Peder Lund Nielsen i JavaScript 2 03/02/202614:19 04/04/202616:02
Åbne en PDF fil fra en mappe Af mbl i JavaScript 9 18/04/202516:52 22/04/202512:33
Spørgsmål til cookies Af Mads i JavaScript 2 14/02/202511:47 27/06/202514:34
Se alle spørgsmål i kategorien Opret spørgsmål

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Opret Log ind

Du kan også logge ind via nedenstående tjenester

Alle kategorier på Eksperten
Seneste spørgsmål Seneste aktivitet
I går 14:53 TV4ever 3.0 Af valby i Diverse
01/0816:21 Installere Ubuntu på Virtuel Maskine Af Uvanga i Andet software
01/0809:38 Microsoft har igen ødelagt mit højreklik Af valby i Windows
30/0714:41 To mails fra YouSee - Jeg tror ikke altid på tilfældigheder Af mort1 i Andet sikkerhed
27/0714:34 Hjælp til at kunne skanne negativer på Plustek 8300i SE Af Mariann i Foto & video
White papers
Flere white papers »