Thread: Quick Sort Help

  1. #1
    Registered User
    Join Date
    Apr 2002
    Posts
    23

    Quick Sort Help

    Hi, i'm having trouble running the quick sort function...here is my code...thanks

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define arySize 100
    #define MIN_SIZE 16
    #define FLUSH while (getchar () != '\n')
    
    void shellSort (int list [], int last, int *compare, int *move);
    
    void quickSort (int sortData [], int left, int right);
    void quickInsertion (int sortData[], int first, int last);
    void medianLeft (int sortData[], int left, int right);
    
    void printData (int list[], int compare, int move);
    
    void printMenu (void);
    char getOption (void);
    void processOption (void);
    
    void shellManager (void);
    void quickManager (void);
    
    int main (void)
    {
    
    /* Statments */	
    	printMenu ();
    	processOption ();
    	
    	return 0;
    }
    
    /*--------------------------printMenu-----------------------------*/
    void printMenu (void)
    {
    
    /* Statements */
        printf("\t\tMENU\n\n");
    	printf("\tS: Perform Shell sort\n");
        printf("\tQ: Perform Quick sort\n");
        printf("\tM: Menu\n");
        printf("\tE: Exit\n");
    
        return;
    } /* printMenu */
    
    /*--------------------------getOption-----------------------------*/
    char getOption (void)
    {
    
    /* Local Definitions */
        char option;
    
    /* Statements */
        printf("\nPlease select an option: ");
        scanf("%c", &option);
        FLUSH;
        
        option = toupper (option);
        while(strchr("SQME", option) == NULL)
        {
            printf("\..........* Invalid option! ***\n");
            printf("Enter one of the following letters: S,Q,M,E: " );
            scanf  ("%c", &option);
            FLUSH;
    	    option = toupper (option);
        }
        
        return option;
    } /* getOption */
    void processOption (void)
    {
    
    /* Local Definitions */
    	char option;
    
    /* Statements */    
        do
        {
        option = getOption ();
        switch (option)
            {
             case 'S': shellManager();
                       break;
             case 'Q': quickManager ();
                       break;
    		 case 'M': printMenu ();
    				   break;
             case 'E': printf("Thanks for using this program!\n");
                       break;
             default : break;
             
            } /* switch*/
        } while (option != 'E');
       
        return;
    } /* processOption */
    void shellSort (int list [], int last, int *compare, int *move)
    {
    
    /* Local Definitions */
    	int hold;
    	int incre;
    	int curr;
    	int walker;
    
    /* Statements */	
    	incre = last / 2;
    	while (incre != 0)
    	{
    		for (curr = incre; ((*compare)++, curr <= last); curr++)
    		{
    			hold = list [curr];
    			walker = curr - incre;
    			while (walker >= 0 && ((*compare)++, hold < list[walker]))
    			{
    				/* Move larger element up in list */
    				list [walker + incre] = list [walker]; // move
    				(*move)++;
    				/* Fall back one partition */
    				walker = ( walker - incre );
    			} /* while */
    			/* Insert hold in proper relative position */
    			list [walker + incre] = hold; // move
    			(*move)++;
    		} /* for walk */
    		/* End of pass--calculate next increment */
    		incre = incre / 2;
    	} /* while */
    	return;
    }
    
    void quickSort (int sortData[], int left, int right)
    {
    
    /* Local Definitions */
    	int sortLeft;
    	int sortRight;
    	int pivot;
    	int hold;
    
    /* Statements */
    	if ((right - left) > MIN_SIZE)
    		/* quick sort */
    	{
    		medianLeft (sortData, left, right);
    		pivot = sortData [left];
    		sortLeft = left + 1;
    		sortRight = right;
    		while (sortLeft <= sortRight)
    			/* Find key on left that belongs on right */
    		{
    			while (sortData [sortLeft] < pivot)
    				sortLeft = sortLeft + 1;
    			/* Find key on right that belongs on left */
    			while (sortData [sortRight] >= pivot)
    				sortRight = sortRight - 1;
    			if (sortLeft <= sortRight)
    			{
    				hold = sortData [sortLeft];
    				sortData[sortLeft] = sortData [sortRight];
    				sortData[sortRight] = hold;
    				sortLeft = sortLeft + 1;
    				sortRight = sortRight - 1;
    			} 
    		}
    		/* Prepare for next phase */
    		sortData [left] = sortData [sortLeft - 1];
    		sortData [sortLeft - 1] = pivot;
    		if (left < sortRight)
    			quickSort (sortData, left, sortRight - 1);
    		if (sortLeft < right)
    			quickSort (sortData, sortLeft, right);
    	}
    	else
    		quickInsertion (sortData, left, right);
    
    }
    
    void quickInsertion (int sortData[], int first, int last)
    {
    
    /* Local Definitions */
    	int current;
    	int hold;
    	int walker;
    
    /* Statements */
    	for (current = first + 1; current <= last; current++)
    	{
    		hold = sortData[current];
    		walker = current - 1;
    		while (walker >= first && hold < sortData[walker]);
    		{
    			sortData[walker + 1] = sortData[walker];
    			walker = walker - 1;
    		}
    		sortData[walker + 1] = hold;
    	}
    	return;
    }
    
    void medianLeft (int sortData[], int left, int right)
    {
    
    /* Local Definitions */
    	int mid;
    	int hold;
    
    /* Statements */
    	mid = (left + right) / 2;
    	if (sortData[left] > sortData[mid])
    	{
    		hold = sortData[left];
    		sortData[left] = sortData[mid];
    		sortData[mid] = hold;
    	}
    	if (sortData[left] > sortData[right])
    	{
    		hold = sortData[left];
    		sortData[left] = sortData[right];
    		sortData[right] = hold;
    	}
    	if (sortData[mid] > sortData[right])
    	{
    		hold = sortData[mid];
    		sortData[left] = sortData[right];
    		sortData[right] = hold;
    	}
    	/* Median is in middle. Exhange with left */
    	hold = sortData[left];
    	sortData[left] = sortData[mid];
    	sortData[mid] = hold;
    
    	return;
    }
    
    void printData (int list[], int compare, int move)
    {
    
    /* Local Definitions */
    	int i = 0;
    	int lineCount = 0;
    
    /* Statements */
    	while (i<arySize)
    	{
    		if (lineCount < 10)
    			lineCount++;
    		else
    		{
    			printf("\n");
    			lineCount = 1;
    		}
    		printf("%6d ", list[i]);
    		i++;
    	}
    	
    	printf("\nCompares: %d  Moves: %d\n", compare, move);
    	
    }
    
    void shellManager (void)
    {
    
    /* Local Definitions */
    	int list[arySize];
    	int i;
    	int compare = 0;
    	int move = 0;
    	
    /* Statements */
    	srand (31);
    
    	for (i=0; i<arySize; i++)
    		list[i] = rand ();
    
    	shellSort(list, arySize - 1, &compare, &move);
    
    	printData(list, compare, move);
    
    	return;
    
    }
    
    void quickManager (void)
    {
    
    /* Local Definitions */
    	int sortData[arySize];
    	int left; /* first element of the array */
    	int right; /*  last element of the array */
    	int i;
    
    /* Statements */
    	srand (31);
    
    
    
    	for (i=0; i<arySize; i++)
    		sortData[i] = rand ();
    
    	left = 0;
    	right = arySize - 1;
    
    	quickSort (sortData, left, right);
    
    	return;
    }

  2. #2
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490
    What are your errors? Does it compile? What's your expected output? What's the output now?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recursive quick sort - stack overflow
    By Micko in forum C Programming
    Replies: 9
    Last Post: 01-01-2005, 05:51 PM
  2. Help On A Quick Sort Program
    By nick4 in forum C++ Programming
    Replies: 11
    Last Post: 12-06-2004, 10:51 AM
  3. Quick sort VS Merge Sort
    By sachitha in forum Tech Board
    Replies: 7
    Last Post: 09-03-2004, 11:57 PM
  4. Questions on basic Quick Sort
    By Weng in forum C++ Programming
    Replies: 4
    Last Post: 12-16-2003, 10:06 AM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 08:05 PM