|
||||||
| Java Tutorials Tutorials and Code for Java |
![]() |
|
|
LinkBack | Thread Tools | Search this Thread | Display Modes |
|
||||
|
Sorting Arrays
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: Code:
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();
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: Code:
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);
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: Code:
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;
}
}
Now we are going to create an array of nums with random numbers. Code:
nums[] aroNums = new nums[10];
for (int i=0;i<10;i++) {
aroNums[i] = new nums((int)(Math.random()*10)+5);
}
Code:
for (int i=0;i<aroNums.length;i++) {
System.out.print(aroNums[i].i + " ");
}
System.out.println();
Quote:
Try this problem out: London Knights. This is an exercise in sorting objects. |
|
||||
|
Re: Sorting Arrays
Great tutorial! +rep
__________________
Questions and Answers | Online News and Social Bookmarking | Code and Text Collaboration General Chat Forum |
|
||||
|
Re: Sorting Arrays
You said it's O(n log n). Is that average, worst case, other? +rep
![]()
__________________
CodeCall Blog | CodeCall Wiki | Shareware Programming is a branch of mathematics. My CodeCall Blog | My Personal Blog |
|
||||
|
Re: Sorting Arrays
It's probably QuickSort, then
![]()
__________________
CodeCall Blog | CodeCall Wiki | Shareware Programming is a branch of mathematics. My CodeCall Blog | My Personal Blog |
|
||||
|
Re: Sorting Arrays
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.
__________________
CodeCall Blog | CodeCall Wiki | Shareware Programming is a branch of mathematics. My CodeCall Blog | My Personal Blog |
![]() |
| Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
| Thread Tools | Search this Thread |
| Display Modes | |
|
|
Similar Threads
|
||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| Simple Arrays Sorting Help? | Puff | C and C++ | 17 | 08-15-2009 03:23 PM |
| PHP Arrays | chili5 | PHP Tutorials | 7 | 05-22-2009 05:16 PM |
| Sorting Array's | ahmed | C and C++ | 9 | 12-03-2008 12:00 PM |
| Help regarding the sorting of arrays with flags! | Yuriy M | C and C++ | 3 | 10-12-2007 11:30 PM |
| Sorting Arrays | falco85 | PHP Forum | 5 | 08-23-2006 10:31 PM |
All times are GMT -5. The time now is 11:40 PM.
Amrosama.cc
Arekbulski.cc
Debtboy.cc
Guest.cc
Jaan.cc
James.cc
Mathx.cc
Tsz.cc
Vswe.cc