Ordinamento di una matrice quando i valori vengono diminuiti da ogni scambio [chiuso]

Non credo che l'applicazione di un algoritmo di ordinamento esistente possa essere di grande aiuto. Nel tuo esempio, credo che il numero minimo di scambi sia 2:

2 (4) (1) 3 5 -> 2 0 3 3 5
(2) (0) 3 3 5 -> -1 1 3 3 5

Questo accade per adattarsi al profilo di un bubble sort, ma quell'algoritmo impiega 7 passaggi per risolvere "5 4 3 2 1", che un ordinamento di inserimento può gestire in 2 passaggi:

(5) 4 3 2 (1) -> 0 4 3 2 4
0 (4) 3 (2) 4 -> 0 1 3 3 4

Esistono anche situazioni in cui è possibile trovare più soluzioni distinte per lo stesso problema:

2 4 1 5 3
2 4 1 2 4
2 1 1 3 4
0 1 1 3 4

o

2 4 1 5 3
2 4 1 3 3
2 0 3 3 3
-1 1 3 3 3

Nota che l'attività è di ottimizzare il numero di scambi , non il numero di confronti. Per l'ordinamento standard, dovrebbe essere ovvio che il semplice "sort sort" non ha bisogno di più di n-1 swaps, quindi suppongo che questo problema modificato non richieda più swap in generale.

Ecco un primo tentativo:

• Passa attraverso l'array fino a trovare un numero inferiore a quello precedente (diciamo all'indice i). Se non ce n'è, la matrice è ordinata e puoi fermarti
• trova l'elemento più piccolo nel sottoarray a [i], ..., a [n], diciamo a [j]
• scambia un [j] con il primo elemento da un [1], ..., un [i-1] che è più grande di un [j] (diciamo a [k]. Poiché un [k] deve essere maggiore di un [k-1] (o k = 1), lo swapping non distruggerà l'ordine esistente di un [1], ..., un [i-1]. Si noti che ci deve essere un tale elemento, poiché [k] > a [i] > = a [j] per ogni k
• ripeti questi passaggi fino a ordinare l'array

Ammetto, non sono sicuro che questo produrrà sempre il numero minimo di swap, continuando a cercare una prova (o un controesempio). Ma facciamo alcuni esempi:

5 4 3 2 1    -> 1 is the smallest beyond 5: swap with 5
0 4 3 2 4    -> 2 is the smallest beyond 4: swap with 4
0 1 3 3 4

o il tuo esempio originale:

2 4 1 3 5  ->  1 is the smallest beyond 4: swap with 2
0 4 1 3 5  ->  1 is the smallest beyond 4: swap with 4
0 0 3 3 5

Se qualcuno trova un controesempio, dimostrando che questo algoritmo non è ottimale, non esitare a presentarlo.

Ciao Dopo aver pensato un po 'ho trovato questa soluzione e ora mi sento come se stessi evitando un concetto molto semplice. SO implemento l'ordinamento tramite merger sort, che fondamentalmente divide e ordina e unisce l'array. abbiamo detrazione fiscale per lo scambio di due valori ma non per il confronto.

quindi ho usato un temp di array alternativo per unire i valori e quindi copiare il valore dello stesso nell'array originale il mio codice C ++ è qualcosa del tipo:

#include<iostream>

using namespace std;

void merge(int a[],int temp[],int left,int mid,int right);

void mergesort(int a[],int temp[],int low,int high)
{
    int mid;
    if(low < high ){

        mid=(int)(high+low)/2;
        mergesort(a,temp,low,mid);
        mergesort(a,temp,mid+1,high);
        merge(a,temp,low,mid+1,high);
    }
}

void merge(int a[],int temp[],int left,int mid,int right)
{
    int i,left_end,size,temp_pos;
    left_end=mid-1;
    size=right-left+1;
    temp_pos=left;
    while((left <= left_end) && (mid<=right)){
        if(a[left]<=a[mid]){
            temp[temp_pos]=a[left];
            temp_pos=temp_pos+1;
            left=left+1;
        }
        else{
            temp[temp_pos]=a[mid];
            mid=mid+1;
            temp_pos=temp_pos+1;
        }
    }

    while(left<=left_end)
    {
        temp[temp_pos]=a[left];
        left=left+1;
        temp_pos=temp_pos+1;
    }

    while(mid<=right)
    {
        temp[temp_pos]=a[mid];
        mid=mid+1;
        temp_pos=temp_pos+1;
    }

    for(int i=0;i<=size;i++){
        a[right]=temp[right];
        right=right-1;
    }
}

int main(){
    int a[]={5,4,9,8,7,1,2,0,3,6};
    int temp[10];
    mergesort(a,temp,0,9);
    for(int i=0;i<=9;i++)
        cout<<a[i];
    return 0;
}

Qualsiasi suggerimento riguardante lo stesso è apprezzato mi piacerebbe conoscere il feedback sul mio approccio.