Sorting Arrays

[chili5]

Sorting Arrays

In some cases, you might want to sort an array. It might be an array of objects or a primitive array. Either way you can use the java.util.Arrays class to sort the array.

This method uses a modified quick sort algorithm that runs in 0(nlogn) time. This is considerably faster than bubble sort and other sort algorithms.

The java.util.Arrays class defines a static sort method for each primitive data type and a method that takes an array of type Object. This allows you to sort an array of any data type you want.

This method is a void method because arrays are based by reference. Thus if the array is modified in the function, then the array is modified outside of the function as well. If you want to retain the array, you must use the Arrays.copyOf method to make a copy of it before you pass it to the sort method.

Examples of sorting:

int[] v = {3,2,7,4,-1,5};
long[] l = {3,2,5,4,3,2,5,9};
String[] names = {"James","bob","test"};

Arrays.sort(v);
Arrays.sort(l);
Arrays.sort(names);

for (int i=0;i<v.length;i++) {
       System.out.print(v[i] + " ");
}
System.out.println();

for (int i=0;i<l.length;i++) {
            System.out.print(l[i] + " ");
}
System.out.println();

for (int i=0;i<names.length;i++) {
      System.out.print(names[i] + " ");
}
System.out.println();

The for loops are to show you the output to notice, that the arrays are now in ascending order. The String sort takes a bit more explanation though. The strings are sorted by there unicode values. Which is a value for the string by adding all the ASCII values for each character together.

I'm a bit disappointed in this class that it defines a sort method for each data type. It would be much more maintainable if it used a generic method. However, generic methods don't work with primitives to they are left with no choice.

Example of sorting and retaining the original array:

int[] v = {3,2,5,7,9,2,4};
int[] copy = v.clone();

// Now we can pass the array to the method
Arrays.sort(v);

This allows you to retain the original array, and get a copy that is sorted.

If you don't know how I copied the array, see my tutorial here: Copying Arrays.

Comparator

To sort objects of a programmer defined data type the data type you supporting must implement the Comparable interface.

Let us first define a class that we can use:

class nums {
    int i;

    nums(int i) {
        this.i = i;
    }

public int compareTo(Object o) {
        nums temp = (nums)o;

        if (temp.i < i) {
            return 1;
        } else if (temp.i == i) {
            return 0;
        }
        return -1;

    }
}

The compareTo method takes an object to compare with and returns 1 if the passed object's i value is less than the other object's i value. It will return 0 if they are equal and -1 otherwise. This is all the Arrays.sort method needs.

Now we are going to create an array of nums with random numbers.

nums[] aroNums = new nums[10];

 for (int i=0;i<10;i++) {
      aroNums[i] = new nums((int)(Math.random()*10)+5);
}

First we allocate an array of 10 nums and then initialize 10 objects. Now if you call Arrays.sort by passing aroNums the array will be sorted based on the i values.

for (int i=0;i<aroNums.length;i++) {
        System.out.print(aroNums[i].i + " ");
}
System.out.println();

Output:

5 5 5 6 10 11 12 14 14 14

This comes in handy with different programming problems, and in the implementation of different data structures.


Try this problem out:
London Knights. This is an exercise in sorting objects.

[Jordan]

Great tutorial! +rep

[Turk4n]

Wow, fun thing to try out thanks !
Also gr8 tutorial
rep+

[WingedPanther]

You said it's O(n log n). Is that average, worst case, other? +rep

[chili5]

Average. In the worst case it is 0(n^2).

[WingedPanther]

It's probably QuickSort, then

[chili5]

I know it is QuickSort. One thing I don't get is why it is 0(nlogn) and sometimes 0(n^2). I read about quick sort in a book and thought huh?

I got merge sort but quick sort makes no sense to me.

The naming conventions in the Arrays class suck. They have methods: sort, sort1, sort2, etc...

The sort method is:

private static void sort1(int x[], int off, int len) {
	// Insertion sort on smallest arrays
	if (len < 7) {
	    for (int i=off; i<len+off; i++)
		for (int j=i; j>off && x[j-1]>x[j]; j--)
		    swap(x, j, j-1);
	    return;
	}

	// Choose a partition element, v
	int m = off + (len >> 1);       // Small arrays, middle element
	if (len > 7) {
	    int l = off;
	    int n = off + len - 1;
	    if (len > 40) {        // Big arrays, pseudomedian of 9
		int s = len/8;
		l = med3(x, l,     l+s, l+2*s);
		m = med3(x, m-s,   m,   m+s);
		n = med3(x, n-2*s, n-s, n);
	    }
	    m = med3(x, l, m, n); // Mid-size, med of 3
	}
	int v = x[m];

	// Establish Invariant: v* (<v)* (>v)* v*
	int a = off, b = a, c = off + len - 1, d = c;
	while(true) {
	    while (b <= c && x[b] <= v) {
		if (x[b] == v)
		    swap(x, a++, b);
		b++;
	    }
	    while (c >= b && x[c] >= v) {
		if (x[c] == v)
		    swap(x, c, d--);
		c--;
	    }
	    if (b > c)
		break;
	    swap(x, b++, c--);
	}

	// Swap partition elements back to middle
	int s, n = off + len;
	s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
	s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);

	// Recursively sort non-partition-elements
	if ((s = b-a) > 1)
	    sort1(x, off, s);
	if ((s = d-c) > 1)
	    sort1(x, n-s, s);
    }

I just don't get how it works at all. This code is nothing like the code in my book.

Is it 0(n^2) in the worst case because of the insertion sort? I don't know.

[WingedPanther]

Many sort algorithms have a variable performance depending on the order the data is in. Bubble sorts are O(n) on sorted data, for example (assuming there's a bailout when no swaps are made).

Quicksort get's O(n^2) when the data is REVERSED (if I recall correctly). Heap-sort avoids this problem. C++ uses a mixture of methods depending on the data being sorted.

[MathX]

Very Very Nice

[Benbo]

Very nice, +rep