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