Sorting an array of integers

[Dawid Smith]

Hello. I've given myself a task to come up with a way to sort an array of integers. It seems to be working fine but I would love to hear some feedback on it from you guys.

The solution works in the following way :
The nested loop compares each value of the array to every other value of the array.  It skips the comparison between values of the same index. There is a counter declared at the beginning of the nested loop which will increase every time a value being compared is found to be either smaller or equal to the other value.The value of the counter is then used to determine a relative position of the tested value and the value is assigned to an appriopriate index position to the newly created array. So, for example, if after all the comparisons the counter remains 0, then we know that the value being tested is the biggest one and it goes at the last index position of the newly created array.

Aside of a sorting method, there is also a printer method for testing purposes. It prints all the values of the arrays after the sorting is done. Other than that the methods can't handle exceptions and printer() could print the data in a nicer way but I think it would be best to try getting some feedback before putting more work into it.

Here is the code :

public class TestingClass
{
    public static void main(String args[])
    {
        int[][] ar = { {3,2,3,1}, {7,4,6}, {3,3}, {1,2,3}, {3,2,1} }; 
        ArraySortingMethods.printer(ar);
    }
}

class ArraySortingMethods
{
    private ArraySortingMethods()
    {
        //Private constructor made in order to prevent instantiation
    }
    static int[] sortingArrayOfInt(int[] numbers)
    {
        int[] sortedArray = new int[numbers.length];
        
        for(int i = 0; i < numbers.length; i++)
        {
            int counter = 0;
            
            for(int y = 0; y < numbers.length; y++)
            {
                if (i == y)
                {
                    continue;
                }    
                
                if (numbers[i] < numbers[y]) 
                {
                    counter++;
                }
               
                if (numbers[i] == numbers[y] & i > y) //it's necessary to test whether i is bigger than y to handle duplicate values in an array. Not doing so will result in assigning the duplicate value to the same index position in sortedArray
                {                                     
                    counter++;
                }
               
                
            }
            sortedArray[numbers.length - 1 - counter] = numbers[i];
        }
        return sortedArray;
    }
    
    static void printer(int[][] ar)
    {
        for(int i = 0; i < ar.length; i++)
        {
            System.out.print("{");  
            for(int x : sortingArrayOfInt(ar[i]) )
            {
                System.out.print(x + ", ");
            }
            System.out.print("} ");
        }
    }
}

[Carey Brown]

It would be interesting to see some performance numbers for very large arrays comparing your method to a simple bubble sort.
Your method has these nested loops

        for( int i = 0 ; i < numbers.length ; i++ )
        {
            for( int y = 0 ; y < numbers.length ; y++ )
            {

A bubble sort has these

        for( int i = 0 ; i < numbers.length-1 ; i++ )
        {
            for( int y = i+1 ; y < numbers.length ; y++ )
            {

Note the inner loop gets shorter and shorter as the outer loop progresses.

[Junilu Lacar]

Instead of writing your own printer() method, you could just use java.util.Arrays.toString() to display an int[]. To display nested arrays, you can use Arrays.deepToString()

[Dawid Smith]

Carey Brown wrote:It would be interesting to see some performance numbers for very large arrays comparing your method to a simple bubble sort.
Your method has these nested loops

        for( int i = 0 ; i < numbers.length ; i++ )
        {
            for( int y = 0 ; y < numbers.length ; y++ )
            {

A bubble sort has these

        for( int i = 0 ; i < numbers.length-1 ; i++ )
        {
            for( int y = i+1 ; y < numbers.length ; y++ )
            {

Note the inner loop gets shorter and shorter as the outer loop progresses.

How would you go about comparing performances of 2 methods?

[Dawid Smith]

Junilu Lacar wrote:Instead of writing your own printer() method, you could just use java.util.Arrays.toString() to display an int[]. To display nested arrays, you can use Arrays.deepToString()

Thank you for the suggestion. I didn't know that such methods exist. Still, what do you think about writing your own version just for practice? I imagine it seems supereasy for someone experienced but I had to think how to print those results

[Junilu Lacar]

If it's your first try, then it's a pretty good try. This algorithm, however, is quite inefficient. If I'm not mistaken, it is best case and worst case O(n²) which means that for large arrays, it takes a very long time, even if it's already sorted. You're basically looking through the entire list NxN times to find the largest unsorted element, including the elements that you've already looked at before and determined to be larger than all others.

Sorting algorithms are a basic area of study in computer science so I suggest you take a look at the various ones already existing and commonly used and compare them with yours to see what kind of improvements you might make.

[Junilu Lacar]

Dawid Smith wrote:I didn't know that such methods exist. Still, what do you think about writing your own version just for practice? I imagine it seems supereasy for someone experienced but I had to think how to print those results

It's good for practice. Once you know the mechanics of it though, you'll probably rather have something that's already been tried and tested. Kind of like how it might be fun to build your own bicycle from scratch but if you've already done it once and you just want to ride a bike, then I'd rather just go and buy one that's already pre-assembled. I've done that (assembled my own bike). Once.

[Carey Brown]

Here's some boiler plate, just do the same for your method. You'll have to play with the size you pass in to createRandomArray() to get an elapsed time from 1-4 minutes. Milliseconds should be sufficient granularity for this. No need to go with nano-time, but you could if you wanted to look into it.

import java.util.Arrays;
import java.util.Random;

public class PerformanceSort
{
	public static void main( String[] args )
	{
		long		start, stop;
		int[]		ary = createRandomArray( 300_000 );
		
		start = System.currentTimeMillis();
		bubbleSort( ary );
		stop = System.currentTimeMillis();
		System.out.printf( "Bubble sort elapsed seconds: %,.3f%n", (stop-start)/1000.0 );
		
		// copy-n-paste for your sort routine
	}
	
	static int[] bubbleSort( int[] aryIn )
	{
		// copy is not a part of standard bubble sort but is here
		// so that sort doesn't modify original ary
		int[]		ary = Arrays.copyOf( aryIn, aryIn.length );
		
		for( int i = 0 ; i < ary.length - 1 ; i++ )
		{
			for( int j = i + 1 ; j < ary.length ; j++ )
			{
				if( ary[j] < ary[i] )
				{
					int		tmp = ary[i];
					ary[i] = ary[j];
					ary[j] = tmp;
				}
			}
		}
		return ary;
	}
	
	static int[] createRandomArray( int size )
	{
		int[]		ary = new int[ size ];
		Random		rand = new Random();
		for( int i = 0 ; i < ary.length ; i++ )
			ary[i] = rand.nextInt();
		return ary;
	}
}

[Winston Gutkowski]

Dawid Smith wrote:Still, what do you think about writing your own version just for practice?

Nothing wrong with it at all; just don't expect too much in the way of enlightenment unless you repeat the process at least 10,000 times, or work with arrays involving millions of objects, which probably isn't very practical.

Java does things very quickly indeed, so the difference between one instruction (or technique) and another might be measured in picoseconds (thats 10⁻¹²), and since the best Java time counter (System.nanotime()) is good to about 1/100th of a second, if you're lucky, you're unlikely to get any meaningful information unless you're running your comparisons on very large samples.

I'm with Junilu - right now, you might get more mileage out of looking at sorting algorithms and working out why you might use them; but don't ignore the simple ones simply because they're supposedly "inefficient" (O(n²) or worse).

The technique you're using, for example, is very similar to a Selection sort, which is still used to sort small datasets ... although Insertion sort is usually quicker.

And in trawling Wikipedia, I was also reminded of Cycle sort, which is basically a "write-optimized" Insertion sort.
All these sorts are supposedly "slow", but they all have their uses, especially in hybrid algorithms that combine them with other, theoretically faster techniques, like Quicksort.

Hope it helps.

Winston

[Liutauras Vilda]

@OP

Very nicely indented and formatted code. Have a cow for disciplined approach on that.

[Campbell Ritchie]

Once you have passed all your exams and got a job, you will sort your array like this

Arrays.sort(myArray);

[Dawid Smith]

Junilu Lacar wrote:If it's your first try, then it's a pretty good try. This algorithm, however, is quite inefficient. If I'm not mistaken, it is best case and worst case O(n²) which means that for large arrays, it takes a very long time, even if it's already sorted. You're basically looking through the entire list NxN times to find the largest unsorted element, including the elements that you've already looked at before and determined to be larger than all others.

Sorting algorithms are a basic area of study in computer science so I suggest you take a look at the various ones already existing and commonly used and compare them with yours to see what kind of improvements you might make.

Now I can see the efficiancy problem with my method. Not that I expected it to be anywhere close in terms of performance to already existing solutions. Thank you

[Dawid Smith]

Winston Gutkowski wrote:

Dawid Smith wrote:Still, what do you think about writing your own version just for practice?

Nothing wrong with it at all; just don't expect too much in the way of enlightenment unless you repeat the process at least 10,000 times, or work with arrays involving millions of objects, which probably isn't very practical.

I am not sure if I understand your point. Do you mean that getting better by writing your own code takes crazy amount of time?

Winston Gutkowski wrote:I'm with Junilu - right now, you might get more mileage out of looking at sorting algorithms and working out why you might use them; but don't ignore the simple ones simply because they're supposedly "inefficient" (O(n²) or worse).

Thank you for the advice. Right now, my studying is heavily skewed towards writing my own stuff instead of looking up what's already out there. Maybe that's a mistake.

[Junilu Lacar]

Dawid Smith wrote:Right now, my studying is heavily skewed towards writing my own stuff instead of looking up what's already out there. Maybe that's a mistake.

Practice by writing code on your own. Expand your horizons and learn from others by studying how they solved the same problem.

[Dawid Smith]

Liutauras Vilda wrote:@OP

Very nicely indented and formatted code. Have a cow for disciplined approach on that.

Thank you. I am trying to make it easy to read.

Campbell Ritchie wrote:Once you have passed all your exams and got a job, you will sort your array like this

Arrays.sort(myArray);

But.. where would the fun be in that?

I get your point though, there are ready-made solutions for common problems.

[Campbell Ritchie]

Dawid Smith wrote:. . . But.. where would the fun be in that? . . .

A $40,000 starting salary?

[Dawid Smith]

Campbell Ritchie wrote:

Dawid Smith wrote:. . . But.. where would the fun be in that? . . .

A $40,000 starting salary?

Oh, that Still, there is so much to learn I haven't even started thinking about salaries yet

[Campbell Ritchie]

You are only allowed to start thinking about starting salaries; don' start thinking about non‑starting salaries or you will have a start.

[Piet Souris]

Campbell Ritchie wrote:Once you have passed all your exams and got a job, you will sort your array like this

Arrays.sort(myArray);

I bet not. What about sorting in descending order?

[Campbell Ritchie]

Arrays.sort(myArray, Comparator.reverseOrder());

Damn! It hasn't got that method. Piet has beaten me.

myNewArray =
    Arrays.stream(myArray)
          .boxed() // No comparator available for ints, only for Integers
          .sorted(Comparator.reverseOrder()) // Supplies Comparator<Integer>
          .mapToInt(Integer::intValue) // back to ints
          .toArray();

[Carey Brown]

A side topic here would be how to benchmark your program. It seems like sorting might be as good a place as any to compare benchmarks from various techniques. I would be interested to know how the streaming version compares to the Arrays.sort version, for instance.

[Mark Ii]

There is an optimized bubble sort. More efficient.

Here is the link.   webpage

import java.util.Arrays;

public class OptimizedBubbleSort {
    static void sort(int [] arrA){
        if(arrA==null || arrA.length==0)
            return;

        System.out.println("Original Array: " + Arrays.toString(arrA));
        boolean isSwapped;
        int size = arrA.length;
        for (int i = 0; i <size-1 ; i++) {
            isSwapped = false;
            for (int j = 0; j <size-i-1 ; j++) {
                //check the adjacent elements
                if(arrA[j]>arrA[j+1]){
                    //swap the elements
                    int temp = arrA[j];
                    arrA[j] = arrA[j+1];
                    arrA[j+1] = temp;
                    isSwapped = true;
                }
            }
            //check if any swapping occurred in last iteration
            //if yes then break the loop, array is sorted at this point
            if(isSwapped==false)
                break;
        }
        System.out.println("Sorted Array: " +  Arrays.toString(arrA));
    }

    public static void main(String[] args) {
        int [] arrA = {5, 1, 9, 3, 2, 10};
        sort(arrA);
        System.out.println("------------------------------");
        arrA = new int []{1, 2, 4, 6, 8, 10};
        sort(arrA);
    }
}