My Quicksort - Your Opinion on programming style

[Jon Avadis]

Hey Folks

I programmed a quicksort program based on the quicksort-description on wikipedia.
The program is running fine. It is reading numbers from a text-file into an ArrayList and
then sorting that List with the quicksort-algorithm.

I attached a file with about 15000 random numbers from 1 to 1000 i used to test it.
I had to rename it to .jpg because .txt arent allowed to upload here...

Im interested in getting opinions on HOW well i programmed it and what i could improve
i.e.:
- hows the readability,
- are there parts that could be done more efficiently/simply,
- do i use keywords for methods and variables right (static, final, etc.) right
- did i choose appropriate classes/methods/loops etc.
- unnecessary or lacking comments
- whatever flaws you see

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Scanner;

public class KwikSort {

	static int 				elements;
	static ArrayList<Integer> 	unsorted;
	static Scanner			scanned;
	final static String 		NEWLINE = System.getProperty("line.separator");

	
	public static void main(String[] args) {
		initialize();
		loadToArray("c:\\random.txt");
		quickSort(0, elements-1);
		printList();
	}
		
	public static void initialize(){
		elements 	= 0;
		unsorted 	= new ArrayList<Integer>();
	}

	public static void loadToArray (String filepath){
		// filling ArrayList<Integer> called 'unsorted' with the numbers from inputfile
		
		try {

			scanned = new Scanner (new BufferedReader(new FileReader(filepath)));
			scanned.useDelimiter(NEWLINE);

			while (scanned.hasNext())	{ 			
				elements++;
				unsorted.add(new Integer(scanned.next()));
			}
			
		} catch (FileNotFoundException e){System.out.println("File not Found");}
	}


	public static void quickSort (int first, int last){

		if (!(first < last))	{	return;	}
		
		int newPivotPosition = splitAroundPivot(first, last);
		
		quickSort (first, newPivotPosition - 1); 	//recursion to sort left of pivot
		quickSort (newPivotPosition + 1, last);	//recursion to sort right of pivot
       }

	public static int splitAroundPivot (int firstInList, int lastInList){

		/* choose last element from the given range to be the pivot and
		 * then sort all elements <= pivot on its left and >= pivot on its right
		 * Once this is done, the new Pivot is set to the last element of the left-part of the list 
		 */
		
		int pivot 	= unsorted.get (lastInList);
		int first 	= firstInList;
		int last 	= lastInList -1;
	
		do{
			while ( unsorted.get(first) <= pivot && first < lastInList )	{	first++;	}
			while ( unsorted.get(last)  >= pivot && last > firstInList )	{	last--;	}

			if (first < last) {
				// swap values because left is bigger than pivot and right smaller than pivot
				
				int temp = unsorted.get(first);
				unsorted.set(first, unsorted.get(last));
				unsorted.set(last, temp);
			}
		} while(first < last);
		
		if (unsorted.get(first) > pivot) {
			// swap pivot element with element at index 'first'
			
			int temp = unsorted.get(first);
			unsorted.set(first, unsorted.get(lastInList));
			unsorted.set(lastInList, temp); 		
		}
		return first; //first now represents the new pivot-position
	}

	public static void printList (){
		for (int i =0 ; i < elements; i++){
			System.out.println (unsorted.get(i));
		}
	}
	
}

[Campbell Ritchie]

It's only Kwik in adverts
Why is your array list static? Why are all your fields static?
Don't declare a List as ArrayList<T> but as List<T>.
Use spaces for indenting, not tabs.
Why are you not creating an object and calling methods on that?
Why has your class got no constructor?
Why do you have an elements field when you could use the size() method of the List instead?
Why are you passing a BufferedReader to the Scanner constructor rather than a File object?
Why are you altering the delimiter on the Scanner rather than using its nextInt() method?
Why are you using system.out rather than System.err for an Exception message?
Why have you got inconsistent indentation, with some lines containing {...}?
You have inconsistent use of whitespace, sometimes putting a space after keywords and before (, and you are doing the same with method names and invocations.

What I am least happy about is trying to do everything in a static context rather than creating an object which does its own loading and printing (at least). I am also not happy about the return in the middle of the recursive method, but many people will disagree with me on that.

Anybody else? Some people will doubtless disagree with me on some points.

[Jon Avadis]

Thanks a bunch Campell!
I'll need some time to answer & wait for more input.

Thanks to everyone taking the time to read the code and write your suggestions, its highly appreciated!

[Campbell Ritchie]

What you should do for sorting Lists is to dump the entire contents of the List into a Comparable[] array (Integer implements Comparable<Integer>, so that's all right, otherwise you would supply a Comparator), sort the array and re-create the List from the array. There is an explanation for that peculiar procedure here.

[Alexander Sales]

i don't like the tabs on the static fields.


i like the high level abstractions down to the low level abstractions.
i like the method arrangements.
i like the naming conventions used.

cool usage of scanner! It's the first time i've seen it.

why NEWLINE instead of LINE_SEPARATOR? my interpretation of NEWLINE is "\n".
why use line.separator? instead of making it simple or what you really have used as delimiter "\".

else are good! and i have learned a lot.

looks like you have read Clean code by Robert Martin

[Jon Avadis]

Campbell Ritchie wrote:Why is your array list static? Why are all your fields static?

I gotta admit im still confused when to use static and when not to. My reasoning here was this: Im writing a program
that sorts numbers in a txt-file, i wont need multiple instances of my fields.

Don't declare a List as ArrayList<T> but as List<T>.

Ill have to look into that.

Use spaces for indenting, not tabs.

Eclipse does that for me, i'll have to check if it can be changed in options/preferences

Why are you not creating an object and calling methods on that?
Why has your class got no constructor?

I guess thats the reason for all my static stuff. Im not thinking in objects enough yet.
I shall try and rewrite it this way

Why do you have an elements field when you could use the size() method of the List instead?

Indeed, i shall change that. I even had an additional "counter" variable before and was happy to get rid of that, but your right,
i dont need "elements".

Why are you passing a BufferedReader to the Scanner constructor rather than a File object?

I thought buffered Reading was the preferred way to go. Wont the Scanner(File) constructer use an unbuffered Filereader to
read from the file?

Why are you altering the delimiter on the Scanner rather than using its nextInt() method?

I set the delimiter explicitly to what i know the file will be delimited by. Isnt it good to be explicit like that?
I didnt know about the nextInt() method, ill replace next() with nextInt() and hasNext() with hasNextInt().

Why are you using system.out rather than System.err for an Exception message?

A bad habit of using system.out for everything i guess, will change that too.

Why have you got inconsistent indentation, with some lines containing {...}?

If i have for example a short "if" or "catch" blocks i can fit easily on one line, i tend to do it, because it look cleaner to me.
I understand its against conventions though.

You have inconsistent use of whitespace, sometimes putting a space after keywords and before (, and you are doing the same with method names and invocations.

Nicely spotted, ill try to be more consistent here.

What I am least happy about is trying to do everything in a static context rather than creating an object which does its own loading and printing (at least).

Yes. I'll try and rewrite it as Object.

I am also not happy about the return in the middle of the recursive method, but many people will disagree with me on that.

For me this was just the most obvious solution to exit the method if the given parameters are "faulty". What would you suggest to do instead?

[Jon Avadis]

Alexander Sales wrote:i don't like the tabs on the static fields.

I dont know, I like to have my field-names start at the same point of the line (it shifted when pasting it here).

i like the high level abstractions down to the low level abstractions.
i like the method arrangements.
i like the naming conventions used.
cool usage of scanner! It's the first time i've seen it.

Thanks!

why NEWLINE instead of LINE_SEPARATOR? my interpretation of NEWLINE is "\n".
why use line.separator? instead of making it simple or what you really have used as delimiter "\".

Campells comment made me look at Scanner again. The default delimiter is "whitespace characters" which
includes "\n" "\r" etc. so i wouldnt even have to set it at all.
I agree that LINE_SEPARATOR would be more meaningful name.

looks like you have read Clean code by Robert Martin

I havent, but ill check it out

[Campbell Ritchie]

Jon Avadis wrote:

Campbell Ritchie wrote:Why is your array list static? Why are all your fields static?

I gotta admit im still confused when to use static and when not to.

There are valid reasons for a sort method to be static, but you need to know why you are using static.

Don't declare a List as ArrayList<T> but as List<T>.

Ill have to look into that.

Use spaces for indenting, not tabs.

Eclipse does that for me, i'll have to check if it can be changed in options/preferences

Yes, there is an option for that. I think you should write code by hand to check for your code style.

Why are you not creating an object and calling methods on that?
Why has your class got no constructor?

I guess thats the reason for all my static stuff. Im not thinking in objects enough yet.
I shall try and rewrite it this way

You should either create an object of your class which encapsulates the List to sort, or decide why having all your methods static is a valid decision (as I said earlier).

Why do you have an elements field when you could use the size() method of the List instead?

Indeed, i shall change that. I even had an additional "counter" variable before and was happy to get rid of that, but your right,
i dont need "elements".

I often find when helping beginners that they include redundant code; I can often delete whole lines because they don't actually do anything..

Why are you passing a BufferedReader to the Scanner constructor rather than a File object?

I thought buffered Reading was the preferred way to go. Wont the Scanner(File) constructer use an unbuffered Filereader to
read from the file?

Don't know. You can go to your Java™ installation folder and unzip the src.zip file and see the code for Scanner.

Maybe you are right and I was mistaken to query it.

Why are you altering the delimiter on the Scanner rather than using its nextInt() method?

I set the delimiter explicitly to what i know the file will be delimited by. Isnt it good to be explicit like that?
I didnt know about the nextInt() method, ill replace next() with nextInt() and hasNext() with hasNextInt().Have you checked what the default delimiter for a Scanner is? Will that work instead of changing it? And will that tie you to a particular format of file?

It says "simple" in the Scanner documentation, which I think means it scans simple text, not that Scanner is simple. It is very sophisticated, with methods like nextInt(). Using such methods will save you a lot of time.

Why are you using system.out rather than System.err for an Exception message?

A bad habit of using system.out for everything i guess, will change that too.

That's what System.err is there for, but many people forget about it altogether.

Why have you got inconsistent indentation, with some lines containing {...}?

If i have for example a short "if" or "catch" blocks i can fit easily on one line, i tend to do it, because it look cleaner to me.
I understand its against conventions though.

But you asked about style and part of style means following the conventions. If you ask somebody to listen to a complicated explanation and introduce a grammatical error, many people will notice the grammatical error and miss the thread of the argument. If you ask somebody to check your code for errors and introcude an indenting error, they will notice the indenting error and may miss a more serious error in the code. Also consistent indentation makes it easier to find errors cause by mis-matched {} pairs.
. . .

What I am least happy about is trying to do everything in a static context rather than creating an object which does its own loading and printing (at least).

Yes. I'll try and rewrite it as Object.

I am also not happy about the return in the middle of the recursive method, but many people will disagree with me on that.

For me this was just the most obvious solution to exit the method if the given parameters are "faulty". What would you suggest to do instead?If first > last, you have an input error. You ought to handle that by defensive programming, by being more assertive than a milk-and-water return. No milk-and-water any more. Give them some spirit!

if (first > last)
{
   throw new IllegalArgumentException("first > last");
}

If that happens, there is an error somewhere else in the code, which you need to sort out. You should of course notify the Exception in the documentation comments. If you want really stylish code, you ought to have documentation comments for every class, field and method, even though the javadoc tool produces no output for private members. There is a chapter in Joshua Bloch's Effective Java, and there is lots about documentation comments here.

[Campbell Ritchie]

For Lists rather than ArrayLists, look up "program to the interface, not the implementation" It was a typo that I wrote introcude but I thought I would let it stand so it can distract you from following the post.

[Campbell Ritchie]

I earlier wrote: . . . look up "program to the interface, not the implementation" . . .

I did, and found this, which looks promising.

[Jon Avadis]

Campbell Ritchie wrote:What you should do for sorting Lists is to dump the entire contents of the List into a Comparable[] array (Integer implements Comparable<Integer>, so that's all right, otherwise you would supply a Comparator), sort the array and re-create the List from the array. There is an explanation for that peculiar procedure here.

That of course defeats the whole purpose of writing a quicksort program