Algoritmi lezione 16 - Shell Sort

#include <iostream>
#include <chrono>
#include <ctime>
#include <random>

using namespace std;
#include "../../min_max/utility_vettori.h"


using namespace std;

//i due array contengono gli stessi elementi?
//ATTENZIONE: modifica il secondo!
bool stessi_elementi(unsigned long v1[], unsigned long v2[], int QUANTI_ELEMENTI)
{

  int rimasti = QUANTI_ELEMENTI;
  for (int i=0; i<QUANTI_ELEMENTI; i++)
  {
      bool trovato = false;

      for (int j=0; j<rimasti; j++)

      //trovato una corripondenza la sposto
      //a fine array per non riconsiderarla
      //al passo successivo gestendo
      //le occorrenze multiple di un certo valore
      if (v1[i] == v2[j]) {
        trovato=true;
        swap(v2[j], v2[rimasti-1]);
        rimasti --;
        break;
      }

      if (!trovato) return false;
  }
  return true;
}

void insertion_sort_interi(unsigned long v[], int numero_elementi)
{
  //porta il minimo in prima posizione a fare da sentinella
  int pos_min = 0;
  for (int i=1; i<numero_elementi; i++)
    if (v[i] < v[pos_min]) pos_min = i;

  swap(v[0], v[pos_min]);

  for (int i = 1; i < numero_elementi; i++) {

    int elemento_corrente = v[i];

    int j = i - 1;
    while( v[j] > elemento_corrente)
    {
      v[j + 1] = v[j];
      j--;
    }
    v[j + 1] = elemento_corrente;
  }
}

void shell_sort_interi(unsigned long v[], int numero_elementi)
{
  int distanza = numero_elementi/2; //'gap'

  while (distanza>0)
  {
    for (int i = distanza; i < numero_elementi; i++) {

      int elemento_corrente = v[i];

      int j = i;
      while( j>=distanza && v[j - distanza] > elemento_corrente)
      {
        v[j] = v[j - distanza];
        j -= distanza;
      }
      v[j] = elemento_corrente;
    }

    distanza = distanza / 2;
  }
}




const int QUANTI_ELEMENTI = 100000;
const int LUNGHEZZA = 1000;
unsigned long v[QUANTI_ELEMENTI];
unsigned long vcopia[QUANTI_ELEMENTI];


int main()
{
  carica_vettore_interi(v, QUANTI_ELEMENTI);

  //stampa_vettore_interi(v, QUANTI_ELEMENTI);
  //cout << string(40, '*') << endl;

  //duplico vettore per controlli finali
  for (int i=0; i<QUANTI_ELEMENTI; i++) vcopia[i] = v[i];

  Cronometro(Stato::START);

  //lo ordino crescente
  shell_sort_interi(v, QUANTI_ELEMENTI);

  cout << "Tempo impiegato: " << Cronometro(Stato::STOP) << endl;
  if (verifica_ordine_crescente(v, QUANTI_ELEMENTI)) cout <<"IN ORDINE!\n";

  //sono gli stessi elementi?
  if (!stessi_elementi(v, vcopia, QUANTI_ELEMENTI))
    cout << "Array difformi!!\n";
  else
    cout << "L'array ordinato contiene gli stessi elementi di quello iniziale\n";

  //stampa_vettore_interi(v, QUANTI_ELEMENTI);


    return 0;
}