Algorithm description

Quick description

Quick sort is an algorithm to sort elements (we will use a vector)

In short, the procedure for sorting is done in this way: i take a vector's element (the pivot) (for example the first element of the vector) and then i move the pivot and all the elements, with value less than the value of pivot, at left of the pivot and all the elements, with value more hight, to the right of the pivot.
In this way i have the pivot in a position where at its left there are all the element of less value and at right, all the element with value more hight. So the pivot is an element just sorted in the vector. It's just in the right position.
Now i can see the array as made by three elements. The pivot, the left sub vector and the right sub vector.
So i can apply the same algorithm to the left sub vector and the right sub vector.
This process is iterated in each sub vector until all the elements are sorted

As you can see this algorithm use divide et impera design algorithm. It 'divide' the problem in a smaller problem, solve them (impera) and combine the result (here it's not needed to combine)

Now i want to show how the algorithm works in more details

How the algorithm works

As i said i'll take, as a pivot, the first element of the vector. I also need of two index, i and j, to scan the vector.
The first, i, scan the vector from the first element (the pivot) to the right. Instead j will scan from the last position to the left

The first index (i) will find the first element for which its value is more hight than the value of the pivot and it will stop there (in this case the second element, the 9)
The second index (j) will search the first element for which the value is less than the value of pivot (in this case the second element, starting by the end. The value 2)

Now we exchange the value of two elements corrisponding the two indexes (2 and 9).
I'm moving all the elements less than 4 (the pivot) at left vector and all higher at right

The algorithm will continue in this way until all the elements are scanned and in case moved

At the end we excange the pivot with the i position.

Now the pivot is in the right position in the vector (sorted) and it's not need to move it anymore.
In order we have 2 sub vectors with the value, respectively, less and higher than the value of the pivot (4)

Now we can iterate the same algorithm to the left and right vectors.

At the end all the pivots will be in the right posizion, so the vector will be sorted

pseudo code alghoritm

As i told this algorithm is designed with 'divide et impera', so we here see how it work in general Because it's used 'divide et imper' we have to use recursive functions

qsort(v,i,f){

	m = partition(v,i,f)

	qsort(v,i,m-1)
	qsort(v,m+1,f)

}

partition(v,inf,sup){
	.....
	.....
	return m  #m è la posizione del pivot
}

The main function is qsort that basically call partition function e then it's called recursively.

The partition function is responsable to set the pivot in the right position and move to left of it all the elements whit the value less than the pivot and, at right, the higher value.

When the qsort function end we will have a sorted vector

Java implementation

Java implementation

QuickSort.java

/*
 * author: Michele Mottola
 * site: www.intellynet.com
 */

public class QuickSort {

	public void qsort(int[] v,int i, int f) {
		if(i>=f) return;
		int m = partition2(v,i,f);
		qsort(v,i,m-1);
		qsort(v,m+1,f);
		
		System.out.println(Arrays.toString(v));
	}

	
	public int partition2( int[] v,int inf ,int sup) {
		
		int pivot=inf;
		int i=inf;
		int j=sup;
		int temp;
		
		while(true) {
			
			while(v[i]<=v[pivot] && i<sup) {
				i++;
			}
			while(v[j]>v[pivot] && j>=1) {
				j--;
			}

			if(i<j) {
				temp=v[i];
				v[i]=v[j];
				v[j]=temp;
			}
			
			if(j<=i+1)
				break;
			
		}

		if(j<i) {
			j++;
			i--;
		}
		

		if(v[pivot]>v[i]){
			temp=v[i];
			v[i]=v[pivot];
			v[pivot]=temp;
		}
		
		
		return i;
		
		
	}


}

TestQuickSort.java

public class Test2QuickSort {

	public static void main(String[] args) {

		int[] v;
		v= new int[] {4,9,3,12,2,17,1,34,6};

		System.out.println("start vector "+Arrays.toString(v));
		
		QuickSort q = new QuickSort();
		q.qsort(v, 0, 8);
		
		System.out.println("end vector "+Arrays.toString(v));
		
	}

}

Notes

I think it's not required any other detail

java execution

start vector [4, 9, 3, 12, 2, 17, 1, 34, 6]
end vector [1, 2, 3, 4, 6, 9, 12, 17, 34]

R implementation

R implementation

#author: Michele Mottola
#site: www.intellynet.com


partition=function(v,inf,sup){
	
	pivot=inf
	i=inf
	j=sup
	
	while(TRUE){
		while(v[i]<=v[pivot] && i<sup) {
			i=i+1
		}
		
		while(v[j]>v[pivot] && j>=1) {  
			j=j-1
		}		

		if(i<j) {
			temp=v[i]
			v[i]=v[j]
			v[j]=temp
		}
		if(j<=i+1)
			break		
		
	}

	if(j<i) {
		j=j+1
		i=i-1
	}
	
	if(v[pivot]>v[i]){
		temp=v[i]
		v[i]=v[pivot]
		v[pivot]=temp	
	}
	
	assign("v", v, envir = .GlobalEnv)
	
	
	return(i)  
	
	
}



qsort2=function(i,f){
	if(i>=f){ 
		return
	}else{
		
		m = partition(v,i,f)
		
		qsort2(i,m-1)
		qsort2(m+1,f)
	
	}
}


#------ test -----------




v<<-c(4,9,5,17,2,23,8,31,15,3) 
i=1
f=10



cat("initial vector ",v,"\n")

qsort2(i,f)

cat("end vector ",v)

Java vs R

There are some differences between java and R

The first, low important, is that in R the first element of a vector has index 1 (in java is 0)
The second thing is important because i have spended many time. It's due to the recursive functions. The problem is that the script use recursive function that modify the vector v, but seems that in R there is no way to make that vector (passed as parameter) as global variable.
This make a problem. The solution i have used is to not use v as parameter of qsort function, but i use v as a global variable.
This is the bigger difference between my Java and R implementations.

R execution

initial vector  4 9 5 17 2 23 8 31 15 3 
end vector  2 3 4 5 8 9 15 17 23 31