java - シェルソートJavaの例

Question

シェルソートの例を教えてもらえますか？私はここでシェルソートについて学ばなければならない新しい人ですが、最初にJavaシェルソートの例を見つけなければなりません。Googleで1つの例を見つけましたが、それは難しすぎます。

Answer 1

ここで、このコードは非常に単純です:

/**
   * Shellsort, using Shell’s (poor) increments.
   * @param a an array of Comparable items.
   */
  public static <T extends Comparable<? super T>>
  void shellsort( T [ ] a )
  {
    int j;
    for( int gap = a.length / 2; gap > 0; gap /= 2 )
    {
      for( int i = gap; i < a.length; i++ )
      {
         T tmp = a[ i ];
         for( j = i; j >= gap && tmp.compareTo( a[ j - gap ] ) < 0; j -= gap )
         {
           a[ j ] = a[ j - gap ];
         }
         a[ j ] = tmp;
      }
    }
  }

Data Structures and Algorithm Analysis in Javaという本から盗み出しました。とてもわかりやすい良書です。読むことをお勧めします。

Answer 2

おそらく、このJavaコードが役に立ちます。

 public class ShellSort {
       private long[] data;

      private int len;

      public ShellSort(int max) {
        data = new long[max];
        len = 0;
      }

      public void insert(long value){
        data[len] = value; 
        len++;
      }

      public void display() {
        System.out.print("Data:");
        for (int j = 0; j < len; j++)
          System.out.print(data[j] + " ");
        System.out.println("");
      }

      public void shellSort() {
        int inner, outer;
        long temp;
        //find initial value of h
        int h = 1;
        while (h <= len / 3)
          h = h * 3 + 1; // (1, 4, 13, 40, 121, ...)

        while (h > 0) // decreasing h, until h=1
        {
          // h-sort the file
          for (outer = h; outer < len; outer++) {
            temp = data[outer];
            inner = outer;
            // one subpass (eg 0, 4, 8)
            while (inner > h - 1 && data[inner - h] >= temp) {
              data[inner] = data[inner - h];
              inner -= h;
            }
            data[inner] = temp;
          }
          h = (h - 1) / 3; // decrease h
        }
      }

      public static void main(String[] args) {
        int maxSize = 10;
        ShellSort arr = new ShellSort(maxSize);

        for (int j = 0; j < maxSize; j++) {
          long n = (int) (java.lang.Math.random() * 99);
          arr.insert(n);
        }
        arr.display();
        arr.shellSort();
        arr.display();
      }
    }

Answer 3

シェルソートは、いくつかの位置のギャップによって分離された要素を比較することにより、挿入ソートを改善します。

これにより、要素は期待される位置に向かって「より大きな一歩」を踏み出すことができます。データに対する複数のパスが、ギャップ サイズがどんどん小さくなっていきます。シェル ソートの最後のステップは単純な挿入ソートですが、それまでに、データの配列はほぼソートされていることが保証されます。

このコードは、ロジックをよりよく理解するのに役立つ場合があります。

package Sorts;
public class ShellSort extends Sorter{

@Override
public <T extends Comparable<? super T>> void sort(T[] a) {
    int h = 1;
    while((h*3+1) < a.length)
        h = 3*h+1;
    while(h > 0){
        for(int i = h-1; i < a.length; i++){
            T s = a[i];
            int j = i;
            for(j = i; (j>=h) && (a[j-h].compareTo(s) > 0); j-=h)
                a[j] = a[j-h];
            a[j] = s;
        }
        h /= 3;
    }
}
}

Answer 4

これは、Python 実装のシェル ソートを視覚化したものです。

def exch(a,i,j):
  t = a[i]
  a[i] = a[j]
  a[j] = t

def shellsort(string):
  print string
  a = list(string)
  N = len(a)
  h = 1
  i = 0
  j = 0
  k = 0
  #determine starting stride length
  while ( h < N/3 ):
    h = 3*h + 1
  print "STRIDE LENGTH: " + str(h)
  while (h >=1):
    i = h
    while i < N:
      j = i
      k = j - h
      while j >= h and a[j] < a[j-h]:
        k = j - h
        exch(a,j,k)
        j -= h
      i += 1
    h = h/3
    print "STRIDE LENGTH: " + str(h)
  print ''.join(a)·


if __name__ == '__main__':
    shellsort("astringtosortwithshellsort")

Answer 5

次に例を示します。

public static void shellsort( Comparable [ ] a )
    {
        for( int gap = a.length / 2; gap > 0;
                     gap = gap == 2 ? 1 : (int) ( gap / 2.2 ) )
            for( int i = gap; i < a.length; i++ )
            {
                Comparable tmp = a[ i ];
                int j = i;

                for( ; j >= gap && tmp.compareTo( a[ j - gap ] ) < 0; j -= gap )
                    a[ j ] = a[ j - gap ];
                a[ j ] = tmp;
            }
    }

Answer 6

古典的なプリミティブ型の実装:

package math;

import java.util.Arrays;

public class Sorter{

    public static void main(String []args){
        int[] a = {9,8,7,6,5,4,3,2,1};//plz use sophisticated random number generator
        System.out.println( Arrays.toString(a) );
        System.out.println( Arrays.toString(shellSort(a)) );
    }

    //Performs a shell sort on an array of ints.
    public static int[] shellSort(int[] array){
        int h = 1;
        while (h < array.length) h = 3*h + 1;
        while (h > 0){
            h = h/3;
            for (int k = 0; k < h; k++){
                for (int i = h+k; i < array.length; i+=h){
                    int key = array[i];
                    int j = i-h;
                    while (j>=0 && array[j] > key){
                        array[j+h] = array[j];
                        j-=h;
                    }
                    array[j+h] = key;
                    //-> invariant: array[0,h,2*h..j] is sorted
                }
            }
            //->invariant: each h-sub-array is sorted
        }
        return array;
    };
}

PS:他の並べ替えアルゴリズムについては、このリンクを確認してください (これらは c++ ですが、Java に簡単に移植できます)。

Answer 7

package sort_tester;

public class ShellSorter extends Sorter {

private final int[] gapArray = {1750,701,301,132,57,23,10,4,1};

@Override
public void makeSort (boolean trace) {

    int size = list.length;
    int i,j, temp;

    for ( int gap : gapArray ) {

        i = gap;

        while ( i < size ) {
            temp = list[i];
            j = i-gap;
            while ( j >= 0 && list[j] > temp ) {
                list[j + gap] = list[j];
                j -= gap;
            }
            list[j + gap] = temp;
            i ++;
        }
    }
}
}

リスト - int[]; Marcin Ciura の北極から取得した GapArray http://sun.aei.polsl.pl/~mciura/publikacje/shellsort.pdf