Ytdyklly

#include <iostream>    



using std::cout;

using std::endl;



int arr = {3,4,2,1,-5,116,31,4,0};



void QuickSort(int start,int end);

int Partition(int start, int end); 

void Swap(int * , int *);

void PrintArr();



int main(int argc, char* argv)

{



    PrintArr();



    QuickSort(0, sizeof(arr)/sizeof(int));



    PrintArr();





    return 0;

}



void QuickSort(int start,int end)

{

    if(start >= end) return;



    int index = Partition(start , end);



    QuickSort(start, index - 1);

    QuickSort(index + 1, end);

}



int Partition(int start, int end)

{

    int index = start;

    int pivot = arr[end-1];

    for(int i = start;i < end - 1;i++)

    {

        if(arr[i] <= pivot)

        {

            Swap(arr + index,arr + i);

            index++;

        }

    }



    Swap(arr + index, arr + end - 1);



    return index;



}



void Swap(int *a , int *b)

{

    if(*a != *b)

    {

        int temp = *a;

        *a = *b;

        *b = temp;

    }

}



void PrintArr()

{

    for(int i = 0;i<sizeof(arr)/sizeof(arr[0]); i++)

        cout<<arr[i] <<" ";



    cout<<endl;

}

Writing an implementation of quicksort is fairly easy. Writing a good implementation that works at least reasonably well with almost any input is much more difficult.

Your uses a choice of pivot element that's pretty well know for bad behavior. By choosing the last element in a range (or the first) you essentially guarantee that it runs in $O(N^2)$ if the input is sorted. One typical way of preventing this problem is to use a "median of three" to select the pivot element--that is, look at the first, middle and last elements, and use the median of those three as the pivot.

There's one more minor detail there though: you don't just want to choose the median of those three and use it as your pivot. If those three elements are out of order (with respect to each other) you want to sort them, and write them back to the array in their sorted order. This improves behavior (somewhat) during the recursive calls.

Another subtlety that important to correct behavior (rather than just performance) is to use the correct order for your recursive calls. To assure against stack overflow, you always want to sort the smaller of the two partitions first. In conjunction with tail call elimination (which compilers have practiced for years) this can eliminate the possibility of stack overflow. If you want to be even more certain about it, you can change the final recursive call to iteration, so it's not up to the compiler to eliminate the tail recursion.

C++ adds another interesting twist, at least as soon as you start to deal with sorting collections of arbitrary types of objects (rather than just int). In this case, a user may well have written their own swap function that they expect you to use to swap objects of a particular type. Otherwise, you normally want to use std::swap rather than writing a swap of your own. To select between those correctly, you normally want to put using std::swap at the beginning of your partition function, and then use unqualified calls to swap (e.g., do not explicitly call std::swap). This way if the user has written a swap in the same namespace as the type you're sorting (and named it swap, like they should) your sorting routine will find that via ADL, and use it. Otherwise, it'll find std::swap because of the using std::swap;, and use that. This gives the behavior we want: use their swap routine by preference, but use std::swap if they haven't provided one.

A few other points: of course, the standard library has std::sort built in, which is typically implemented as introsort (which is just a quicksort that keeps track of recursion depth, and switches to a heap sort if quicksort is doing poorly for the input it's been given).

This code doesn't really look/feel much like most people expect C++ to be written. Right now, you're mostly using (and passing) indexes into the array. In C you'd more likely use pointers. In C++, you'd probably want to use iterators instead (though you can pass pointers as iterators). In C++ you'd also normally want something like this to be template, so it can be applied to almost any type of object, not just int. In addition, you'd typically allow the user to pass a comparison function so (for example) if they want to sort Person objects that don't support comparison using <, the user can still sort by passing (for example) a lambda expression saying they want to sort by a person's last name and first name (and default to std::less<T>, so if < is defined, it can be used by default, though the user can still pass a different comparison if they want).

Global Variables

Whether this is C or C++, global variables such as arr are always a bad idea. Global variables make writing and debugging code very difficult and allow for unintended side affects. The array arr should be defined in main and passed to all of the other functions.

Using std::ANYTHING

You as a software engineer may in your career write your own cin and cout. To do this you would have to have your own namespace so that std::cin and std::cout did not break your code. Including the namespace in the symbolic identified identifies which symbol you are using. This allows you to write programs and libraries that have the most meaningful names.

Use Container Classes

C++ has a great many container classes, some of which are std::vector, std::array, std::queue and std::stack. These container classes reduce the amount of code you need to write, and provide functionality such as the size of the array so that you don't have to write sizeof(arr)/sizeof(arr[0]). It would be much simpler to use the containers provided by the Standard Template Library.