/*==============================================================
 * Sortieren eines Feldes mit dem
 * QUICKSORT Algorithmus
 *============================================================*/

#include <stdio.h>


/************************************************************** 
 * der zu  durchsuchende Array 
 **************************************************************/

#define ARRAY_LEN 20
#define ALL_IDENTICAL -1

typedef struct {
    int key; /* Schluessel */
    char name[10]; /* Daten, 1.Feld */
    int  gehalt; /* Daten, 2. Feld */
} my_array_t;


/* Fuer das Beispiel wird der Array konstant belegt */
my_array_t a[ARRAY_LEN] =
{ { 33, "Mueller", 2400 },
  {2, "Zorn", 2800 },
  {77, "Fritz", 1400 },
  {999, "Freund", 2200 },
  {3, "Zahlten", 2100 },
  {4, "Baggins", 2111 },
  {33, "Harald", 2444 },
  {34, "Harald1", 2444 },
  {31, "Harald2", 2444 },
  {31, "Harald3", 2444 },
  {39, "Harald4", 2444 },
  {33, "Harald5", 2444 },
  {34, "Harald6", 2444 },
  {35, "Harald7", 2444 },
  {44, "Harald8", 2444 },
  {37, "Harald9", 2444 },
  {38, "Harald10", 2444 },
  {18, "Harald10", 2444 },
  {22, "Harald10", 2444 },
  {21, "Harald10", 2444 }
};



/***********************************************************************
 * Hilfsfunktion zum Vertauschen zweier Array-Elemente
 ***********************************************************************/

void swap(int i, int j) {

    my_array_t temp;

    temp = a[i];
    a[i] = a[j];
    a[j] = temp;

}


/***********************************************************************
 * Suchen des Pivot-Elementes im Array-Index-Bereich ug..og
 ***********************************************************************/

int findpivot(int ug, int og) {

    int firstkey;
    int iCnt;

    firstkey = a[ug].key;

    for (iCnt = ug + 1; iCnt <= og; iCnt++) {
	if ( a[iCnt].key > firstkey ) 
	    return iCnt;
        else if ( a[iCnt].key < firstkey )
            return ug;
    }

    return ALL_IDENTICAL;

}



/***********************************************************************
 * Partitionierung des Arrays: Ziel ist, dass links vom Pivot-Element
 * nur Schluessel liegen, die KLEINER als der des Pivot-Elements sind
 * und rechts vom Pivot-Element nur Schluessel, die >= dem Schluessel
 * des Pivot-Elements sind.
 * pivotkey ist der Schluesselwert des Pivot-Elements
 * Rueckgabewert ist der Index des Array-Abschnitts, der rechts vom
 * Pivot-Element liegt.
 ***********************************************************************/

int partition( int ug, int og, int pivotkey ) {

    int li, re;

    li = ug;
    re = og;

    do {

	swap(li,re);

	while (a[li].key < pivotkey) li++;

	while (a[re].key >= pivotkey) re--;

    } while ( li <= re );

    return li;

}


/***********************************************************************
 * Hauptprozedur des Quicksort-Algorithmus
 ***********************************************************************/

void quicksort(int ug, int og) {

    int pivotkey;
    int pivotindex;
    int iCnt;

    pivotindex = findpivot(ug,og);

    if ( pivotindex != ALL_IDENTICAL ) {

	pivotkey = a[pivotindex].key;

        /* partition() liefert einen Index zurueck,
           so dass LINKS von diesem Index ALLE Schluesselwerte
           KLEINER als pivotkey sind und ALLE Schluesselwerte
           RECHTS von diesem Index >= pivotkey sind.

           Damit braucht man die Schluessel des
           linken Array-Teils nicht mehr mit den Schluesseln
           des rechten Array-Teils zu vergleichen.
	*/ 
           
	iCnt = partition(ug,og,pivotkey);

        /* Sortiere den linken Array-Teil */ 
	quicksort(ug,iCnt-1);
        /* sortiere den rechten Array-Teil */ 
	quicksort(iCnt,og);

    }

}

/***********************************************************************
 * Hauptprogramm
 ***********************************************************************/

int main() {

    int iCnt;

    quicksort(0,ARRAY_LEN-1);

    for (iCnt = 0; iCnt < ARRAY_LEN; iCnt++)
	printf("No. %d Key %d Name %s Gehalt %d\n",
	       iCnt,a[iCnt].key,a[iCnt].name,a[iCnt].gehalt);

}