13c1e67e433728684b5f228c5d4f3e5b1457bb271sm/* 23c1e67e433728684b5f228c5d4f3e5b1457bb271sm * Copyright (C) 2010 The Android Open Source Project 33c1e67e433728684b5f228c5d4f3e5b1457bb271sm * 43c1e67e433728684b5f228c5d4f3e5b1457bb271sm * Licensed under the Apache License, Version 2.0 (the "License"); 53c1e67e433728684b5f228c5d4f3e5b1457bb271sm * you may not use this file except in compliance with the License. 63c1e67e433728684b5f228c5d4f3e5b1457bb271sm * You may obtain a copy of the License at 73c1e67e433728684b5f228c5d4f3e5b1457bb271sm * 83c1e67e433728684b5f228c5d4f3e5b1457bb271sm * http://www.apache.org/licenses/LICENSE-2.0 93c1e67e433728684b5f228c5d4f3e5b1457bb271sm * 103c1e67e433728684b5f228c5d4f3e5b1457bb271sm * Unless required by applicable law or agreed to in writing, software 113c1e67e433728684b5f228c5d4f3e5b1457bb271sm * distributed under the License is distributed on an "AS IS" BASIS, 123c1e67e433728684b5f228c5d4f3e5b1457bb271sm * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 133c1e67e433728684b5f228c5d4f3e5b1457bb271sm * See the License for the specific language governing permissions and 143c1e67e433728684b5f228c5d4f3e5b1457bb271sm * limitations under the License. 153c1e67e433728684b5f228c5d4f3e5b1457bb271sm */ 163c1e67e433728684b5f228c5d4f3e5b1457bb271sm 17cfd74d65d832137e20e193c960802afba73b5d38smpackage com.replica.replicaisland; 18cfd74d65d832137e20e193c960802afba73b5d38sm 19cfd74d65d832137e20e193c960802afba73b5d38smimport java.util.Comparator; 20cfd74d65d832137e20e193c960802afba73b5d38sm 21cfd74d65d832137e20e193c960802afba73b5d38smpublic class ShellSorter<Type> extends Sorter<Type> { 22cfd74d65d832137e20e193c960802afba73b5d38sm/** 23cfd74d65d832137e20e193c960802afba73b5d38sm * Shell sort implementation based on the one found here: 24cfd74d65d832137e20e193c960802afba73b5d38sm * http://www.augustana.ab.ca/~mohrj/courses/2004.winter/csc310/source/ShellSort.java.html 25cfd74d65d832137e20e193c960802afba73b5d38sm * Note that the running time can be tuned by adjusting the size of the increment used 26cfd74d65d832137e20e193c960802afba73b5d38sm * to pass over the array each time. Currently this function uses Robert Cruse's suggestion 27cfd74d65d832137e20e193c960802afba73b5d38sm * of increment = increment / 3 + 1. 28cfd74d65d832137e20e193c960802afba73b5d38sm */ 29cfd74d65d832137e20e193c960802afba73b5d38sm 30cfd74d65d832137e20e193c960802afba73b5d38smpublic void sort(Type[] array, int count, Comparator<Type> comparator) { 31cfd74d65d832137e20e193c960802afba73b5d38sm int increment = count / 3 + 1; 32cfd74d65d832137e20e193c960802afba73b5d38sm 33cfd74d65d832137e20e193c960802afba73b5d38sm // Sort by insertion sort at diminishing increments. 34cfd74d65d832137e20e193c960802afba73b5d38sm while ( increment > 1 ) { 35cfd74d65d832137e20e193c960802afba73b5d38sm for ( int start = 0; start < increment; start++ ) { 36cfd74d65d832137e20e193c960802afba73b5d38sm insertionSort(array, count, start, increment, comparator); 37cfd74d65d832137e20e193c960802afba73b5d38sm } 38cfd74d65d832137e20e193c960802afba73b5d38sm increment = increment / 3 + 1; 39cfd74d65d832137e20e193c960802afba73b5d38sm } 40cfd74d65d832137e20e193c960802afba73b5d38sm 41cfd74d65d832137e20e193c960802afba73b5d38sm // Do a final pass with an increment of 1. 42cfd74d65d832137e20e193c960802afba73b5d38sm // (This has to be outside the previous loop because the formula above for calculating the 43cfd74d65d832137e20e193c960802afba73b5d38sm // next increment will keep generating 1 repeatedly.) 44cfd74d65d832137e20e193c960802afba73b5d38sm insertionSort(array, count, 0, 1, comparator ); 45cfd74d65d832137e20e193c960802afba73b5d38sm } 46cfd74d65d832137e20e193c960802afba73b5d38sm 47cfd74d65d832137e20e193c960802afba73b5d38sm 48cfd74d65d832137e20e193c960802afba73b5d38sm/** 49cfd74d65d832137e20e193c960802afba73b5d38sm * Insertion sort modified to sort elements at a 50cfd74d65d832137e20e193c960802afba73b5d38sm * fixed increment apart. 51cfd74d65d832137e20e193c960802afba73b5d38sm * 52cfd74d65d832137e20e193c960802afba73b5d38sm * The code can be revised to eliminate the initial 53cfd74d65d832137e20e193c960802afba73b5d38sm * 'if', but I found that it made the sort slower. 54cfd74d65d832137e20e193c960802afba73b5d38sm * 55cfd74d65d832137e20e193c960802afba73b5d38sm * @param start the start position 56cfd74d65d832137e20e193c960802afba73b5d38sm * @param increment the increment 57cfd74d65d832137e20e193c960802afba73b5d38sm */ 58cfd74d65d832137e20e193c960802afba73b5d38smpublic void insertionSort(Type[] array, int count, int start, int increment, 59cfd74d65d832137e20e193c960802afba73b5d38sm Comparator<Type> comparator) { 60cfd74d65d832137e20e193c960802afba73b5d38sm int j; 61cfd74d65d832137e20e193c960802afba73b5d38sm int k; 62cfd74d65d832137e20e193c960802afba73b5d38sm Type temp; 63cfd74d65d832137e20e193c960802afba73b5d38sm 64cfd74d65d832137e20e193c960802afba73b5d38sm for (int i = start + increment; i < count; i += increment) { 65cfd74d65d832137e20e193c960802afba73b5d38sm j = i; 66cfd74d65d832137e20e193c960802afba73b5d38sm k = j - increment; 67cfd74d65d832137e20e193c960802afba73b5d38sm int delta = comparator.compare(array[j], array[k]); 68cfd74d65d832137e20e193c960802afba73b5d38sm 69cfd74d65d832137e20e193c960802afba73b5d38sm if ( delta < 0 ) { 70cfd74d65d832137e20e193c960802afba73b5d38sm // Shift all previous entries down by the current 71cfd74d65d832137e20e193c960802afba73b5d38sm // increment until the proper place is found. 72cfd74d65d832137e20e193c960802afba73b5d38sm temp = array[j]; 73cfd74d65d832137e20e193c960802afba73b5d38sm do { 74cfd74d65d832137e20e193c960802afba73b5d38sm array[j] = array[k]; 75cfd74d65d832137e20e193c960802afba73b5d38sm j = k; 76cfd74d65d832137e20e193c960802afba73b5d38sm k = j - increment; 77cfd74d65d832137e20e193c960802afba73b5d38sm } while ( j != start && comparator.compare(array[k], temp) > 0 ); 78cfd74d65d832137e20e193c960802afba73b5d38sm array[j] = temp; 79cfd74d65d832137e20e193c960802afba73b5d38sm } 80cfd74d65d832137e20e193c960802afba73b5d38sm } 81cfd74d65d832137e20e193c960802afba73b5d38sm } 82cfd74d65d832137e20e193c960802afba73b5d38sm} 83