I'm trying to implement a Shell Sort. Understanding that Shell Sort breaks down the sort into segmented insertion I use a value of 10 that is first divided into 5 to start the first segmentation. Then 2 for the second segmentation, then 1 for the last segmentation. The problem lies in the last segmentation of 1. The first element of the array does not get checked by the if statement. When using an array of size 12, array[0], and array[10-11] find themselves not sorted. I can't seem to find the right starting point for my for loop, or while loop, that is in the segmented insertion sort. Array of 10 unsorted: 10 9 8 7 6 5 4 3 2 1 Sorted: 10 1 2 3 4 5 6 7 8 9 Array of 12 unsorted: 12 11 10 9 8 7 6 5 4 3 2 1 Sorted: 12 1 2 3 4 5 6 7 8 9 10 11 edit:: I don't think the problem lies in the segmentation aspect. Seeing as the final segment gap for sorting is 1. n = size; h = segment;
public int SegmentedInsertionSort(IntegerType[] A, int n, int h)
{
IntegerType temp;
System.out.println("Entered Segmeted InsertionSort");
for(int -> h+1 to n)
{
int j = i -h;
while( j > 0)
{
if (A[j].isBetterThan(A[j+h]))
{
System.out.println("Swap");
temp = A[j+h];
A[j+h] = A[j];
A[j] = temp;
j=j-h;
}else
{
System.out.println("Ever?");
j = 0;
}
}
System.out.println("Segmenting");
}System.out.println("outter loop done"); return h;
}
public void ShellSort(IntegerType[] A, int size)
{
int H = (size/2);
System.out.println("Entering Shell Sort");
while(H > 0)
{
SegmentedInsertionSort(A, size, H);
H = H/2;
}
}