1 /*
 2    Copyright (C) 2003 Alessandro Bugatti (alessandro.bugatti@istruzione.it)
 3  
 4    This program is free software; you can redistribute it and/or
 5    modify it under the terms of the GNU General Public License
 6    as published by the Free Software Foundation; either version 2
 7    of the License, or (at your option) any later version.
 8  
 9    This program is distributed in the hope that it will be useful,
10    but WITHOUT ANY WARRANTY; without even the implied warranty of
11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12    GNU General Public License for more details.
13  
14    You should have received a copy of the GNU General Public License
15    along with this program; if not, write to the Free Software
16    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
17  */
18  
19  /*! \file
20   *  \brief Algoritmo di ordinamento Quick Sort che ordina
21   *  un vettore di N stringhe, spostando fisicamente le stringhe
22   *  \author Alessandro Bugatti
23   *
24   *  \version 0.1
25   *  \date  Creazione  04/04/2003
26   *  \date  Ultima modifica 22/09/2014
27   */
28  
29  #include <stdio.h>
30  #include <string.h>
31  
32  void exchange(int *i1,int *i2)
33  {
34     int temp;
35     temp = *i1;
36     *i1 = *i2;
37     *i2 = temp;
38  }
39  
40  int partition(int indici[], char (*str)[20],int l, int r)
41  {
42     int i=l-1,j=r;
43     char *v=str[indici[r]];
44     for(;;)
45        {
46           while (strcmp(str[indici[++i]],v)< 0);
47           while (strcmp(v,str[indici[--j]])< 0) if (j==i) break;
48           if (i>=j) break;
49           exchange(&indici[i],&indici[j]);
50        }
51     exchange(&indici[i],&indici[r]);
52     return i;
53  }
54  
55  void quicksort(int indici[], char (*stringa)[20],int l, int r)
56  {
57     int i;
58     if (r<=l) return;
59     i = partition(indici, stringa,l,r);
60     quicksort(indici, stringa,l,i-1);
61     quicksort(indici, stringa,i+1,r);
62  }
63  
64  int main(int argc, char *argv[])
65  {
66    char str[10][20]={"Vassi", "Pino", "Roni","Aroldo","Tieri","Melli",
67                       "Zabruga","Benni", "Pini","Lollo"};
68    int ind_str[10];
69    //Iniziliazziamo i puntatori per farli puntare alle stringhe
70    for (int i = 0; i < 10; i++)
71      ind_str[i] = i;
72    quicksort(ind_str,str,0,9);
73    for (int i=0;i<10;i++)
74      printf("%s \n",str[ind_str[i]]);
75    return 0;
76  }