quick sort using partitioning technique

Question

I implemented quick sort using partitioning technique. The one issue I am facing is based on the pivot I need to change my code. Below is my implementation of qsort.

#include<iostream>
using namespace std;
void qsort1(int arr[], int p, int q)
{ 
    if(p<q)
    {
        int ppos = p;
        int pivot = arr[ppos];
        int r = p; 
        for(int i=p;i<=q;i++)
        {
            if(arr[i] < pivot)
            {
                r++;
                swap(arr[i],arr[r]);  
            }
        }
        swap(arr[r],arr[ppos]);
        qsort1(arr,p,r-1);
        qsort1(arr,r+1,q);
    }
}
int main()
{
    int arr[]= {9,7,4,1,2,3};
    qsort1(arr,0,5);
    for(int i =0;i<6;i++)
        cout<<arr[i]<<endl;
    return 0;
}

To change the pivot from first to last element I need to change my r to exclude the last element. can someone please suggest me a better implementation using same partitioning technique . By the way its not a homework question.

I've you're including <iostream>, then this is not a C program. I've edited your tags. — Greg Hewgill
– Greg Hewgill, Commented Mar 27, 2012 at 20:44
@KennyTM There are about 1000 reasons I can think of not to use STL in every case. With that said, most people lack basic understanding of how algorithms work, and if mousey is doing "self homework" then I think he should be praised — std''OrgnlDave
– std''OrgnlDave, Commented Mar 27, 2012 at 20:47
@mousey generally speaking, you should use a randomly chosen initial qsort pivot. For instance if your array is already sorted using this pivot selection method it will cause O(n * n) behavior. Choosing a random elements helps to amortize the worst-case cost of O(n*n) to roughly O(n log n). Failing a random element, choosing the middle pivot or even the median (if you have access to that) works too. — std''OrgnlDave
– std''OrgnlDave, Commented Mar 27, 2012 at 20:50

Scott Hunter · Accepted Answer · 2012-03-27 20:55:21Z

4

Why not just swap the first element w/ the one you want to use as the pivot? Then your code using the first element as the pivot will do just fine.

answered Mar 27, 2012 at 20:55

Scott Hunter

50k12 gold badges64 silver badges107 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

amit Over a year ago

+1: Make a small change [processing] and reduce the problem to the already solved one.

Matt Eckert Over a year ago

This is a good example of catb.org/~esr/faqs/smart-questions.html#goal

Collectives™ on Stack Overflow

quick sort using partitioning technique

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related