Optimizing quicksort partition method/function for duplicate elements I'm a newbie and interested in learning different data structures and algorithms. While implementing quicksort, I found this code works pretty well for partitioning.

int partition(int ar[], int lft, int rgt) {

int left = lft;
int right = rgt;
/*median of three is the best pivot value to accomplish in nlogn time*/
int pivotVal = ar[(left+right)/2];
printf("pivot: %d\n", pivotVal);

/*
-this while loop holds the left and right portion of the
-splitted array together to accomplish partitioning.
*/
while (left &lt; right) {

    /*loop for left half array*/
    while (ar[left] &lt; pivotVal) { left += 1; };

    /*loop for right half array*/
    while (ar[right] &gt; pivotVal) { right -= 1; };

    /*
    -if the above conditions are not met the sub arrays are unsorted
    -we need to sort or exchange the values.
    */
    if (left &lt; right) {
      int cache = ar[left];
      ar[left] = ar[right];
      ar[right] = cache;
    }


}

int pivotIndex = left; /*updated left or right is the pivot index*/
return pivotIndex;

}


Notice the code will get stuck in an infinite loop if there are any duplicate values in the given input array. So I hacked the problem just adding an additional line just after the swapping portion that looks like this:

int partition(int ar[], int lft, int rgt) {
int left = lft;
int right = rgt;
/*median of three is the best pivot value to accomplish in nlogn time*/
int pivotVal = ar[(left+right)/2];
printf("pivot: %d\n", pivotVal);

/*
-this while loop holds the left and right portion of the
-splitted array together to accomplish partitioning.
*/
while (left &lt; right) {

    /*loop for left half array*/
    while (ar[left] &lt; pivotVal) { left += 1; };

    /*loop for right half array*/
    while (ar[right] &gt; pivotVal) { right -= 1; };

    /*
    -if the above conditions are not met the sub arrays are unsorted
    -we need to sort or exchange the values.
    */
    if (left &lt; right) {
      int cache = ar[left];
      ar[left] = ar[right];
      ar[right] = cache;
    }

    /*if there are any duplicate value
    the above conditions would not met
    and the algo will go into an infinite loop.
    this if condition checks if there are any
    duplicate value if exixts... increase
    left or decrease right one to break the loop
    */
    if (ar[left] == ar[right]) {
      right--; /*if we increase left then pivot index will be the right one*/
    }


}

int pivotIndex = left; /*updated left or right is the pivot index*/
return pivotIndex;

}


How do you veterans handle the duplicate values ?
Naming

I'm a stickler for variable naming - most of my answers mention it. You should be too - correctly named variables make code much easier to maintain.

Now, while I don't know C that well at all, the principles are the same. In your first three lines you do this:

int partition(int ar[], int lft, int rgt) {
int left = lft;
int right = rgt;


Why bother with the extra two declarations? Name the variables correctly in the method declaration, and you can eliminate them entirely. While we're here, what does ar mean? You should name your variables according to the data they hold, so perhaps a method declaration like this would be better:

int partition(int unsortedArray[], int leftIndex, int rightIndex)


Then update your variable references in the rest of the code.

Formatting

Indent your code correctly. Trust me, it makes it much easier to see what comes in which block. I don't know whether this was a product of how you pasted it into the question (which it might well be), but make sure your method code is indented from the declaration.

Sorting algorithms

There are four major sorting algorithms:


Bubble sort
Shuttle sort
Quicksort
Shell sort


Each of those is useful for a different purpose, and each has a different time complexity. If you read through the Wikipedia articles (links above) for each, you should at least have a basic grounding in each.