up vote 2 down vote favorite

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 < right) {

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

    /*loop for right half array*/
    while (ar[right] > 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 < 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 < right) {

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

    /*loop for right half array*/
    while (ar[right] > 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 < 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 ?

share|improve this question
    
A sorting function should state if it maintains order of equivalent elements. This is: it is a stable sort? This additional property is sometimes a low cost for a given algorithm, for others, its adds code complexity. Maybe for some, it totally defeats a some key performance factor of the sort. I suspect, to maintain order with this algorithm, more than partition() needs to be amended so really cannot discuss how to handle it. – chux Apr 26 '16 at 22:25
    
Use Hoare partition scheme, but with your median of 3 pivot. It doesn't have the infinite loop issue on duplicate values (since it always either increments left or decrements right). – rcgldr May 27 '16 at 0:03
up vote 3 down vote

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:

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.

share|improve this answer
    
Well Ana thanx for your feedback cause both of us have the same philosophy but what I would say the code I directly pasted from my rough sheet. However the indentation was a bit tough for me as I could not get the indentation style of SO. Anyways, the questions were actually: 1. How do you veterans handle the duplicate values ? 2. Which sorting algos are used in contests and real life scenario ? 3. (It may seem a bit off topic) Do the binary and other tree structures like in merge sort are similarly formed that we use in quicksort ? – ph03n1x Apr 21 '16 at 11:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.