Problema selection sort array C++

di il
4 risposte

Problema selection sort array C++

Salve a tutti, dovrei svolgere il seguente esercizio sul selection sort : Si supponga che l'algoritmo venga eseguito su di un array di n elementi. Alla i-esima iterazione dell'algoritmo Selection-sort l'elemento di posizione k dell'array viene selezionato e viene sostituito con l'elemento di posizione i. Si suppone quindi che le iterazioni inizino con un valore i pari a 0 e terminino con il valore i pari a n-1. Si supponga inoltre che, nella selezione dell'elemento minimo, l'algoritmo scelga sempre quello più a sinistra qualora fossero presenti più elementi con valore minimo.
Si scriva un programma di C++ che sia in grado di calcolare la somma delle distanza (k-i), per tutte le iterazioni dell'algoritmo, ovvero per i che va da 0 a n-1.

l'esercizio fornisce un file di input con 100 righe ed ogni riga ha tutti i numeri da inserire nell'array e da ordinare.

l'algoritmo scritto da me funziona correttamente ma non riesco a calcolare sta benedetta distanza, ci sto dietro da un pomeriggio..
vi lascio il codice scritto da me :

#include <iostream>
#include <fstream>

#define INPUT_FILE "input.txt"
#define OUTPUT_FILE "output.txt"

using namespace std;

fstream infile, outfile;

void SelectionSort(int a[], int N)
{
    int i, k, min, temp;
    int somma = 0;
    int spostamenti = 0;
    for(i=0;i<N-1;i++)
    {
        
	    min=i;
        for(k=i+1;k<N;k++) {
           
            if (a[k]<a[min])
        	     min = k;
        }
        spostamenti = k - min;
        somma = spostamenti;
        temp=a[min];
        a[min]=a[i];
        a[i]=temp;
        
        
    }
    outfile << somma << endl;
   
}

int main () 
{
    bool end = false;
    int N;
    int y;
    infile.open(INPUT_FILE, fstream::in);
    outfile.open(OUTPUT_FILE, fstream::out);

    
    if (!infile.is_open()) 
    {
        cerr << "error opening file " << INPUT_FILE <<
                endl;
        return -1;
    }
    
    if (!outfile.is_open()) 
    {
        cerr << "error opening file " << OUTPUT_FILE <<
                endl;
        return -1;
    }
    
    while (!end)
    {
        infile >> N;
        int vett[N];
        
        if (infile.eof())
        {
            cout << "end of input, exit!" << endl;
            end = true;
        }
        else if (infile.fail())
        {
            cerr << "error reading N from file " << 
                    INPUT_FILE << endl;
            end = true;
        }
        else 
        {
            for (int i=0; i<N; i++) 
            {
                infile >> y;
                vett[i] = y;
            }
            
            SelectionSort(vett, N);
        }
            
    }
    
}
spero possiate aiutarmi perché proprio non riesco, l'ho scritto in tutti modi che ho pensato e comunque è sbagliato...

4 Risposte

  • Re: Problema selection sort array C++

    
            spostamenti = min - i;
            somma += spostamenti;
    
  • Re: Problema selection sort array C++

    Grazie mille, ora funziona perfettamente!
  • Re: Problema selection sort array C++

    Weierstrass ha scritto:


    
            spostamenti = min - i;
            somma += spostamenti;
    
    ciao, adesso ho un altro esercizio in cui mi sono bloccato, in sostanza devo creare una classe pila utilizzando i template e questa classe deve comprendere i prototipi delle funzioni di inserimento, estrazione e stampa.. l'esercizio fornisce anche qui un file di input di questo genere :
    bool 10 i1 i0 pop pop i1 i0 i0 i1 i1 i0
    char 10 ij ir pop it iq ir im ik it it
    int 10 i13 i17 i6 pop i15 i2 i9 pop pop i5
    in cui la prima stringa rappresenta il tipo di valore, l'intero rappresenta il numero di valori e seguono i valori.. ora il mio problema è nel capire come fare per far si che il programma riconosca il carattere "i" (che indica l'inserimento in pila) o la stringa pop (che indica l'estrazione dalla pila).. In sostanza il mi problema è: se creo un oggetto Pila<bool> p, i resta comunque un carattere e pop una stringa, come devo fare per far si che se il programma legge la i inserisca il valore concatenato, mentre se legge pop estragga l'ultimo valore inserito?

    Grazie anticipatamente!
  • Re: Problema selection sort array C++

    Apri un altro thread, spiega un po' meglio (almeno io non ho capito benissimo quello che devi fare) e posta il codice che hai già fatto
Devi accedere o registrarti per scrivere nel forum
4 risposte