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: