Bonjour,

Il y a des mois que je suis resté bloqué en face d'un problème qui demande de trier deux tableaux :

LIMITES DE TEMPS ET DE MEMOIRE (Langage : C)

Temps : 0.5s sur une machine à 1Ghz. 
Mémoire : 16000 Ko.

CONTRAINTES

ENTRÉE

SORTIE

EXEMPLE

entrée :

6
1 6
2 3
4 12
3 7
5 25
7 18

sortie :

2 3
1 6
3 7
4 12
7 18
5 25

bon, j'ai réussi à écrire un code qui affiche correctement mais pour 3 tests, il prend plus que 0.5s

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
  cin.sync_with_stdio(false);
  int nbre;
  cin>>nbre;
  int tableau1[nbre];
  int tableau2[nbre];

  for(int i=0;i<nbre;i++)
  {
    cin>>tableau1[i]>>tableau2[i];
    if(i>0)
    {int c=0;
      for(int b=i-1;b>=0;b--)
      {
        if(tableau2[b]>tableau2[i-c])
        {
          int rapport=tableau2[i-c];
          int rapport1=tableau1[i-c];;
          tableau2[i-c]=tableau2[b];
          tableau1[i-c]=tableau1[b];
          tableau2[b]=rapport;
          tableau1[b]=rapport1;
        }
        else if(tableau2[b]==tableau2[i-c])
        {
          if(tableau1[b]>tableau1[i-c])
          {
            
         int  rapport1=tableau1[i-c];
          
          tableau1[i-c]=tableau1[b];
          
          tableau1[b]=rapport1;
          }
        }
        else
        {
          b=-1;
        }
        c++;
      }
    }
  }

 for(int i=0;i<nbre;i++)
  {    
      cout<<tableau1[i]<<" "<<tableau2[i]<<endl;
  }
}
          
        

Je ne sais pas comment je dois faire pour le rendre plus rapide, c'est pour cela que je demande votre aide.

merci d'avance

-
Edité par garmel 5 juillet 2015 à 6:29:25

garmel a écrit:

LIMITES DE TEMPS ET DE MEMOIRE (Langage : C)

#include<iostream>
#include<algorithm>

En C ou en C++ ?

En plus, tu inclus algorithm qui contient des fonctions de tri. Pourquoi ne pas les utiliser ?

Sinon, le tri par insertion n'est pas le plus rapide des tris vu que tu n'est pas sur un programme à flux (toutes les données te sont accessibles instantanément). Récupère toutes tes données puis effectue un tri rapide ou un tri par fusion (ça devrait passer dans toute la mémoire qu'on t'autorise à avoir). Sinon, tu peux stocker tes données dans une structure/classe et trier un tableau d'identifiants interne (l'indice de ta structure). Les copies seront bien moins importantes et ça te fera gagner un temps précieux.

-
Edité par anolya 5 juillet 2015 à 8:14:51

En fait, j'ai utiliser "sort", "tri rapide", "tri par fusion", mais c'est toujours le 9 ème test qui prend plus que 0.5 s

Je pense que tu dois avoir des soucis de cache. Tes 2 tableaux sont éloignés en mémoire l'un de l'autre et tu les modifies en même temps. Si, à chaque fois, tu as du cache miss, tu risques d'écraser ton autre tableau et donc tu te retrouveras avec un autre cache miss. De ce fait, le temps d'exécution va être beaucoup plus important.

Je viens de coder un truc. Si tu avais l'endroit où je peux le tester pour vérifier qu'il répond bien aux 12 tests... (histoire que je ne dise pas de bêtises et que je ne te ponde pas la solution toute faite)

Malheureusement, seulement si vous avez un compte et si vous avez déjà débloquer le 3 ème niveau.

Enfin, résolu...En effet, merci beaucoup anolya de me faire connaître le tri par fusion....Il est le plus rapide dont la complexité est minimale

Attention, même si le tri par fusion a une complexité en O(n ln(n)), même dans le pire des cas, ce n'est pas un tri sur place (contrairement au quick sort). En effet, on a besoin, au minimum, de la moitié de la taille du tableau à trier en mémoire supplémentaire.

-
Edité par anolya 5 juillet 2015 à 23:17:59

anolya a écrit:

Attention, même si le tri par fusion a une complexité en O(ln(n)), même dans le pire des cas

Ça serait tellement beau… 

O(n * log(n))

-
Edité par Mad scientist 5 juillet 2015 à 23:16:58

Ah oui, oublié le n, je l'ajoute.

Ah tu as gâché mes rêves. 

@KimKossiAfangnike Bonjour,  merci de ne pas squatter le sujet résolu des autres, créer votre propre sujet dans le respect des règles du forum à savoir qu'un message commence par des règles de politesses (Un bonjour ou des salutations à la communauté et se termine par des remerciements par avances pour les futures réponses), la description de votre problème et le code que vous avez écrit inséré sur le forum à l'aide de l'outil d'intégration de code soit le bouton code </>.

Déterrage

Citation des règles générales du forum :

Avant de poster un message, vérifiez la date du sujet dans lequel vous comptiez intervenir.

Si le dernier message sur le sujet date de plus de deux mois, mieux vaut ne pas répondre.
En effet, le déterrage d'un sujet nuit au bon fonctionnement du forum, et l'informatique pouvant grandement changer en quelques mois il n'est donc que rarement pertinent de déterrer un vieux sujet.

Au lieu de déterrer un sujet il est préférable :

• soit de contacter directement le membre voulu par messagerie privée en cliquant sur son pseudonyme pour accéder à sa page profil, puis sur le lien "Ecrire un message"
• soit de créer un nouveau sujet décrivant votre propre contexte
• ne pas répondre à un déterrage et le signaler à la modération

Liens conseillés

• Charte de bonne conduite
• Règles générales du forum