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...