Sorting



Sorting is rearranging a list of items to be in order. There are many different algorithms for sorting. Some are fast and some are slow depending on the number of items that are being sorted. Most all algorithms are fast if you have a small number of items to sort. The problem with time comes when the list gets large.

Examples:


A Summary of Sorting Algorithms (wikipedia)







Sort        Big O (worst case)                 Big O (best case)                 Link  





Merge Sort    O(n*log2(n))  O(n*log2(n)) Merge 





Quick Sort    O(n2)  O(n*log2(n)) Quick





Bubble Sort    O(n2)  O(n) Bubble 





Selection Sort    O(n2)  O(n2) Selection 





Insertion Sort    O(n2)  O(n) Insertion 




		  






Example 1: Sorting an Array
String [] list = {"Tom", "Sue", "Adam"};
Arrays.sort(list);




Example 2: Sorting an ArrayList

ArrayList list = new ArrayList();

list.add("Tom");
list.add("Sue");
list.add("Adam");
etc.

Collections.sort(list);




Example 3: Writing your own sorts

// the following code shows a selection sort
 
for (int j = 0; j < n-1; j++) {
    /* find the min element in the unsorted a[j .. n-1] */
 
    /* assume the min is the first element */
    int iMin = j;
    /* test against elements after j to find the smallest */
    for (int i = j+1; i < n; i++) {
        /* if this element is less, then it is the new minimum */  
        if (a[i] < a[iMin]) {
            /* found new minimum; remember its index */
            iMin = i;
        }
    }
 
    if ( iMin != j ) {
        swap(a[j], a[iMin]);
    }
}