Trier des points algorithme

Version imprimable

15/01/2019, 15h08
gaddielnabet

Trier des points algorithme

Bonjour j'aurai besoin d'aide pour un algorithme, dans mon programme l'utilisateur rentre le nombre de points qu'il veut trier, après cela les coordonnées x et y de chacun des points, ce que je dois faire c'est afficher les points du plus proche de l'axe au plus éloigné.
Par exemple, pour trois points (4,5) (2,3) (1,2) la réponse sera (1,2) (2,3) (4,5)
15/01/2019, 15h35
ternel

Comment as-tu trié ces trois éléments?
15/01/2019, 16h01
gaddielnabet

j'ai compris que je dois rentrer ces elements dans un tableau, mais c'est justement la le probleme je n'arrive pas trouver l'algorithme qui me permette de trier les points en fonction de leur distance
15/01/2019, 16h20
Kannagi

Citation:

Envoyé par gaddielnabet

je dois faire c'est afficher les points du plus proche de l'axe au plus eloigne.

Lequel des axes ? Soit tu trie par rapport à X , soit par rapport à Y , soit tu fait une moyenne des deux , tout dépend de ce que tu souhaite faire !
Sinon il existe Qsort :roll:
15/01/2019, 17h22
gerald3d

Bonjour.

Je vais émettre une remarque sûrement stupide mais elle a le mérite de ne rien coûter, alors... ;)

Si tu dois classer des points en fonction de leur distance à l'origine, pourquoi ne pas calculer justement cette distance à ce point ? Bon, c'est coûteux en temps de calcul, mais je suppose que l'exercice n'est pas axé sur la performance.
Tu pourrais disposer d'une structure contenant les coordonnées du point et la distance. Le tri se ferait alors assez facilement il me semble. Tu pourrais même te passer d'une telle structure avec un algorithme pensé en amont.

Une autre remarque qui ne mange pas de pain. En français "c" s'écrit "c'est" ou "s'est". C'est selon... :) Ce n'est pas plus cher à écrire et beaucoup plus sympa pour les lecteurs que nous sommes ;).

Citation:

Envoyé par gaddielnabet

j'ai compris que je dois rentrer ces elements dans un tableau, mais c'est justement la le probleme je n'arrive pas trouver l'algorithme qui me permette de trier les points en fonction de leur distance

Petite question. Sais-tu calculer la distance d'un point dans un plan ?
15/01/2019, 18h53
gaddielnabet

Oui je connais la formule de la distance ...x^2+y^2 sous la racine carre mais cela ne change pas grand chose, et justement le programme doit avoir une complexite de temps de nlogn (n represente le nombre de points que l'on souhaite rentrer) et nous n'avons pas appris a utiliser les structures donc impossible d'utiliser ca...
15/01/2019, 19h52
Bousk

Citation:

Envoyé par gaddielnabet

nous n'avons pas appris a utiliser les structures donc impossible d'utiliser ca

Les structures sont justes là pour structurer le code de manière plus logique.
Tu peux très bien avoir 2 tableaux pour les coordonnées au lieu d'un unique tableau d'une struct Point. C'est super moche, si un étudiant me montrait ça je l'insulterais, mais si c'est imposé alors la faute revient au prof.

Citation:

Envoyé par gaddielnabet

mais cela ne change pas grand chose

Ben ça change que c'est la façon de faire :koi:

L'exercice consiste à réimplémenter une fonction de tri.

Citation:

Envoyé par gaddielnabet

le programme doit avoir une complexite de temps de nlogn

Donc un Merge sort correspond d'après le tableau précédent.
15/01/2019, 20h27
gaddielnabet

Merci pour ton aide,j'avais egalement pense a utiliser merge sort mais je n'arrive pas a trouver de quel maniere...

La distance d'un point est bien égale à à la racine carrée de (x² + y²) (merci M. Pythagore :)). On peut d'ors et déjà se passer de la racine pour gagner en temps de calcul.

Ensuite il faut connaître l'intervalle des points traiter. Peuvent-ils avoir des coordonnées négatives ? Quels sont les limites de ces mêmes coordonnées ? La réponse à ces deux questions va permettre de traiter le signe de la distance (même si mathématiquement c'est bien entendu faux) et de savoir de quel type devra être le tableau qui va recevoir les valeurs des distances calculées.

En admettant que les coordonnées peuvent être négatives voila un pseudo-code possible :
Code:

1 2 3 4 5 6 7 8 9 index = 0 tant qu'il y a un point à traiter sauver le point dans un tableau point à la position index distance = x*x + y*y si x ou y négatif alors distance égale -distance sauver distance dans le tableau dist incrémenter l'index fin tant que
À la sortie on dispose d'un tableau dist [] dans lequel on a toutes les distances non triées. Il suffit ensuite de le trier en utilisant l'algorithme mergesort dont le lien du post précédent de Bousk te donne le code source et le pseudo-code !

Lors du tri il faut sauver dans un nouveau tableau indextri [] pas exemple non pas les distances triées mais les index du tableau dist [] trié. Ainsi, il suffira pour afficher les points triés d'utiliser les valeurs du tableau indextri [] comme index pour le tableau point [].

16/01/2019, 19h41
Matt_Houston
S'il s'agit de trier les points par rapport à leur éloignement à une droite alors le critère de comparaison est la valeur du produit scalaire du vecteur de projection orthogonale avec lui-même, soit le carré de sa norme.

On a le choix de calculer ce produit scalaire :
- à l'avance, une fois pour chaque point et réaliser plusieurs parcours de la collection ;
- à chaque comparaison (donc plusieurs fois pour chaque point dans le cas général) et réaliser un seul parcours de la collection.
La mise en cache utilise moins de temps processeur mais plus de mémoire et c'est l'inverse pour la seconde méthode.

Quoiqu'il en soit il y a au moins deux fonctions à écrire :
1. la fonction d'ordre, qui attend deux points et est indépendante ;
2. celle qui implémente l'algorithme de tri, qui attend une collection d'éléments (peu importe qu'il s'agisse de points, de chaînes ou de nouilles) et fait appel à la fonction d'ordre.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void EnterMessage();
void EnterPoints();
void SortedPoints();
void TopDownMergeSort(int A[],int B[],int n,int sorter_point[]);
void TopDownSplitMerge(int B[],int iBegin,int iEnd,int A[],int sorter_point[]);
void TopDownMerge(int A[],int iBegin,int iMiddle,int iEnd,int B[],int sorter_point[]);
void CopyArray(int A[],int iBegin,int iEnd,int B[]);
 
int main()
{
EnterMessage();
int number_points;
scanf(" %d",&number_points);
int points[number_points][number_points];
int distance[number_points];
int help_array[number_points];
int sorter_points[number_points];
for (int i=0;i<number_points;i++){
        EnterPoints();
        for (int j=0;j<2;j++){
        scanf(" %d", &points[i][j]);
        distance[i]+=(points[i][j]*points[i][j]);}
    }
TopDownMergeSort(distance,help_array,number_points,sorter_points);
printf("%d",sorter_points[0]);
  return 0;
}
void EnterMessage(){
printf("Enter number of points: ");}
void EnterPoints(){
    printf("Enter point: ");}
void SortedPoints(){
printf("Sorted points: ");}
 
 
 
 
 
 
void TopDownMergeSort(int A[],int B[],int n,int sorter_point[])
{
    CopyArray(A, 0, n, B);
    TopDownSplitMerge(B, 0, n, A,sorter_point);
}
 
void TopDownSplitMerge(int B[],int iBegin,int iEnd,int A[],int sorter_point[])
{
    if(iEnd - iBegin < 2)
        return;
 
 
    int iMiddle = (iEnd + iBegin) / 2;
    TopDownSplitMerge(A, iBegin,  iMiddle, B,sorter_point);
    TopDownSplitMerge(A, iMiddle,iEnd, B,sorter_point);
 
 
    TopDownMerge(B, iBegin, iMiddle, iEnd, A,sorter_point);
}
 
void TopDownMerge(int A[],int iBegin,int iMiddle,int iEnd,int B[],int sorter_point[])
{
int    counter=0;
    int i = iBegin, j = iMiddle;
    for (int k = iBegin; k < iEnd; k++) {
        if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            sorter_point[counter]=i;
            i = i + 1;
            counter++;
        } else {
            B[k] = A[j];
            sorter_point[counter]=j;
            j = j + 1;
            counter++;
        }
    }
}
 
void CopyArray(int A[],int iBegin,int iEnd,int B[])
{
    for(int k = iBegin; k < iEnd; k++)
        B[k] = A[k];
}

MErci a tous pour vous reponses qui m'ont deja beaucoup aide, mais le programme ne fonctionne pas encore totalement je pense que le probleme se situe lorsque j'essaye de trier les distances et les index en meme temps...

17/01/2019, 11h46
gaddielnabet

Merci pour l'idee mais je bloque justement sur le tri et l'agencement du tableau des index en meme temps...