Toon posts:

[alg] Insertion Sort probleem

Pagina: 1
Acties:

maandag 10 maart 2003 19:33

Acties:

Verwijderd

Topicstarter
'k zit met het volgende probleem voor school hebben wij een relatief simpele opdracht gekregen om een algoritme aan te passen, het gaat hier dus om een Insertion Algoritme.

Nu is het principe me wel duidelijk, ende volgende code ook:

C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void insertionSort()
{
   int in, out;

   for(out=1; out < nElems; out++)      // out is dividing line
   {
        int temp = rij[out];            // remove marked item
        in = out;                       // starts shift at out
        while(in > 0 && rij[in-1] >= temp) // until one is smaller,
        {
                rij[in] = rij[in-1];       // shift item to right
                in--;                      // go left one position
        }
        rij[in] = temp;                    // insert marked item
   } // end for
} // end inertionSort()


Bij dit algortime begint ie vooraan en werkt naar achteren toe, maar nu wil ik achteraan beginnen en dan naar voren! Ik heb al van alles geprobeerd maar het wil maar niet lukken.

En het schijnt zo te zijn dat je dit algoritme nog kan verbeteren door 'm binair te laten zoeken, maar ik zie niet echt waar je dat dan zou moeten plaatsen!

Ik hoop dat iemand mij in de goede richting kan sturen, en wil er ff op wijzen dat ik GEEN uitgewerkte antwoorden wil hebben, aangezien het opdrachten betreft voor school!

maandag 10 maart 2003 19:47

Acties:
  • SWfreak
  • Registratie: Juni 2001
  • Niet online

SWfreak

insertionSort is insertionSort, dat kun je niet echt versnellen. Binair zoeken werkt alleen als je array al gesorteerd is, dus dat kan niets helpen voor je sorteeralgoritme. Er bestaan wel algoritmen die sneller zijn (quicksort, mergesort).
Als je snapt hoe insertion sort werkt, zou je eigenlijk ook moeten begrijpen hoe je het van achter naar voren moet doen. tis een kwestie van een paar dingetjes omdraaien (+ naar - enzo).
Is er eigenlijk een reden waarom je het anders wilt doen? Het maakt (theoretisch gezien) namelijk geen bal uit of je van voor naar achter of van achter naar voor gaat.

[ Voor 6% gewijzigd door SWfreak op 10-03-2003 19:47 . Reden: typos ]

maandag 10 maart 2003 20:04

Acties:

Verwijderd

Topicstarter
De reden om van achter naar voor te gaan, en binair zoeken te implementeren is omdat het gaat om opdrachten voor school, zoals onderaan staat! :)

Je hebt waarschijnlijk wel gelijk met insertionSort = insertionSort, maar het gaat, zoals ik al zei, om opdrachten voor school! Heb ze ook nie verzonnen! ;)

Ok, van achter naar voor sorteren is me gelukt! Me fout zat 'm in het groter dan (>) teken! 8)7

[ Voor 15% gewijzigd door Verwijderd op 10-03-2003 20:30 ]

Reageer