Speciel Array Sorterings Index

Det ville være for cool med en hjælpende hånd ;) - Mvh Fini

Fandt lige en sjov side der visuelt viser sortering algoritmer:

http://www.eecs.harvard.edu/~ellard/Q-97/Demos/SortDemo/sorts.html

<script language=\'javascript\'>

function createSortIndex( arr ) {
    var kopi = new Array();
    for (var i=0; arr.length>i; i++ ) kipi[i] = arr[i];
    kopi.sort();
    var res = new Array();
    var j1,j2,k;
    for (var i=0; arr.length>i; i++ ) {
        j = kopi.length;
        k = Math.floor(j/2)
        for ( ; kopi[k]!=arr[i]; } {
          k = Math.floor((j1+j2)/2)
          if ( kopi[k] > arr[i] ) j2 = k-1;
          if ( kopi[k] < arr[i] ) j1 = k+1;
        };
        res[i] = k;
    };
    return res;
}; //end createSortIndex( Array object ) -> Array object

var a = new Array(\'D\',\'B\',\'A\',\'C\',\'A\');
var b = createSortIndex(a);

</script>

mvh JakobA

Ups. i første forløkke staver jeg kop forkert. det skal være:
    for (var i=0; arr.length>i; i++ ) kopi[i] = arr[i];

hey JakobA du er for sej!

jeg får en syntax error på:

for ( ; kopi[k]!=arr[i]; } {

hvad skal der rigtigt stå?+ ;)

Ups. Ups. Og jeg initierer ikke j1 og j2 og k ordentligt:
udskift:
        j = kopi.length;
        k = Math.floor(j/2)
med:
        j1 = 0;
        j2 = kopi.length;
        k = 0;

Ups Ups Ups :[

  <script language=\'javascript\'>

function createSortIndex( arr ) {
    var kopi = new Array();
    for (var i=0; arr.length>i; i++ ) kopi[i] = arr[i];
    kopi.sort();
    var res = new Array();
    var j1,j2,k;
    for (var i=0; arr.length>i; i++ ) {
        j1 = 0;
        j2 = kopi.length;
        k = 0;
        for ( ; kopi[k]!=arr[i]; ) {
          k = Math.floor((j1+j2)/2)
          if ( kopi[k] > arr[i] ) j2 = k-1;
          if ( kopi[k] < arr[i] ) j1 = k+1;
        };
        res[i] = k;
    };
    return res;
}; //end createSortIndex( Array object ) -> Array object

var a = new Array(\'D\',\'B\',\'A\',\'C\',\'A\');
var b = createSortIndex(a);

</script>

mvh JakobA

sejt nok, dog får begge A\'er værdien 0

alert(b.join(\',\'))  => 4,2,0,3,0

den burde helst give 4,2,0,3,1

hvis muligt ;) doh.. Men for sejt, at du reagerede så hurtigt ;) wow.!

[\'a\',\'a\',\'a\'] => [0,1,2]
[0,\'A\',1] => [0,2,1]

OSV..

Hmm. Er det ok at jeg siger der max kan være 58 ens entries med en given værdi?

hmm I guess ;)  men hvorfor 58? he he

Brug følgende funktion:

function createSortIndex(arr)
{

  function compar( a, b )
  {
      var retval;
      if (arr[a] < arr[b]) {
        retval = -1;
      }
      else if (arr[a] == arr[b]) {
        retval = 0;
      }
      else if (arr[a] > arr[b]) {
        retval = 1;
      }
      return retval;
  }

  var sortIndex = new Array(arr.length);
  for (i = 0; i < arr.length; i++) {
      sortIndex[i] = i;
  }
  sortIndex.sort( compar );
  return sortIndex;
}

Princippet er, at den starter med at skabe et array sortIndex, der initialiseres
til værdierne 0..arr.length-1. Sidenhen sorteres dette array med Array.sort, men
med en compare funktion, der kigger i det oprindelige array for at finde ud af
rækkefølgen. Resultatet er at sortIndex sorteres som om det var det originale
array, og det var vist lige hvad du havde brug for.

Mvh
Jesper Naur

hej jespernaur, truly den sejeste måde at gøre det på,

for god ordens skyld lister jeg lige koden til at teste det med:

var a = new Array(\'D\',\'B\',\'A\',\'C\',\'A\',\'A\',\'C\');
var b = createSortIndex(a);

for(i = 0; i < b.length; i++) {

    document.write(a[b[i]] + \'<br>\');
}

I får begge to points for den storslåede indsats ;)
tak gutter!

håber i kan klare jer med 60 points hver ;)

jakoba: Jeg var ellers igang med at lave en parser til din funktion, som kunne lave [3,0,0,0,3] om til [3,0,1,2,4],
men bruger jespernaurs kode istedet, da det virker perfekt, hvad mere kan man kræve ? ;)

Endnu en gang tak til jer begge to.. cu.. Fini

Fordi min første ide var at sætte et extra bogstav (0-9A-Za-z) bagefter dem der var ens.
men det gir formeget bøvl med at holde rede i hvem der er hvilken \'vi er ens\'-gruppe, så jeg gik fra den igen og lavede istedet alle elementer om til arrays indeholdende elementet og et løbenummer.

Det tager hulens meget mere køretid så i en virkelig situation ku det godt være jeg ville bruge den første metode.

allenfals her er resultatet:
http://hjem.get2net.dk/Jakob.Aggernaes/temp/exp102125.html

mvh JakobA

Jamen så simpelt det kan gøres når man tænker før man programmerer. :-))
Tak for jeg også fik nogen.

Øh, jespernaur >> er det dig der spiller klaver?

Jeg tænkte nok at Array.sort() kunne bruges til noget vildt med den ekstra parameter, men jeg kunne ikke gennemskue hvordan det precist skulle hænge sammen ;)

Det gør jeg faktisk

Men vi har et problem. de to algoritmer giver vidt forskellige resultater:
\'D\',\'B\',\'A\',\'C\',\'A\'
ja  -> 4,2,0,3,1
naur-> 2,4,1,3,0

FYI:

Man kan nemt lave omvendt sortering:

var b = createSortIndex(a).reverse();

hmm. ja det er vel egentlig jakobs der er \"mest\" korrekt..?

Det eneste man kan diskutere er rækkefølgen af de 2 identiske \'A\'er. Så vidt jeg kan bedømme, er rækkefølgen 4,2,0,3,1 ved siden af, ville svare til

AADCB

Hvorvidt 4 eller 2 (det ene eller det andet A)skal stå først, er nok en smagssag. Det er dog tydeligt, at algoritmen i Array.sort IKKE har egenskaben stabil (som betyder, at identiske nøgler bevarer rækkefølgen i det sorterede output).

Mvh
Jesper Naur

jep, korrekt, dog virker det pt. som det skal i mit program, men det er vel ikke noget man kan regne 100% med hvis Array.sort fungerer som du (jesper) lige beskrev.

Jeg tror mere det er definitionen af hvad præcis et sortIndex er vi er uenige om:
4,2,0,3,1  afspejler slutposition  4 fordi *D\' ender med at stå sidst.
2,4,1,3,0  afspejler startposition  0 fordi \'D\' startede med at stå først.

mvh JakobA

nåh, ja.. jeg testede lige mit program med jakobs funktion og fik det omvendte resultat af jespers funktion, begge to virker, bare .reversed() i forhold til hinanden ;)

var aa = new Array(\'D\',\'B\',\'A\',\'C\',\'A\');

var aaIdx = createSortIndexJakobA(aa);
    for(i = 0; i < aa.length; i++) {
   
        document.write( aa[aaIdx[i]]+\' - \' + aaIdx[i] +\'<br>\');
    }

giver AADCB, der må da være da være noget galt her, jakob?

;)

Hvad har du behov for? Du kan \'reverse\' min ved at vende ulighedstegnene i \'compar\'. Der er ingen grund til først at sortere \'omvendt\' for derefter at \'reverse\' det for at få det på plads, når man ligeså godt kan få det rigtigt i første hug.

Angående jakob\'s AADCB: Det har jeg allerede nævnt

jesper: det virker fint med din rutine, jeg så godt at du nævnte det med AADCB, men jeg var bange for at vi brugte forskellige Arrays som udgangspunkt.. ;)

Jeg indser nu, at man i dette særlige tilfælde kan opnå
egenskaben \'stabil\' ved at inddrage det oprindelige index i sammenligningen foretaget
af \'compar\', således:

  function compar( a, b )
  {
      var retval;
      if (arr[a] < arr[b]) {
        retval = -1;
      }
      else if (arr[a] == arr[b]) {
        if (a < b) {
            retval = -1;
        }
        else {
            retval = 1;
        } // The indices a and b can by definition not be identical
      }
      else if (arr[a] > arr[b]) {
        retval = 1;
      }
      return retval;
  }

Det kan du overveje, hvis du har brug for \'stabil\' egenskaben

her kan i se hvad jeg har brugt det her sjov til ;)
det er egentlig kun en test, indtil videre, når det virker perfekt laver jeg noget mere generelt end \"Books\"..

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

<html>
<head>
        <title>Untitled</title>
        <link rel=\"stylesheet\" href=\"common.css\" type=\"text/css\">

<script language=\"JavaScript\" type=\"text/javascript\">

function _arraySwap(a, b) {

    var c = this[a];
    this[a] = this[b];
    this[b] = c;
}


Array.prototype.swap = _arraySwap;

var bc;
function init() {

    var bc = new gBookCollection(\'Sci-Fi books\');
    bc.addBook(\'Neuromancer\', \'William Gibson\', \'1984\', \'bgh614646\', \'\', \'\', \'Sci-Fi Bible\', \'A good book, read it now...\',\'3rd edition\');

    bc.addBook(\'Klingon Attack Strategy\', \'A. W. Henderson,Homer E. Simpson\', \'2301\', \'zgh666564\', \'\', \'\', \'Warfare at it\\\'s best\', \'A good book, read it before every battle...\',\'\');

    bc.addBook(\'Nano Meister\', \'William Gibson\', \'1984\', \'bgh614646\', \'\', \'\', \'Sci-Fi Bible\', \'A good book, read it now...\',\'2nd edition\');

    bc.addBook(\'Amazing Dreams\', \'Fini A. Alring, Thomas Pri, Thomas Alb\', \'1993\', \'a53453453\', \'\', \'\', \'Sci-Fi Bible\', \'A good book, read it now...\',\'Paperback\');


    var sortIdx = getSortIndex(bc.books, \'bAuthors[0]\');
   
    //alert(sortIdx.join(\',\'));
    document.write(\'<b>Sort by Author:</b><br>\');
    for(i = 0; i < sortIdx.length; i++) {
   
        document.write(bc.books[sortIdx[i]].bName + \' - \' + bc.books[sortIdx[i]].bYear + \' - \' + bc.books[sortIdx[i]].bAuthors.join(\', \') + \'<br>\');
    }
    document.write(\'<br><br><b>Sort by Year:</b><br>\');
   
    sortIdx = getSortIndex(bc.books, \'bYear\');
   
    for(i = 0; i < sortIdx.length; i++) {
   
        document.write(bc.books[sortIdx[i]].bName + \' - \' + bc.books[sortIdx[i]].bYear + \'<br>\');
    }

    document.write(\'<br><br><b>Sort by Year (Reversed):</b><br>\');
   
    sortIdx = sortIdx.reverse();
   
    for(i = 0; i < sortIdx.length; i++) {
   
        document.write(bc.books[sortIdx[i]].bName + \' - \' + bc.books[sortIdx[i]].bYear + \'<br>\');
    }
}


/*
var aa = new Array(\'D\',\'B\',\'A\',\'C\',\'A\');

var aaIdx = createSortIndex(aa);
    for(i = 0; i < aa.length; i++) {
   
        document.write( aa[aaIdx[i]]+\' - \' + aaIdx[i] +\'<br>\');
    }
*/

window.onload = init;



function gBookCollection(bcName) {

        this.bcName = bcName;
        this.books = new Array();
       
        this.addBook = function(bName, bAuthor, bYear, ISBN, thumbSrc, photoSrc, synopsis, comment, revisionComment) {
       
                this.books[this.books.length] = new gBook(bName, bAuthor, bYear, ISBN, thumbSrc, photoSrc, synopsis, comment, revisionComment);

        }

}



function gBook(bName, bAuthorStr, bYear, ISBN, thumbSrc, photoSrc, synopsis, comment, revisionComment) {

        this.bName = bName;
        this.bAuthorStr = bAuthorStr;
        this.bAuthors = new Array();
        if(this.bAuthorStr.indexOf(\',\') != -1) { // grab each author into his own array, later make author object.

                this.bAuthors = bAuthorStr.split(\',\');
        }
        else {
                this.bAuthors[0] = bAuthorStr;
        }
        this.bYear = bYear;   
        this.ISBN = ISBN;
        this.thumbSrc = thumbSrc;
        this.photoSrc = photoSrc;
        this.synopsis = synopsis;
        this.comment = comment;
        this.revisionComment = revisionComment;
}
/*
        var sortIndex = new Array();
        var sortIndexId = new Array();
*/       
       
function getSortIndex(objArray, sortByPropName) {

        sortIndexBase = new Array();
        var sortIndex;

        var outPut = new Array();

       
        for(var i = 0; i < objArray.length; i++) {
       
                sortIndexBase[sortIndexBase.length] = eval(\'objArray[\' + i + \'].\' + sortByPropName);
        }
      // alert(sortIndexBase.join(\',\'));

        return createSortIndex(sortIndexBase);
}


function createSortIndex(arr) {

  function compar( a, b ) {
      var retval;
      if (arr[a] < arr[b]) {
        retval = -1;
      }
      else if (arr[a] == arr[b]) {
        retval = 0;
      }
      else if (arr[a] > arr[b]) {
        retval = 1;
      }
      return retval;
  }

  var sortIndex = new Array(arr.length);
 
  for (i = 0; i < arr.length; i++) {
      sortIndex[i] = i;
  }
  sortIndex.sort( compar );
  return sortIndex;
}   



function compar( elmA, elmB ) {
    if ( elmA[0] < elmB[0] ) return -1;
    if ( elmA[0] > elmB[0] ) return 1;
    return elmA[1]-elmB[1];
}

function createSortIndexJA( arr ) {
    var kopi = new Array();
    var kop2 = new Array();
    for (var i=0; arr.length>i; i++ ) {
        kopi[i] = new Array(arr[i],i);
        kop2[i] = new Array(arr[i],i);
    };
    kop2.sort( compar );
    var res = new Array();
    var j1,j2,k,c;
    for (var i=0; arr.length>i; i++ ) {
        j1 = 0;
        j2 = kopi.length;
        c = 1
        for ( ; c != 0; ) {
            k = Math.floor((j1+j2)/2)
            c = compar( kop2[k], kopi[i] );
          if ( c < 0 ) j1 = k+1;
          if ( c > 0 ) j2 = k-1;
        };
        res[i] = k;
    };
  // document.forms[\'testform\'].uddata.value = res.toString();
    return res;
}; //end createSortIndex( Array object ) -> Array object


</script>



</head>

<body>

</body>
</html>

cool jesper!, jeg bruger den nu, kan ikke se forskel, men som du nævnte er det jo kun i særlige tilfælde ;)  ?

Nu tror jeg endelig jeg har fundet ud af hvad der foregår.
Array.sort() ER stabil. Men kun hvis man ikke definerer sin egen compareroutine.

De to algoritmer finder 2 \'inverse\' versioner af det samme array. de kan inverteres til hinanden med:
  for ( i=0; arr.length>i; i++) jaIndexSort[jnSortIndex[i]] = i;
  for ( i=0; arr.length>i; i++) jnSortIndex[jaIndexSort[i]] = i;

med input Array:
        \'D\',\'B\',\'A\',\'C\',\'A\',\'D\',\'B\',\'A\',\'C\',\'A\',\'D\',\'B\',\'A\',\'C\',\'A\'
giver min
        12,6,0,9,1,13,7,2,10,3,14,8,4,11,5  som inverterer til
        2,4,7,9,12,14,1,6,11,3,8,13,0,5,10
jespers giver:
        2,4,7,9,12,14,1,6,11,3,8,13,0,5,10  som inverterer til
        12,6,0,9,1,13,7,2,10,3,14,8,4,11,5

vi blev vildledt af at
4,2,0,3,1
2,4,1,3,0  ligner en ombytning af 0 med 1 og af 2 med 4.
men det er det faktisk ikke. den interne Array.sort() er stabil.

mvh JakobA

Har \'stabil\' en præcis definition hvis man vil lave en descending sort?

Hvis man ikke definerer en compare-funktion, er det ikke muligt at fastslå,
om Array.sort er stabil eller ej. Forklaring: Vi går tilbage til det oprindelige
simple eksempel:

var a = new Array(\'D\',\'B\',\'A\',\'C\',\'A\');

Ved udførelse af a.sort(); opnår man den korrekt sorterede rækkefølge AABCD - det er
dog ikke muligt at fastslå, hvilket af de oprindelige A\'er (fra position 2 eller 4) der
er endt i position 0, og hvilket der er endt i position 1. Dette er dog nok
også ligegyldigt, da de jo er ens.

Der hvor egenskaben \'stabil\' kan have betydning, er tilfælde hvor en record består
af sorterings-nøglen plus noget ekstra data, der ikke skal indgå i sorteringen. Her
kan det (afhængig af anvendelsen) have betydning, om records med identisk sorterings-nøgle
bevarer deres oprindelige rækkefølge. Den slags anvendelser kræver brug af en compare-
funktion, for at nøjes med at sammenligne den del af data, der faktisk hører til
sorterings-nøglen, og ikke den del, der bare \'følger med\'.

Mht \'stabil\' og \'descending\' rækkefølge: Det er ligegyldigt! \'Stabil\' betyder, at
records med identiske sorterings-nøgler bevarer deres oprindelige indbyrdes rækkefølge
i det sorterede output. De kommer i sagens natur til at stå ved siden af hinanden,
i deres oprindelige rækkefølge, men hvorvidt records med forskellige nøgler sorteres
den ene eller den anden vej, har ingen betydning for dette.

Mvh
Jesper Naur