Thread: How to optimize quicksort with selectionsort

  1. #1
    Registered User
    Join Date
    Apr 2017
    Posts
    5

    How to optimize quicksort with selectionsort

    I need to modify qsort function.When array length(int n) is,for ex. 200, I need to use selectionsort instead of quicksort.Here is my quicksort implementation.
    Code:
    void quicksort(int *array, int n) {
        int pi;
        if (n < 2)
            return;
        pi = partition(array, n);
        quicksort(array, pi);
        quicksort(array + pi + 1, n - pi - 1);
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,064
    So adding an if ( n < 200 ) test is too much for you?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Apr 2017
    Posts
    5
    No,it's not,but it doesn't work,because this is recursion and I am not good with recursion.
    This is my code that doesn't work.
    Code:
    void quicksort(int *array, int n) {
        int pi;
        if (n < 2)
            return;
        if(n<200){
            selectionsort(array,n);
        }
    else{
        pi = partition(array, n);
    }
        quicksort(array, pi);
        quicksort(array + pi + 1, n - pi - 1);
    
    }
    Last edited by tony172; 04-28-2017 at 05:07 AM.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,777
    Once you have used selection sort on the range, there's nothing else to sort in that range, so you should just return.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Apr 2017
    Posts
    5
    I tried returning but it doesnt work,array is not sorted and some elements are missing.
    Code:
    void quicksort(int *array, int n) {
        int pi;
        if (n < 2)
            return;
        if(n<200){
            selectionsort(array,n);
            return;
        }
    else{
        pi = partition(array, n);
    }
        quicksort(array, pi);
        quicksort(array + pi + 1, n - pi - 1);
    
    }

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,777
    1. Does your original quicksort function work?
    2. Does your selection sort function work?
    3. Assuming your answer to #1 and #2 are "yes", what is your implementation of the partition function and the selectionsort function?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Apr 2017
    Posts
    5
    Of course it works.
    Here is my implementation.
    Code:
    void selectionsort(int *niz, int n) {
    	int i;
    	for (i = 0; i < n - 1; i++) {
    		int j, tmp, maxi = i;
    		for (j = i + 1; j < n; j++) {
    			if (niz[j] < niz[maxi])
    				maxi = j;
    		}
    
    
    		tmp = niz[maxi];
    		niz[maxi] = niz[i];
    		niz[i] = tmp;
    	}
    }
    
    
    int partition(int *niz, int n) {
    	int l, r;
    	l = 1;
    	r = n - 1;
    	while (l < r) {
    		if (niz[r] >= niz[0]) {
    			r--;
    		}
    		else if (niz[l] < niz[0]) {
    			l++;
    		}
    		else {
    			int tmp = niz[l];
    			niz[l] = niz[r];
    			niz[r] = tmp;
    		}
    	}
    	if (niz[0] < niz[r]) {
    		return 0;
    	}
    	else {
    		int tmp = niz[r];
    		niz[r] = niz[0];
    		niz[0] = tmp;
    		return r;
    	}
    }
    
    
    
    
    void quicksort(int *niz, int n) {
    	int pi;
    	if (n < 2) 
    		return;
    	pi = partition(niz, n);
    	quicksort(niz, pi); 
    	quicksort(niz + pi + 1, n - pi - 1);
    }

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,777
    I plugged in your functions into a test program I was preparing, and as far as I can tell, your modification of your implementation of quicksort works:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    void selectionsort(int *niz, int n) {
        int i;
        for (i = 0; i < n - 1; i++) {
            int j, tmp, maxi = i;
            for (j = i + 1; j < n; j++) {
                if (niz[j] < niz[maxi])
                    maxi = j;
            }
    
    
            tmp = niz[maxi];
            niz[maxi] = niz[i];
            niz[i] = tmp;
        }
    }
    
    int partition(int *niz, int n) {
        int l, r;
        l = 1;
        r = n - 1;
        while (l < r) {
            if (niz[r] >= niz[0]) {
                r--;
            }
            else if (niz[l] < niz[0]) {
                l++;
            }
            else {
                int tmp = niz[l];
                niz[l] = niz[r];
                niz[r] = tmp;
            }
        }
        if (niz[0] < niz[r]) {
            return 0;
        }
        else {
            int tmp = niz[r];
            niz[r] = niz[0];
            niz[0] = tmp;
            return r;
        }
    }
    
    void quicksort(int *array, int n) {
        int pi;
        if (n < 2)
            return;
        if (n < 200) {
            selectionsort(array, n);
            return;
        }
        else {
            pi = partition(array, n);
        }
        quicksort(array, pi);
        quicksort(array + pi + 1, n - pi - 1);
    }
    
    void populate(int numbers[], int n) {
        int i;
        for (i = 0; i < n; ++i) {
            numbers[i] = i;
        }
    }
    
    void shuffle(int numbers[], int n) {
        int i;
        int r;
        int temp;
        for (i = n - 1; i > 1; --i) {
            r = rand() % (i + 1);
            if (i != r) {
                temp = numbers[i];
                numbers[i] = numbers[r];
                numbers[r] = temp;
            }
        }
    }
    
    int check_sorted(int numbers[], int n) {
        int i;
        for (i = 0; i < n; ++i) {
            if (numbers[i] != i) {
                return 0;
            }
        }
        return 1;
    }
    
    #define N 1000000
    
    int main(void) {
        int numbers[N];
        srand((unsigned int)time(NULL));
        populate(numbers, N);
        shuffle(numbers, N);
        quicksort(numbers, N);
        printf("Sorted: %d\n", check_sorted(numbers, N));
        return 0;
    }
    When I comment out the return statement I suggested, it segfaults.

    Actually, you can write your modified quicksort a bit more clearly:
    Code:
    void quicksort(int *array, int n) {
        int pi;
        if (n >= 200) {
            pi = partition(array, n);
            quicksort(array, pi);
            quicksort(array + pi + 1, n - pi - 1);
        }
        else if (n >= 2) {
            selectionsort(array, n);
        }
    }
    Last edited by laserlight; 04-29-2017 at 04:56 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Apr 2017
    Posts
    5
    Thank you soo much

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Optimize?
    By nuko in forum C Programming
    Replies: 3
    Last Post: 12-21-2011, 01:14 AM
  2. Help me optimize
    By sand_man in forum Game Programming
    Replies: 14
    Last Post: 05-10-2005, 05:19 PM
  3. How to Optimize
    By cfrost in forum C++ Programming
    Replies: 5
    Last Post: 11-09-2004, 09:07 AM
  4. Replies: 2
    Last Post: 05-06-2003, 08:34 AM
  5. Replies: 2
    Last Post: 10-18-2002, 08:30 AM

Tags for this Thread