Quicksort (C++/ Java/ C/ Prolog / javaScript)

quickSort.cpp

#include <iostream>

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 << "Size of test array : "  << N << endl;

    cout << "Before sorting : " << endl;
    print(test, N);

    quickSort(test, 0, N-1);

    cout << endl << endl << "After sorting : " << endl;
    print(test, N);
    
    return 0;
}

/**
* Quicksort.
* @param a The array to be sorted.
* @param first The start of the sequence to be sorted.
* @param last The end of the sequence to be sorted.
*/
void quickSort( int a[], int first, int last ) 
{
    int pivotElement;

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

/**
* Find and return the index of pivot element.
* @param a The array.
* @param first The start of the sequence.
* @param last The end of the sequence.
*/
int pivot(int a[], int first, int last) 
{
    int  p = first;
    int pivotElement = a[first];

    for(int i = first+1 ; i <= last ; i++)
    {
        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 a 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 a 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;
} 

This code was developed by me, G. Samaras.

Notice, that I used as little C++ as possible, so that one can easy interchange between C and C++.

Implementation in Java

package quicksortjava;

/**
 * Same implementation as above, but in Java
 * @author SAMARAS
 */
public class QuicksortJava {
    public static void main(String[] args) {
        int test[] = { 7, -13, 1, 3, 10, 5, 2, 4 };
        // No need to remember size of array, like in C
      
 
        System.out.println("Before sorting : ");
        print(test);
 
        quickSort(test, 0, test.length - 1);
 
        System.out.println("After sorting : ");
        print(test);
     
    
    }

    /**
    * Print an array.
    * @param a The array.
    * @param N The size of the array.
    */
    private static void print( int[] A)
    {
        for(int i = 0 ; i < A.length ; i++)
            System.out.println("array[" + i + "] = " + A[i]);
    }

    
    /**
    * Quicksort.
    * @param a The array to be sorted.
    * @param first The start of the sequence to be sorted.
    * @param last The end of the sequence to be sorted.
    */
    private static void quickSort( int A[], int first, int last ) 
    {
        int pivotElement;
 
        if(first < last)
        {
           pivotElement = pivot(A, first, last);
           quickSort(A, first, pivotElement-1);
           quickSort(A, pivotElement+1, last);
        }
    }
    
    /**
    * Find and return the index of pivot element.
    * @param a The array.
    * @param first The start of the sequence.
    * @param last The end of the sequence.
    */
    private static int pivot( int A[], int first, int last ) 
    {
        int  p = first;
        int pivotElement = A[first];
 
        for(int i = first+1 ; i <= last ; i++)
        {
            if(A[i] <= pivotElement)
            {
                p++;
                swap(A, i, p);
            }
        }
 
            swap(A, p, first);
 
        return p;
    }
 
 
    /**
    * Swap the parameters.
    * @param a The first parameter.
    * @param a The second parameter.
    */
    private static void swap(int A[], int a, int b)
    {
        // Check the link below code to see why we changed swap method.
        // You still can use the swap that
        // does not uses an extra variable
        // from the C++ implementation.
        int temp = A[a];
        A[a] = A[b];
        A[b] = temp;
    }
 
}

Implementation in C

Remember that one can use the built-in quicksort implementation of C (qsort-stdlib.h).

#include <stdio.h>

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

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

    printf("Size of test array : %d\n", N);

    printf("Before sorting : \n");
    print(test, N);

    quickSort(test, 0, N-1);

    printf("After sorting : \n");
    print(test, N);
    
    return 0;
}

/**
* Quicksort.
* @param a The array to be sorted.
* @param first The start of the sequence to be sorted.
* @param last The end of the sequence to be sorted.
*/
void quickSort( int a[], int first, int last ) 
{
    int pivotElement;

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

/**
* Find and return the index of pivot element.
* @param a The array.
* @param first The start of the sequence.
* @param last The end of the sequence.
*/
int pivot(int a[], int first, int last) 
{
    int  i, p = first;
    int pivotElement = a[first];

    for(i = first+1 ; i <= last ; i++)
    {
        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 a The second parameter.
*/
void swap(int* a, int* b)
{
    // You still can use the swap that
    // does not uses an extra variable
    // from the C++ implementation.
    int temp = *a;
    *a = *b;
    *b = temp;
}

/**
* Print an array.
* @param a The array.
* @param N The size of the array.
*/
void print(int a[], const int N)
{
    int i;
    for(i = 0 ; i < N ; i++)
        printf("array[%d] = %d\n",i ,a[i]);
}

Swap in Java.

Implementation in Prolog

/* quicksort(Xs, Ys) is true if Ys is a sorted permutation of the list Xs. */
quicksort(Xs, Ys):-quicksort_1(Xs, Ys, []).
 
quicksort_1([], Ys, Ys).
quicksort_1([X|Xs], Ys, Zs):-
  partition(Xs, X, Ms, Ns),
  quicksort_1(Ns, Ws, Zs),
  quicksort_1(Ms, Ys, [X|Ws]).
 
/* partition(Ls, X, Ms, Ns) is true if the list Ms contains the elements   */
/*   of the list Ls which are less than or equal to X, and the list Ns     */
/*   contains the elements of Ls which are greater than X.                 */
partition([K|L], X, M, [K|N]):-
  X < K, !,
  partition(L, X, M, N).
partition([K|L], X, [K|M], N):-
  partition(L, X, M, N).
partition([], _, [], []).

Implementation in javaScipt

/**
 * I used this code to sort the table of Klouvi results. The scenario was that I had a table, which I wanted to sort* by one field (array a in the quickSort()). I would also need an array ("names"), which would hold the id of every entry of the table. I would sort these two arrays simultaneously and I would use the swapEntries() to swap the entries of the table too.
*/
/** 
 * Will swap two table entries 
 * @param a - name of first player
 * @param b - name of second player
*/
function swapEntries(a, b)
{
	var editor = $("#" + a);  //put your ids here
      	var viewer = $("#" + b);

	editorContent = editor.clone();
    	viewerContent = viewer.clone();

 	editor.replaceWith(viewerContent);
    	viewer.replaceWith(editorContent);
}

/** 
 * Will swap two array cells
 * @param ar - array
 * @param a - first cell's index
 * @param b - second cell's index
*/
function swap(ar, a, b)
{
	var temp = ar[a];
	ar[a] = ar[b];
	ar[b] = temp;
}

/**
 * Quicksort.
 * @param a - The array to be sorted.
 * @param first - The start of the sequence to be sorted.
 * @param last - The end of the sequence to be sorted.
 * @param names - Array of names.
*/
function quickSort( a, first, last, names ) 
{
    var pivotElement;
 
    if(first < last)
    {
        pivotElement = pivot(a, first, last, names);
        quickSort(a, first, pivotElement-1, names);
        quickSort(a, pivotElement+1, last, names);
    }
}
 
/**
 * Find and return the index of pivot element.
 * @param a - The array.
 * @param first - The start of the sequence.
 * @param last - The end of the sequence.
 * @param names - Array of names.
 * @return - the pivot element.
*/
function  pivot( a, first, last) 
{
    var p = first;
    var pivotElement = a[first];
 
    for(var  i = first+1 ; i <= last ; i++)
    {
        if(a[i] > pivotElement)
        {
            p++;
            swap(a, i, p);
	     swapEntries(names[i], names[p]);
	     swap(names, i, p);
        }
    }
 
    swap(a, p, first);
    swapEntries(names[p], names[first]);
    swap(names, p, first);
 
    return p;
}

In case the data of the a array are strings, then 10 will be assumed to be 1 and so on. So, if for example you fill the a array with jQuery and .text(), you need to use parseInt(), in order to convert strings to integers!

Have questions about this code? Comments? Did you find a bug? Let me know!😀
Page created by G. (George) Samaras (DIT)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s