Cuisine fine - Demi finale 2009

Bonjour j'ai besoin d'aide, je dépasse la limite de temps sur cet exo (http://www.prologin.org/training/challenge/demi2009/cuisine_fine).
Quelqu'un pourrait-il m'envoyer un code qui marche que je puisse l'analyser svp, je pense que mon tri est trop lent, mais je ne vois comment faire autrement de façon relativement simple... mon tri est actuellement en O(N²) (tri par insertion).
Merci d'avance, a bientôt !

Nan.

Edit: :)

Merci !
Une simple aide me suffirait :p

Je dis std::sort, mais je dis rien. \^\^

C'est déjà mieux comme demande "une simple aide". Moi je répondais "nan" pour le code tout fait.

N'écoute pas Equinoxe, et implémente des tris en O(N log N) toi-même. :)

1) Savoir implémenter un algo de tri efficace est toujours utile. Par exemple, quick sort.

2) Savoir comment s'appelle la fonction de tri dans ton langage préféré est indispensanble.

3) La fonction de tri de ton langage préféré sera toujours plus efficace que le tri codé à la main. ;)

Donc si je vous dis que j'code en C, vous me conseillez d'opter pour un langage qui possède une fonction de tri (gain de temps de codage et performance) ?
edit: et optionnellement d'apprendre à créer soi-même cet algorithme ?

Une fonction de tri existe déjà en C.

7.22.5.2 The qsort function
Synopsis
1
#include \<stdlib.h>
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
Description
2 The qsort function sorts an array of nmemb objects, the initial element of which is
pointed to by base. The size of each object is specified by size.
3 The contents of the array are sorted into ascending order according to a comparison
function pointed to by compar, which is called with two arguments that point to the
objects being compared. The function shall return an integer less than, equal to, or
greater than zero if the first argument is considered to be respectively less than, equal to,
or greater than the second.
4 If two elements compare as equal, their order in the resulting sorted array is unspecified.
Returns
5 The qsort function returns no value.

Après, la lib standard C n'a pas d'arbre, de liste, de table de hachage, de tas... C'est toujours bien de connaitre deux-trois langages (voire 5 ou 7). Et connaitre un algo de tri te sera utile même a des endroits ou aucun tri n'est requis, donc oui c'est mieux.

J'ai encore tellement de choses à apprendre ... Merci ;)

Bonjour,

Je n'aime pas lire :
"3) La fonction de tri de ton langage préféré sera toujours plus efficace que le tri codé à la main. ;)"

C'est totalement faux : a partir d'une certaine taille, trier un tableau de booleans se fait plus vite en les comptant et en recréant le tableau ensuite.

On observe la même chose pour un tableau d'entiers dans un interval donné (qu'on peut allouer en ram sans trop prendre de place)

Le tri comptage est en O(n), les fonctions de trie de la lib standard sont souvent en nlogn

En même temps le comptage à paniers c'est *le* cas particulier. Et quand on en arrive à ce niveau d'optimisation, en général on sait quand c'est nécessaire.

Sans parler du radix sort et du pancake[1] sort qui sont en O(n) !

[1] http://en.wikipedia.org/wiki/Pancake_sorting

Le radix sort est non pas en O(n) mais en O(nW), si j'en crois wikipédia, avec W quelque chose comme le logarithme du plus grand nombre. Et W n'est pas proportionnel à n, ce qui fait que le radix sort n'est pas de complexité linéaire ... Et peut potentiellement arriver à quelque chose d'horrible, si par exemple la suite à trier est définie comme étant les n premiers termes de la suite d'ackerman (liste[i] = A(i, i);).
Si on choisit le nombre de chiffres pris en compte comme étant fonction de n, de sorte à n'avoir qu'un nombre fixe de passes (avec par exemple les n/2 premiers chiffres pour avoir 2 passes), alors on se retrouve avec un autre problème : la complexité mémoire, qui passe cette fois-ci en O(W), toujours avec W ce logarithme potentiellement énorme.
Et si on veut optimiser la complexité mémoire en ne considérant que les nombres utiles, on se retrouve, selon la structure choisie, au mieux avec un algorithme en O(n log n), avec log n le temps d'accès à la structure de données.

Et le pancake sorting est totalement HS, pour le coup ! =p

En même temps, parler de "logarithme potentiellement énorme", à côté d'une fonction linéaire, c'est quand même chipoter pour chipoter.