Bonjour a tous , 

Je veux trier un " K-Sorted Array" c'est a dire que chaque emplacement est dans K place de son emplacement dans le tableau trie .

Je cherche a avoir une complexité minime ... J'ai pense a une sorte de Merge sort vu que on peut diviser sur pleins de petite partitions qui eut seront a un bon emplacement mais il existe un probleme pour K=1 et je suis pas sur de mon raisonnement meme si mon code marche sur des examples de tableau ( donc coup de chance ou bon code? )

void merge(int a[], int na, int b[], int nb, int c[]) {
    int ia, ib, ic;
    for(ia = ib = ic = 0; (ia < na) && (ib < nb); ic++)
    {
        if(a[ia] < b[ib]) {
            c[ic] = a[ia];
            ia++;
        }
        else {
            c[ic] = b[ib];
            ib++;
        }
    }
    for(;ia < na; ia++, ic++) c[ic] = a[ia];
    for(;ib < nb; ib++, ic++) c[ic] = b[ib];
}

void internal_msort(int a[], int n, int helper_array[],int k)
{
    int left = ( n/(k) ) ,right = (n - left);
    if (n < k)
        return;
    internal_msort(a, left, helper_array,k);
    internal_msort(a + left, right, helper_array,k);
    merge(a, left, a + left, right, helper_array);
    memcpy(a, helper_array, n * sizeof(int));
}

void merge_sort(int a[], int n,int k)
{
    int *tmp_array = malloc(sizeof(int) * n);
    internal_msort(a, n, tmp_array,k);
    free(tmp_array);
}

Je sais que le cas . K = 1 me renvoie une boucle infini vu que right sera egal a 0 mais je sais pas comment y remedier .

Merci de votre temps

Salut,

Le merge sort est un algorithme très répendu, tu peux trouver des exemples partout pour comparer avec ton exemple, et comprendre ce qu'il ne vas pas.

https://www.tutorialspoint.com/data_structures_algorithms/merge_sort_program_in_c.htm

Ensuite, tu cherches à avoir la meilleure complexité, et effectivement merge sort est un algo de tri en O(n log(n)) en moyenne, mais le quick sort l'est aussi. Ca peut être un bon exercice de recoder ça, mais si le but est vraiment d'avoir de la rapidité, tourne toi vers des implantations existantes (fonction qsort en C par exemple).

Enfin, tu parle d'un cas spécifique (K-sorted array), mais il me semble que ton algo reste en O(n log(n)), donc peut être qu'il y a de meilleures solutions.

Je n'ai pas fait de recherches sur les K-sorted array, et peut-être que je me trompes sur la complexité de ton algo, mais dans un post où tu parles de meilleur temps, il faudrait que tu spécifie un peu plus ton travail, parce que ça prend du temps à quelqu'un d'aller faire des recherches juste pour comprendre ton algo

EDIT: ton algo a pour but d'être plus rapide pour K petit ? En moyenne, ton k est petit ? (je viens de voir ton titre)

-
Edité par Smiley32 16 juin 2019 à 14:06:46

pour un k sorted array, "le shellSort" semble bien s'y prêter sans être trop difficile à implémenter.

EDIT :
chercher une complexité minime c'est super :) 
Mais il faut tester en pratique la performance en fonction de n (un bon entrainement).

-
Edité par neuneutrinos 16 juin 2019 à 20:37:52

Oui le "n" est effectivement minime par rapport a la taille de l'array. Je cherche a utiliser des tris vu en cours (QuickSort ou MergeSort) cependant QuickSort est rapide en moyenne mais complexité de O(n^2) dans le pire des cas et donc invalide dans ce calcul de complexité .

Oui, alors de là à dire "invalide dans ce calcul de complexité", il faut tout de même faire attention. Le quick sort utilise moins d'espace que le merge sort (tri interne), et est efficace sur des petits tableaux. 

Le merge sort est plus générique, et est aussi efficace quelle que soit la taille du tableau.

Donc tu dois plutôt choisir en fonction de ton utilisation précise.

Et tu dis 'le "n" est [...] minime par rapport a la taille de l'array'. Mais n est la taille du tableau. Et en règle générale, quand on parle de complexité de tri, le n fait référence à la taille du tableau. Que veux-tu dire par minime ?

Comme le dit @neuneutrinos, c'est super de chercher une complexité minime, mais la complexité n'est pas le seul point important : la mémoire peut être également un soucis (même si généralement non).  Regarde également l'algo que @neuneutrinos t'as cité, ça pourrait t'aider.

euhhh je faisait reference au "k" excusez moi . J'ai compris ce que vous avez dit sur la complexité a ne pas foncer tete baisser vers des calculs dénué de sens mais je voulais savoir si le MergeSort était applicable dans ce cas la et si oui quel a ete l'erreur que jai faite ( pour le cas K = 1 )

Eh bien c'est simple, tu appelles ton 'internal_sort' avec k égal à 1. D'où left=n et right=0

Et tu rapelles ton 'internal_sort', avec k égal à 1. Et ainsi de suite. Tu n'as pas de condition d'arrêt.

Le merge sort est toujours applicable, mais n'est pas forcément la solution la plus adaptée, c'est tout.

Peut être que, si chaque élément n'est qu'à la distance k de sa destination, en faisant k passes de tri à bulles ça le fait ?