snippetjavaMinor
Quick Sort Implementation
Viewed 0 times
sortimplementationquick
Problem
I have written the below code for quick sort in Java:
Please review and possibly offer a better solution.
void quicksort (int[] a, int lo, int hi)
{
// lo is the lower index, hi is the upper index
// of the region of array a that is to be sorted
int i=lo, j=hi, h;
// comparison element x
int x=a[(lo+hi)/2];
// partition
do
{
while (a[i]x) j--;
if (i<=j)
{
h=a[i];
a[i]=a[j];
a[j]=h;
i++;
j--;
}
} while (i<=j);
// recursion
if (lo<j) quicksort(a, lo, j);
if (i<hi) quicksort(a, i, hi);
}Please review and possibly offer a better solution.
Solution
Some small notes:
-
Instead of commenting here:
rename the variables:
It's easier to read.
(Check Clean Code by Robert C. Martin, page 53-54 also.)
-
Try to minimize the scope of local variables. It's not necessary to declare them at the beginning of the method.
(Effective Java, Second Edition, Item 45: Minimize the scope of local variables. (Google for "minimize the scope of local variables", it's on Google Books too.))
-
This:
can be extracted out to a
-
Maybe you should provide an easier to use helper method too for the clients:
Note the input validation.
-
Instead of commenting here:
void quicksort (int[] a, int lo, int hi) {
// lo is the lower index, hi is the upper index
// of the region of array a that is to be sorted
int i=lo, j=hi, h;rename the variables:
void quicksort (final int[] a, final int lowerIndex, final int upperIndex)It's easier to read.
(Check Clean Code by Robert C. Martin, page 53-54 also.)
-
Try to minimize the scope of local variables. It's not necessary to declare them at the beginning of the method.
(Effective Java, Second Edition, Item 45: Minimize the scope of local variables. (Google for "minimize the scope of local variables", it's on Google Books too.))
-
This:
h=a[i];
a[i]=a[j];
a[j]=h;can be extracted out to a
swap method:public void swap(final int[] arr, final int pos1, final int pos2) {
final int temp = arr[pos1];
arr[pos1] = arr[pos2];
arr[pos2] = temp;
}-
Maybe you should provide an easier to use helper method too for the clients:
public void quicksort(final int[] data) {
if (data == null) {
throw new NullPointerException("data cannot be null");
}
if (data.length == 0) {
return;
}
quicksort(data, 0, data.length - 1);
}Note the input validation.
Code Snippets
void quicksort (int[] a, int lo, int hi) {
// lo is the lower index, hi is the upper index
// of the region of array a that is to be sorted
int i=lo, j=hi, h;void quicksort (final int[] a, final int lowerIndex, final int upperIndex)h=a[i];
a[i]=a[j];
a[j]=h;public void swap(final int[] arr, final int pos1, final int pos2) {
final int temp = arr[pos1];
arr[pos1] = arr[pos2];
arr[pos2] = temp;
}public void quicksort(final int[] data) {
if (data == null) {
throw new NullPointerException("data cannot be null");
}
if (data.length == 0) {
return;
}
quicksort(data, 0, data.length - 1);
}Context
StackExchange Code Review Q#6939, answer score: 7
Revisions (0)
No revisions yet.