HiveBrain v1.2.0
Get Started
← Back to all entries
snippetcppMinor

Quicksort for a pseudosite

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
forpseudositequicksort

Problem

I have a pseudosite, where I actually post small functions, so that I can re-use them*, but some posts have visitors. The top is Quicksort (C++). I feel that beginners visit it, so I do not care in improving (its poor) performance, but only the readability, so that the beginner can catch things more easily.

#include 

void quickSort(int a[], int first, int last);
int pivot(int a[], int first, int last);
void swap(int& a, int& b);
void swapNoTemp(int& a, int& b);
void print(int array[], const int& N);

using namespace std;

int main()
{
    int test[] = { 7, -13, 1, 3, 10, 5, 2, 4 };
    int N = sizeof(test)/sizeof(int);

    cout " */
        if(a[i] <= pivotElement)
        {
            p++;
            swap(a[i], a[p]);
        }
    }

    swap(a[p], a[first]);

    return p;
}

/**
 * Swap the parameters.
 * @param a - The first parameter.
 * @param b - The second parameter.
*/
void swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}

/**
 * Swap the parameters without a temp variable.
 * Warning! Prone to overflow/underflow.
 * @param a - The first parameter.
 * @param b - The second parameter.
*/
void swapNoTemp(int& a, int& b)
{
    a -= b;
    b += a;// b gets the original value of a
    a = (b - a);// a gets the original value of b
}

/**
 * Print an array.
 * @param a - The array.
 * @param N - The size of the array.
*/
void print(int a[], const int& N)
{
    for(int i = 0 ; i < N ; i++)
        cout << "array[" << i << "] = " << a[i] << endl;
}


As you see, I use many things from C, since I wanted the code to be able to work in a C program with minor modifications, thus I am adding c tag too.

*since I find it easier to find them there than in my FS and it helps in restoring harmony after a nuke.

Solution

Only small/minor issues:

-
Since code it to be portable to C with minor mods, suggest demarcating that which is sort code from test code. Its appears the sort code is only these 3. Do not mix test code with the application code. Better in separate files.

void quickSort( int a[], int first, int last ) 
int pivot(int a[], int first, int last) 
void swap(int& a, int& b)


-
pivot(), swap() should be static functions. No need for them outside this file.

-
Minor: int vs. size_t. An int index may lack sufficient range to index an array. Use size_t as that is Goldilocks type neither to narrow nor wide a type to handle all array sizes - it is just right. As size_t is some unsigned type, watch out for attempting to create negative values. I did not notice any issue for your code concerning that.

// int N = sizeof(test)/sizeof(int);
size_t N = sizeof(test)/sizeof(int);

// void quickSort( int a[], int first, int last )
void quickSort( int a[], size_t first, size_t last )

// int pivot(int a[], int first, int last) 
size_t pivot(int a[], size_t first, size_t last)


-
The sort would works well with other types beside int. Perhaps code that way.

typedef int sort_type;     
void quickSort(sort_type a[], size_t first, size_t last )


-
Function signature: Rather than oblige the calling code to supply 0, n-1, create a top level call:

void quickSortTop(sort_type a[], size_t size) {
  if (size) quickSort(a, 0, size-1);
}


-
Minor: Keep local variables as local as able. pivotElement could be declared and initialized in 1 step local to the if() block as it is not used outside the block. This borders on style issues, but as a rule, limiting variable scope is easier to see its use and impact.

int pivotElement;  // here 
if(first < last) {
    int pivotElement = pivot(a, first, last); // or here
    quickSort(a, first, pivotElement-1);
    quickSort(a, pivotElement+1, last);
}


-
Minor: Correct comment? I would think to reverse the order a >= would be needed. If this is not so, then I would expect

-
Minor: Dead code
swapNoTemp()`. No explanation for its existance here.

Code Snippets

void quickSort( int a[], int first, int last ) 
int pivot(int a[], int first, int last) 
void swap(int& a, int& b)
// int N = sizeof(test)/sizeof(int);
size_t N = sizeof(test)/sizeof(int);

// void quickSort( int a[], int first, int last )
void quickSort( int a[], size_t first, size_t last )

// int pivot(int a[], int first, int last) 
size_t pivot(int a[], size_t first, size_t last)
typedef int sort_type;     
void quickSort(sort_type a[], size_t first, size_t last )
void quickSortTop(sort_type a[], size_t size) {
  if (size) quickSort(a, 0, size-1);
}
int pivotElement;  // here 
if(first < last) {
    int pivotElement = pivot(a, first, last); // or here
    quickSort(a, first, pivotElement-1);
    quickSort(a, pivotElement+1, last);
}

Context

StackExchange Code Review Q#121065, answer score: 2

Revisions (0)

No revisions yet.