Problem with sorting an integer array

[Nelson Sam]

I am trying to sort an array.Below is the code.But I cant get it working properly.

    
import java.io.*;

class numbersort
{
public static void main(String args[]) throws Exception
	{
	int n;
	int[] a=new int[10];
	int temp=0;
	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	
	System.out.println("Enter no of elements:");
	n=Integer.parseInt(br.readLine());
	System.out.println("Enter the elements");
		for(int i=0;i<n;i++)
			{
			a[i]=Integer.parseInt(br.readLine());
			}

	for(int i=0;i<n;i++)
			{
			if(a[i]>a[i+1])
			
				{
				temp=a[i];
				a[i]=a[i+1];
				a[i+1]=temp;
				}
			}

	System.out.println("Sorted Order");

	for(int i=0;i<n;i++)
			{
			System.out.println(a[i]);
			}
	}
}

[Seetharaman Venkatasamy]

Hmm. sounds like you are trying Bubble sort[you need to improve your for loop]. why cant you use Arrays.sort ?

[Nelson Sam]

Hi Seetharaman Venkatasamy

I know using sort() method.
But I want to sort programatically.

[Seetharaman Venkatasamy]

google for bubble sort algorithm,basic algorithm.

[Norm Radder]

I cant get it working properly

Can you show the output and explain?

A suggestion: For ease of testing use a hardcoded array of ints vs prompting the user.

int[] anArray = new int[] {3,4,2,6};

It'll make the debugging easier.

[Campbell Ritchie]

I always thought bubble sort/sinking sort needs two for loops, inside each other.

[Rene Larsen]

Campbell Ritchie wrote:I always thought bubble sort/sinking sort needs two for loops, inside each other.

You are correct - they do! (if the code should be readable)

I think it is possible to do with only one for loop - but I don't want to read the code afterward.

[Campbell Ritchie]

A bubble sort with only one loop? That sounds interesting. I never knew that was possible.

[Rene Larsen]

I haven't tried to coded a sort with just one for loop - but with some "spaghetti code", it should be possible (to do a bubble sort with recursive calls are also possible - with only one for loop, but it wasn't what I was thinking about).

But then you are right - it will no longer be a bubble sort, if it is done with "spaghetti code"

[Campbell Ritchie]

You mean a spaghetti sort? That sounds like a new algorithm, which ought to be published

[Hunter McMillen]

Would that spaghetti code actually improve the performance of the sort? Or would the one-loop bubble sort still be O(n**2)?

Hunter

[Campbell Ritchie]

So much better if it runs in O(n^3) time. Then you can say it is something really new and get a better publication

[Rene Larsen]

Hunter McMillen wrote:Would that spaghetti code actually improve the performance of the sort? Or would the one-loop bubble sort still be O(n**2)?

Hunter

If you look in the java.util.Array.java source file - http://kickjava.com/src/java/util/Arrays.java.htm - you will see that there is not only one implementation of a sort - it depends on the size of the array to sort.

A small array where the size is < 7 - is a bubble sort.

[Campbell Ritchie]

Yes, even though bubble sort runs in quadratic time, it is faster than merge sort (which is used for larger arrays) for sorting very small arrays.

[Hunter McMillen]

My question was if you managed to implement bubble sort with one for loop wouldn't that make it O(n) instead of O(n**2) ? So shouldn't it be more effective at sorting.


Hunter

[Campbell Ritchie]

If it really is bubble sort still, it will surely still run in quadratic time. I should be very interested to see how it is implemented with a single loop.