Insertion Sort dan Implementasinya
Dalam kebanyakan kasus insertion sort adalah yang terbaik dari jenis dasar dijelaskan dalam bab ini. Masih mengeksekusi dalam O (N2) waktu, tetapi ini tentang dua kali lebih cepat sebagai bubble sort dan agak lebih cepat dari selection sort dalam situasi normal. Ini juga tidak terlalu rumit, meskipun itu sedikit lebih terlibat daripada macam gelembung dan seleksi. Ini sering digunakan sebagai tahap akhir dari jenis yang lebih canggih, seperti quickSort. Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.
Berikut Algoritma dari pada Insertion Sort.
public void insertionSort()
{
int in, out;
for(out=1; out
{
long temp = a[out];
in = out;
while(in>0 && a[in-1] >= temp)
{
a[in] = a[in-1];
--in;
}
a[in] = temp;
}
}
Dan berikut Implementasi ke programnya.
public class ArrayIns
{
private long[] a;
private int nElems;
public ArrayIns(int max) // constructor
{
a = new long[max]; // membuat array
nElems = 0; // Belum ada nilai
}
public void insert(long value) // Msukan nilai array
{
a[nElems] = value; // masuk kan disini
nElems++; // ukuran increment
}
public void display() // menampilkan array
{
for(int j=0; j // perulangan element
System.out.print(a[j] + " "); // menampilkan
System.out.println("");
}
public void insertionSort()
{
int in, out;
for(out=1; out
{
long temp = a[out];
in = out;
while(in>0 && a[in-1] >= temp)
{
a[in] = a[in-1];
--in;
}
a[in] = temp;
}
}
} // Penutup class Terakhir arr
class InsertSortApp
{
public static void main(String[] args)
{
int maxSize = 100; // ukuran array
ArrayIns arr; // acuan ke array
arr = new ArrayIns(maxSize); // membuat array dengan nama arr
arr.insert(10); // masukkan 10 nilai
arr.insert(3);
arr.insert(4);
arr.insert(5);
arr.insert(2);
arr.insert(8);
arr.insert(1);
arr.insert(6);
arr.insert(7);
arr.insert(0);
arr.display(); // menampilkan arr
arr.insertionSort(); // insertion-sort lagi
arr.display(); // Menampilakan array lagi
} // tanda penutup main ()
} // tanda penutup pada insertsort
0 komentar:
Posting Komentar