Shellsort is a simple extension of insertion sort that gains speed by allowing e

Question

Shellsort is a simple extension of insertion sort that gains speed by allowing exchanges of entries that are far apart. It works by producing partially sorted arrays that can be efficiently sorted, eventually by insertion sort. The idea is to rearrange the array to give it the property that taking every hth entry (starting anywhere) yields a sorted sequence. Such an array is said to be h-sorted.

By h-sorting for some large values of h, we can move entries in the array long distances and thus make it easier to h-sort for smaller values of h. Using such a procedure for any increment sequence of values of h that ends in 1 will produce a sorted array. That is the essence of shellsort.

For this assignment, create your own Shellsort. Your output should be similar to:

> more test.txt
S O R T E X A M P L E

> java ShellSort < test.txt

A
E
E
L
M
O
P
R
S
T
X

Explanation / Answer

/******************************************************************************
* Compilation: javac Shell.java
* Execution: java Shell < input.txt
* Dependencies: StdOut.java StdIn.java
*   
* Sorts a sequence of strings from standard input using shellsort.
*
******************************************************************************/

public class Shell {

// This class should not be instantiated.
private Shell() { }

/**
* Rearranges the array in ascending order, using the natural order.
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {
int N = a.length;

// 3x+1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, ...
int h = 1;
while (h < N/3) h = 3*h + 1;

while (h >= 1) {
// h-sort the array
for (int i = h; i < N; i++) {
for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
exch(a, j, j-h);
}
}
assert isHsorted(a, h);
h /= 3;
}
assert isSorted(a);
}

/***************************************************************************
* sorting functions.
***************************************************************************/
  
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
  
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}

/***************************************************************************
* Check if array is sorted
***************************************************************************/
private static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++)
if (less(a[i], a[i-1])) return false;
return true;
}

// is the array h-sorted?
private static boolean isHsorted(Comparable[] a, int h) {
for (int i = h; i < a.length; i++)
if (less(a[i], a[i-h])) return false;
return true;
}

// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
}

/**
* Reads in a sequence of strings from standard input; Shellsorts them;
* and prints them to standard output in ascending order.
*/
public static void main(String[] args) {
String[] a = StdIn.readAllStrings();
Shell.sort(a);
show(a);
}

}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.