[C++]Ouput hoog-laag

[Chip.]

Hallo,

Ik heb een programma dat de afstand van x aantal, in dit geval 3, punten van elkaar berekent. Dit is de code:

C++:

#include <iostream>
#include <cmath>
using namespace std;

struct Punt
{
    float x;
    float y;
};

float afstandP2P(Punt p1, Punt p2)
{
    return sqrt(pow(p1.x - p2.x,2) + pow(p1.y - p2.y,2));
}

int main()
{
    Punt p1, p2, p3;
    
    cout << "Bereken de afstand van 3 punten tot elkaar." << endl;
    cout << "Voer de x-coordinaat in voor punt 1: ";
    cin >> p1.x;
    cout << "Voer de y-coordinaat in voor punt 1: ";
    cin >> p1.y;
    cout << endl << "Voer de x-coordinaat in voor punt 2: ";
    cin >> p2.x;
    cout << "Voer de y-coordinaat in voor punt 2: ";
    cin >> p2.y;
    cout << endl << "Voer de x-coordinaat in voor punt 3: ";
    cin >> p3.x;
    cout << "Voer de y-coordinaat in voor punt 3: ";
    cin >> p3.y;
    
                // Cout
}

Nu moet ik ervoor zorgen dat het programma dus de afstand van alle punten van elkaar berekent dus:
De afstand van punt 1 naar punt 2, afstand van punt 2 naar punt 3 en de afstand van punt 3 naar punt 1 niet moeilijk toch? Nauw nu zit ik met het volgende probleem ik moet de afstand van die 3 outputten in de volgorde van hoog naar laag. Nu kan ik dit doen met een heleboel if else structuur maar ik vroeg me af of er geen gemakkelijkere manier is???

[NMe]

Arrays en een standaard sorteeralgoritme? Dat kan sequentiëel zijn, of iets als quicksort als je daaraan toe bent.

[MrBucket]

Zoals de poster hierboven me al zegt, plaats de afstanden in een array.
Je kunt dan de sort-implementatie van de STL gebruiken: http://www.sgi.com/tech/stl/sort.html.

De tekst op deze pagina zal je waarschijnlijk een beetje als chinees in de oren klinken, maar er wordt een voorbeeldje gegeven van hoe je sort() moet gebruiken

[Chip.]

Zal eens ermee gaan prutsen

[.oisyn]

Als je 3 dingen sorteren wilt sorteren dan kun je dat natuurlijk ook gewoon met de hand doen door 3x te verwisselen: Als het tweede element hoger is dan het eerste, wissel ze om. Als het derde element hoger is dan het tweede, wissel ze om. Als het tweede element vervolgens weer hoger is dan het eerste, wissel ze weer om. Nu zijn ze gegarandeerd gesorteerd

[MeMoRy]

ik weet niet of je ook nog moet herinneren welke afstanden tussen welke punten zijn, dan zou je nog een structje moeten maken

code:

struct Afstand
{
    int begin;
    int eind;
    float afst;
};

[Verwijderd]

.oisyn schreef op vrijdag 23 februari 2007 @ 23:10:
Als je 3 dingen sorteren wilt sorteren dan kun je dat natuurlijk ook gewoon met de hand doen door 3x te verwisselen: Als het tweede element hoger is dan het eerste, wissel ze om. Als het derde element hoger is dan het tweede, wissel ze om. Als het tweede element vervolgens weer hoger is dan het eerste, wissel ze weer om. Nu zijn ze gegarandeerd gesorteerd

Oftewel, sequential sort. Bij weinig elementen heel simpel, handig en performant, maar als 't aantal elementen oploopt zijn er betere sort algorithmes.

[Teun_2]

Is dat niet bubble sort?
Maar zoek eens naar quicksort/heapsort etc.

[ Voor 48% gewijzigd door Teun_2 op 24-02-2007 16:09 ]

[.oisyn]

Zoutvat schreef op zaterdag 24 februari 2007 @ 16:09:
Maar zoek eens naar quicksort/heapsort etc.

Beetje nutteloos, om iets te sorteren hoef je natuurlijk niet te weten hoe zo'n sorteerfunctie werkt. std::sort() was al geopperd

[FTPlus]

Als het om het sorteren van specifiek 3 waarden gaat gebruik ik meestal deze manier:
(dit is pseudo code)

code:

int a, b, c; // 3 waarden in willekeurige vollgorde

// a=1 b=2 c=3

if (b < a)
    swab(a, b);

// a=2 b=1 c=3

if (c < b)
    swab(b, c);

// a=2 b=3 c=1

if (b < a)
    swab(a, b);

// a=3 b=2 c=1

[Daos]

FTPlus schreef op zondag 25 februari 2007 @ 04:34:
Als het om het sorteren van specifiek 3 waarden gaat gebruik ik meestal deze manier:
(dit is pseudo code)
...

Dat lijkt op Bubblesort. Het is zo'n beetje het slechtste algoritme dat er bestaat. Bovendien kan je beter met arrays werken. Het is kost dan geen moeite om je programma met een ander aantal dan 3 te laten werken.

En waarom zou je een sorteeralgoritme implementeren als er al een implementatie is? Zie hierboven:

MrBucket schreef op vrijdag 23 februari 2007 @ 19:22:
Je kunt dan de sort-implementatie van de STL gebruiken: http://www.sgi.com/tech/stl/sort.html.

[Soultaker]

Daos schreef op zondag 25 februari 2007 @ 11:59:
Dat lijkt op Bubblesort. Het is zo'n beetje het slechtste algoritme dat er bestaat. Bovendien kan je beter met arrays werken. Het is kost dan geen moeite om je programma met een ander aantal dan 3 te laten werken.

Echt niet. De efficiëntie van sorteeralgoritmen wordt pas relevant als je uitgaat van een groot aantal elementen (al is 'groot' een rekbaar begrip en nogal van de situatie afhankelijk). Het gaat om het ordenen van drie elementen, en het sorteren van drie elementen met drie vergelijkingen is optimaal. Je zou wel gek zijn om daar een standaardalgoritme voor aan te roepen, want dat is gegarandeerd veel trager.

Wel grappig in deze context is dat Quicksort ook O(N²) worst case is, maar dat om de worst-case in praktische situaties te vermijden, meestal een optimalisatie wordt toegepast: in plaats van zomaar een element als pivot te kiezen, wordt de mediaan van het eerste, laatste en middelste element van de lijst genomen (dat helpt niet tegen de theoretische worst case, maar wel in de praktijk). Quicksort moet dus intern deze drie waarden sorteren; grote kans dat de Quicksort die in de standard library zit dus intern soortgelijke code bevat als wat oisyn en FTPlus suggereren.

[Daos]

Soultaker schreef op zondag 25 februari 2007 @ 12:29:
[...]

Echt niet. De efficiëntie van sorteeralgoritmen wordt pas relevant als je uitgaat van een groot aantal elementen (al is 'groot' een rekbaar begrip en nogal van de situatie afhankelijk). Het gaat om het ordenen van drie elementen, en het sorteren van drie elementen met drie vergelijkingen is optimaal. Je zou wel gek zijn om daar een standaardalgoritme voor aan te roepen, want dat is gegarandeerd veel trager.

Je hebt inderdaad minimaal 3 vergelijkingen nodig, maar je hebt minder dan de 3 swaps nodig die voorgesteld worden. De volgende code is bijvoorbeeld een stukje sneller:

C:

#include <stdio.h>

void sort3(int *pa, int *pb, int *pc) {
  int a = *pa;
  int b = *pb;
  int c = *pc;
  int tmp;

  if (a <= b) {
    if (a <= c) {
      if (b > c) {
        /* a c b */
        tmp = b;
        b = c;
        c = tmp;
      }
      /* else a b c */
    }
    else {
      /* c a b */
      tmp = c;
      c = b;
      b = a;
      a = tmp;
    }
  }
  else {
    if (a <= c) {
      /* b a c */
      tmp = a;
      a = b;
      b = tmp;
    }
    else {
      if (b < c) {
        /* b c a */
        tmp = a;
        a = b;
        b = c;
        c = tmp;
      }
      else {
        /* c b a */
        tmp = a;
        a = c;
        c = tmp;
      }
    }
  }

  *pa = a;
  *pb = b;
  *pc = c;
}

int main() {
  int a = 3, b = 1, c = 2;

  sort3(&c, &b, &a);

  printf("Gesorteerd van hoog naar laag: %d %d %d\n", a, b, c);

  return 0;
}

Zo kan je blijven doorgaan...

In dit topic is snelheid geen issue, dus ik zie geen reden waarom je niet gewoon de bestaande sort zou kunnen gebruiken.

[.oisyn]

FTPlus schreef op zondag 25 februari 2007 @ 04:34:
Als het om het sorteren van specifiek 3 waarden gaat gebruik ik meestal deze manier:
(dit is pseudo code)

Euh, precies wat ik al zei dus

Daos: Dat kun je niet zeggen. Conditional moves (cmov*) zijn met jouw code bijvoorbeeld niet mogelijk. Bovendien kost een registerswap (xchg) geen drol .
Overigens, veel sorteerroutines quicksorten tot een deellijst onder een bepaalde threshold komt, waarna een shellsort gebruikt wordt.

[ Voor 57% gewijzigd door .oisyn op 25-02-2007 17:29 ]