The efficiency of a bubble sort may be improved by using a Shell sort. In this sort we do a series of bubble sorts on subsets of the data, starting with data extracted from remote parts of the list, a distance Range apart. After we have that subset ordered, we reduce Range by a factor of 2 and repeat the process until we do a final pass of the original bubble sort with Range equal to 1.
01: /* ShellSort 02: (C) Copyright 1999, 2003 Herbert J. Bernstein 03: All Rights Reserved 04: 05: Based in part in D. L. Shell, CACM 2, 1959, PP 30-32 06: */ 07: 08: public class ShellSort { 09: 10: // Sample of a Shell Sort 11: // H. J. Bernstein, 10 November 1999, rev 28 October 2003 12: 13: // Accepts sequence of names as strings and returns a sorted list 14: 15: 16: String Names[]; // The array of strings 17: int NameCount=0; // The count of strings 18: int NameCapacity=0; // The capacity of the array 19: 20: void add(String xstr) { 21: 22: // If the array is full, double the size 23: // and copy to the new array 24: 25: if(NameCount >= NameCapacity) { 26: if (NameCapacity == 0) { 27: NameCapacity = 1024; 28: Names = new String[NameCapacity]; 29: } else { 30: int ii; 31: int oldcap; 32: String [] xx; 33: oldcap = NameCapacity; 34: NameCapacity *= 2; 35: xx = Names; 36: Names = new String[NameCapacity]; 37: for (ii=0; ii < NameCount; ii++) { 38: Names[ii] = xx[ii]; 39: } 40: } 41: } 42: Names[NameCount] = xstr; 43: NameCount++; 44: return; 45: } 46: 47: String[] trim() { 48: int ii; 49: String [] xx; 50: 51: if (NameCount > 0) { 52: xx = Names; 53: Names = new String[NameCount]; 54: for (ii=0; ii < NameCount; ii++) { 55: Names[ii] = xx[ii]; 56: } 57: } else { 58: Names = null; 59: } 60: NameCapacity = NameCount; 61: return Names; 62: } 63: 64: 65: String[] SortNames( ) { 66: 67: // The actual sort, done case insensitive 68: // Just one comb per Range 69: 70: int Done; 71: int Range; 72: int Icount; 73: String Temp; 74: 75: Range = NameCount/2; 76: while ( Range > 0 ) { 77: do { 78: Done = 1; 79: for (Icount = Range; Icount < NameCount; Icount += Range ) { 80: if (Names[Icount-Range].compareToIgnoreCase(Names[Icount]) > 0) { 81: Temp = Names[Icount]; 82: Names[Icount] = Names[Icount-Range]; 83: Names[Icount-Range] = Temp; 84: Done = 0; 85: } 86: } 87: } while (Done != 1); 88: Range = Range/2; 89: } 90: 91: return trim(); 92: } 93: } 94:
Here is a client to test the Shell Sort taking strings from the command line
01: /* ShellSortClient 02: (C) Copyright 2003 Herbert J. Bernstein 03: All Rights Reserved 04: */ 05: 06: // A client to test the ShellSort class 07: // Sorts the arguments on the command line 08: 09: 10: public class ShellSortClient { 11: 12: public static void main (String [] args) { 13: int ii; 14: ShellSort ss; 15: String [] xs; 16: 17: ss = new ShellSort(); 18: 19: for (ii=0; ii < args.length; ii++) { 20: ss.add(args[ii]); 21: System.out.println("added "+args[ii]); 22: } 23: 24: xs = ss.SortNames(); 25: for (ii = 0; ii < xs.length; ii++) { 26: System.out.println(xs[ii]); 27: } 28: return; 29: } 30: } 31: 32: 33: 34: