Programmi C/C++ - prof.Claudio Maccherani

Programmi C / C++ - prof. Claudio Maccherani - Perugia - 2008
SORT (Insertion e Bubble) e Ricerca BINARIA o DICOTOMICA

 /* Sort (Insertion e Bubble) e Ricerca Binaria
   Dev-C++ - prof. Claudio Maccherani - Perugia - 2008/09 */

 #include <stdlib.h>
 #include <stdio.h>     
 #include <iostream.h>                             
 #include <windows.h> 
 #include <time.h>

 const int N = 51;
 int col=10,v[N],ov[N];

 int gotoxy(int r, int c) { // posiziona il cusore a riga 'r' e colonna 'c' 
   HANDLE Hout; CONSOLE_SCREEN_BUFFER_INFO ConsoleInfo; 
   Hout = GetStdHandle(STD_OUTPUT_HANDLE); 
   ConsoleInfo.dwCursorPosition.Y = r; ConsoleInfo.dwCursorPosition.X = c;     
   SetConsoleCursorPosition(Hout,ConsoleInfo.dwCursorPosition); }

 void visualizzazione() { // visualizzazione vettore --------------------------
     for (int i = 1; i < N; i++)
     cout << i << " - " << v[i] << "\n"; cout << "\n";
     system("pause"); return; }  

 void creazione() { // riempimento vettore con numri casuali ------------------
   system("cls"); printf("Riempimento casuale vettore\n\n");
   srand(time(0));
   for (int i = 1; i < N; i++) { v[i] = rand() %1000 + 1; ov[i] = v[i]; } 
   visualizzazione(); return; }  
   
 void Insertion_Sort() { // ordinamento per selezione (Insertion)
   system("cls"); printf("Insertion Sort, Ordinamento per selezione\n\n");
   for (int i = 0; i <= N; i++) v[i] = ov[i];
   int appo,i,j;
   for (i = 1; i < N - 1; i++ ) 
        for (j = i + 1; j < N; j++ )
             if (v[i] > v[j]) { appo = v[i]; v[i] = v[j]; v[j] = appo; }
   visualizzazione(); return; }  

 void Bubble_Sort() { // ordinamento per scambio (Bubble)
   system("cls"); printf("Buble Sort, Ordinamento per scambio\n\n");
   for (int i = 0; i <= N; i++) v[i] = ov[i];
   bool scambio; int appo;
   do  {
       scambio = false; 
       for (int i = 1; i < N - 1; i++ )
             if (v[i] > v[i+1]) { appo = v[i]; v[i] = v[i+1];
                                  v[i+1] = appo; scambio = true; }
       }      
   while (scambio == true);
   visualizzazione(); return; }  
   
 void ordinamenti() { // ordinamenti ------------------------------------------
   int scelta;             
   do {
      system("cls"); scelta = -1;
      gotoxy( 1,col); printf("Ordinamenti (Sort)"); 
      gotoxy( 4,col); printf("1 - Insertion Sort "); 
      gotoxy( 6,col); printf("2 - Bubble    Sort "); 
      gotoxy( 8,col); printf("    scegli (0=fine) ");
      cin>>scelta; 
      switch (scelta) {
           case 1: { Insertion_Sort(); break; } // insertion sort
           case 2: { Bubble_Sort();    break; } // bubble sort
           }
      }     
   while (scelta!= 0);
   return;}

 int ricbin(int x,int i1,int i2) { // ricerca binaria (ricorsiva) 
   int j;
   if (i1 > i2) return 0;
   j = (i1+i2)/2;
   if (v[j] == x) return j;
   if (x < v[j])
       ricbin(x,i1,j-1);
   else
      ricbin(x,j+1,i2);
   }        
   
 void ricerca() { // ricerca di un elemento -----------------------------------
   int x,pos;
   system("cls"); printf("Ricerca Binaria (Search)\n\n");
   cout<<"Elemento da cercare: "; cin>>x;
   pos = ricbin(x,1,N-1);
   if (pos == 0) cout << x << " non esiste";
   else cout << x << " e' in posizione " << pos;
   cout << "\n"; system("pause"); 
   return;}   

 void main() { // programma principale ----------------------------------------
   int scelta;             
   do {
      system("cls"); scelta = -1;
      gotoxy( 1,col); printf("Ordinamenti (Sort) e Ricerche (Search) <ClaMa>"); 
      gotoxy( 4,col); printf("1 - Riempimento Vettore "); 
      gotoxy( 6,col); printf("2 - Ordinamenti o Sort  "); 
      gotoxy( 8,col); printf("3 - Ricerca Binaria "); 
      gotoxy(10,col); printf("4 - Visualizzazione "); 
      gotoxy(12,col); printf("    scegli (0=fine) ");
      cin>>scelta; 
      switch (scelta) {
           case 1: { creazione();       break; } 
           case 2: { ordinamenti();     break; }
           case 3: { ricerca();         break; } 
           case 4: { visualizzazione(); break; } }
      }     
   while (scelta!= 0); }