Shell Sort in Java

Dalam postingan kali ini, saya akan menjelaskan secara sederhana tentang Shell Sort atau penyortiran shell.

Apa itu Shell sort?

Shell Sort
adalah pengurutan yang dilakukan di tempat. Shell sort bisa di generalisasikan dengan Bubble sort yang mengurutkan dengan pertukaran, atau Insertion sort yang mengurutkan dengan melakukan penambahan. Langkahnya dimulai dengan mengurutkan 2 elemen paling jauh dari semuanya, lalu mengecilkan jarak dari keduanya. Dimulai dengan elemen-elemen yang berjauhan, shell sort bisa menyortir elemen yang berada diluar untuk menuju posisi seharusnya dengan lebih cepat dan simpel daripada Bubble sort. Kata "Shell" diambil dari nama pencetusnya yaitu, Donald Shell, beliau mencetuskan versi pertama dari penyortiran ini pada 1959. Lama prosesnnya penyortiran ini sangat bergantung pada jarak urutan yang akan di sortir. Makin besar jaraknya, maka akan semakin lama pula penyortirannya.

Deskripsi Shell Sort
Shellsort adalah generalisasi dari insertion sort yang bisa menukar tempat elemen yang berjauhan. Initinya adalah untuk mengurutkan elemen dimulai dari mana saja. Disebut juga dengan metoda pertambahan menurun (diminishing increment). Pada langkah pertama, ambil elemen pertama dan kita bandingkan dengan elemen pada jarak terjauh dari elemen pertama tersebut. Kemudian elemen kedua dibandingkan dengan elemen lain dengan jarak yang sama. Demikian seterusnya sampai seluruh elemen terbandingkan.

Cara kerja Shell Sort bisa diterangkan dengan gambar dibawah ini :

Flowchart Shell sort
berikut gambar flowchart dari Shell sort :

Implementasi di Java
Dan berikut adalah source code pengimplementasiannya di Java :

import java.util.*;

public class ShellSort{

  public static void sort(int[] array) {

    int inner, outer;

    int temp;

    int h = 1;

    while (h <= array.length / 3) {

      h = h * 3 + 1;

    }

    while (h > 0) {

      for (outer = h; outer < array.length; outer++) {

        temp = array[outer];

        inner = outer;

        while (inner > h - 1 && array[inner - h] >= temp) {

          array[inner] = array[inner - h];

          inner -= h;

        }

        array[inner] = temp;

      }

      h = (h - 1) / 3;

    }

  }

  public static void main(String[] args) {

    int [] array = {5,3,0,2,4,1,0,5,2,3,1,4};

    System.out.println("Before: " + Arrays.toString(array));

    sort(array);

    System.out.println("After:  " + Arrays.toString(array));

  }

}

Hasil outputnya akan seperti dibawah ini :

Java Shell Sort :

Before: [5, 3, 0, 2, 4, 1, 0, 5, 2, 3, 1, 4]

After:  [0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]