quicksort.c

quicksort quicksort

		#include "quicksort.h"
		#include <stdlib.h>
		#include "fatal.h"

		#define MinPQSize (10)
		#define Cutoff ( 3 )

		struct SortStruct
		{
			int Capacity;
			int Size;
			ElementType *Elements;
		};

		int count = 0;

		Sort
        Initialize( int MaxElements )
        {
            Sort S;

            if( MaxElements < MinPQSize )
                Error( "Priority queue size is too small" );
            S = malloc( sizeof( struct SortStruct ) );
            if( S ==NULL )
                FatalError( "Out of space!!!" );

            /* Allocate the array plus one extra for sentinel */
            S->Elements = malloc( ( MaxElements )
                                    * sizeof( ElementType ) );
            if( S->Elements == NULL )
                FatalError( "Out of space!!!" );

            S->Capacity = MaxElements;
            S->Size = 0;

            return S;
        }

		void
        MakeEmpty( Sort S )
        {
            S->Size = 0;
        }

		void
        Insert( ElementType X, Sort S )
        {
            if( IsFull( S ) )
            {
                Error( "Priority queue is full" );
                return;
            }
			S->Elements[ S->Size++ ] = X;   
        }

		int
        IsFull( Sort S )
        {
            return S->Size == S->Capacity;
        }

		void
        Destroy( Sort S )
        {
            free( S->Elements );
            free( S );
        }

		void
        InsertionSort( ElementType A[ ], int N )
        {
            int j, P;
            ElementType Tmp;

            for( P = 1; P < N; P++ )
            {
                Tmp = A[ P ];

                for( j = P; j > 0 && A[ j - 1 ] > Tmp; j-- )
                {
					count++;
                    A[ j ] = A[ j - 1 ];
				}
				if( j > 0 )
				{
					count++;
				}
                A[ j ] = Tmp;
            }
        }

		void
        Swap( ElementType *Lhs, ElementType *Rhs )
        {
            ElementType Tmp = *Lhs;
            *Lhs = *Rhs;
            *Rhs = Tmp;
        }

		ElementType
        Median3( ElementType A[ ], int Left, int Right )
        {
            int Center = ( Left + Right ) / 2;

            if( A[ Left ] > A[ Center ] )
			{
				count++;
                Swap( &A[ Left ], &A[ Center ] );
			}
            if( A[ Left ] > A[ Right ] )
			{
				count++;
                Swap( &A[ Left ], &A[ Right ] );
			}
            if( A[ Center ] > A[ Right ] )
			{
				count++;
                Swap( &A[ Center ], &A[ Right ] );
			}

            /* Invariant: A[ Left ] <= A[ Center ] <= A[ Right ] */

            Swap( &A[ Center ], &A[ Right - 1 ] );  /* Hide pivot */
            return A[ Right - 1 ];                /* Return pivot */
        }

		void
        Qsort( ElementType A[ ], int Left, int Right )
        {
            int i, j;
            ElementType Pivot;
        
            if( Left + Cutoff <= Right )
            {
                Pivot = Median3( A, Left, Right );
                i = Left; j = Right - 1;
                for( ; ; )
                {
                    while( A[ ++i ] < Pivot )
						count++;
                    while( A[ --j ] > Pivot )
						count++;
					if( i < j )
                        Swap( &A[ i ], &A[ j ] );
                    else
                        break;
                }
                Swap( &A[ i ], &A[ Right - 1 ] );  /* Restore pivot */

                Qsort( A, Left, i - 1 );
                Qsort( A, i + 1, Right );
            }
            else  /* Do an insertion sort on the subarray */
                InsertionSort( A + Left, Right - Left + 1 );
        }

		void
        Quicksort( Sort S, int N )
        {
            Qsort( S->Elements, 0, N - 1 );
			printf("%d\n", count);
        }