10.6

  1. 19 18 21 22 29 26 37
26 41 63 47 61 72 55
  2. 26 19 21 18 26 22 47
41 55 29 61 72 63 37
  3. 121, 364, 1093
  4. The last insertion sort will be very fast since data are almost sorted.
  5.  
    1.  
      public static int findK(int n)
{
   int k = 1;
   while (k * 3 + 1 < n)
      k = k * 3 + 1;
   return k;
}
    2.  
      public static int prevK(int k)
{
   return (k-1) / 3;
}
  6.  
    1.  
      public static void shellSort(int[] list)
{
   for (int k = findK(list.length); k > 0; k = prevK(k))
      for (int loop = 0; loop < k; loop++)
      {
         for (int top = k + loop; top < list.length; top += k)
         {
            int i;
            int item = list[top];
            for (i = top; i > 0 + loop && item < list[i-k]; i -= k)
               list[i] = list[i-k];
            list[i] = item;
         }     
      }
}
    2.  
      public static void testShellSort ()
{
   int testList[] = new int [500];
   System.out.println ("Original List");
   for (int i = 0 ; i < testList.length ; i++)
   {
      testList [i] = (int) (Math.random () * 1000);
      System.out.print (testList [i] + " ");
      if ((i + 1) % 10 == 0)
         System.out.println ();
   }


   shellSort (testList);
   System.out.println ();
   System.out.println ("Sorted List");
   for (int i = 0 ; i < testList.length ; i++)
   {
      System.out.print (testList [i] + " ");
      if ((i + 1) % 10 == 0)
         System.out.println ();
   }
}