Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- returns 0 if a equal b
- returns -1 if a < b
- returns 1 if a > b
- public void sort(Comparable[] lst)
- {
- for(int i=0; i<lst.length; i++)
- {
- for(int j=i; j<lst.length; j++)
- {
- if(lst[i].compareTo(lst[j]) < 0)
- {
- //swap elements, sorts in ascending order
- Comparable tmp = lst[i];
- lst[i] = lst[j];
- lst[j] = tmp;
- }
- }
- }
- }
- private static <T> void binarySort(T[] a, int lo, int hi, int start, Comparator<? super T> c) {
- assert lo <= start && start <= hi;
- if (start == lo)
- start++;
- for ( ; start < hi; start++) {
- T pivot = a[start];
- // Set left (and right) to the index where a[start] (pivot) belongs
- int left = lo;
- int right = start;
- assert left <= right;
- /*
- * Invariants:
- * pivot >= all in [lo, left).
- * pivot < all in [right, start).
- */
- while (left < right) {
- int mid = (left + right) >>> 1;
- if (c.compare(pivot, a[mid]) < 0)
- right = mid;
- else
- left = mid + 1;
- }
- assert left == right;
- /*
- * The invariants still hold: pivot >= all in [lo, left) and
- * pivot < all in [left, start), so pivot belongs at left. Note
- * that if there are elements equal to pivot, left points to the
- * first slot after them -- that's why this sort is stable.
- * Slide elements over to make room for pivot.
- */
- int n = start - left; // The number of elements to move
- // Switch is just an optimization for arraycopy in default case
- switch (n) {
- case 2: a[left + 2] = a[left + 1];
- case 1: a[left + 1] = a[left];
- break;
- default: System.arraycopy(a, left, a, left + 1, n);
- }
- a[left] = pivot;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement