Shell sort

Language: English
Programming Language: Java
Published by: laur72_98 [not registered]
Last Update: 5/15/2006
Views: 284

Description

Part of Sorters package

Code

Display line numbers

1 /* 2 * ShellSort.java 1.0 07/21/1999 Laurentiu Cristofor 3 * 4 * Copyright (c) 1999 Laurentiu Cristofor 5 * 6 * Permission to use, copy, modify, and distribute this software 7 * and its documentation for NON-COMMERCIAL or COMMERCIAL purposes and 8 * without fee is hereby granted provided that this copyright notice 9 * appears in all copies. 10 * 11 * I MAKE NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF 12 * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED 13 * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A 14 * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. I SHALL NOT BE LIABLE FOR 15 * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR 16 * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. 17 * */ 18 19 /** 20 * Implementation of the Shellsort algorithm (Donald L. Shell 1959). 21 * 22 * @author Laurentiu Cristofor 23 * @version 1.0, July 21st, 1999 24 * */ 25 public class ShellSort implements SortInterface 26 { 27 // helper method for shellSort 28 private static void deltaInsertionSort(SInteger[] A, 29 int left, int right, 30 int delta) 31 { 32 int i, j; 33 SInteger value = new SInteger(); 34 35 for (i = left + delta; i <= right; i += delta) 36 { 37 value.assign(A[i]); 38 39 for (j = i ; j > left 40 && value.compareTo(A[j - delta]) < 0; j -= delta ) 41 A[j].assign(A[j - delta]); 42 43 A[j].assign(value); 44 } 45 } 46 47 public void sort(SInteger[] A) 48 { 49 shellSort(A); 50 } 51 52 public static void shellSort(SInteger[] A) 53 { 54 shellSort(A, 0, A.length - 1); 55 } 56 57 public static void shellSort(SInteger[] A, int left, int right) 58 { 59 int delta = A.length; 60 61 do 62 { 63 // initially we take delta about one third 64 // the number of elements in the array A 65 delta = delta / 3 + 1; 66 67 for (int i = left; i < left + delta; i++) 68 deltaInsertionSort(A, i, right, delta); 69 } 70 while (delta > 1); 71 } 72 } 73

Shell sort

Description

Code

No comments avaiable

Add a comment