Quick Sort template


public void sortIntegers(int[] A) {
	quicksort(A, 0, A.length - 1);
}

private void quicksort(int[] array, int start, int end){
	if(start >= end){
		return;
	}
	int index = partition(array, start, end);
	quicksort(array, start, index - 1);
	quicksort(array, index + 1, end);
}

private int partition(int[] array, int start, int end){
	int pivot = array[end];
	int i = start - 1;
	for(int j = start; j < end; j++){
		if(array[j] <= pivot){
			swap(array, ++i, j);
		}
	}
	swap(array, i + 1, end);
	return i + 1;
}

private void swap(int [] array, int i, int j){
	int temp;
	temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}

Advertisements

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