[METODE PENGURUTAN DATA]

 

·       Pengurutan berdasarkan dan penjagaan terurut (insert and keep sorted method)

A.   Insertion sort

Insertion sort adalah metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat. Insertion Sort dimulai dari data ke-2 kemudian disisipkan pada tempat yang sesuai. Data pada posisi pertama diandaikan memang sudah pada tempatnya. Ilustrasinya mirip seperti saat menyisipkan kartu di permainan kartu.

for (i = 1 ; i <= n - 1; i++)

{

 j = i;

 while ( j > 0 && data[j] < data[j-1])

 {

  temp      = data[j];

  data[j]   = data[j-1];

  data[j-1] = temp;

  j--;

 }

}

Contoh Program

 #include <stdio.h>

int main()
{
  int n, array[1000], c, d, t;

  printf("Enter number of elements\n");
  scanf("%d", &n);

  printf("Enter %d integers\n", n);

  for (c = 0; c < n; c++) {
    scanf("%d", &array[c]);
  }

  for (c = 1 ; c <= n - 1; c++) {
    d = c;

    while ( d > 0 && array[d] < array[d-1]) {
      t          = array[d];
      array[d]   = array[d-1];
      array[d-1] = t;

      d--;
    }
  }

  printf("Sorted list in ascending order:\n");

  for (c = 0; c <= n - 1; c++) {
    printf("%d\n", array[c]);
  }

  return 0;
}

    #include <iostream.h>
    #include <conio.h>
    main()
    {
        int i,j,n,data[10],simpan,min,posisi;
       cout<<"masukkan banyak data= ";cin>>n;
       for(i=1;i<=n;i++)
       {
        cout<<"data "<<i<<" = ";cin>>data[i];
       }
       for(i=1;i<n;i++)
       {
        for(j=i+1;j<=n;j++)
          {
                if(data[i]>data[j])
             {
                simpan=data[i];
                data[i]=data[j];
                data[j]=simpan;
             }
          }
       }
       cout<<"hasil= ";
       for(i=1;i<=n;i++)
        cout<<data[i]<<" ";
    
    getch();
    }  

B.   Tree sort

Metode sorting dengan cara membangun pohon biner dengan menampilkan 3 hasil output: PreOrder, InOrder, dan PostOrder.Konsep dasar dari tree sort adalah sebagaimana sebuah pohon, ada akar, batang, ranting, daun, dan sebagainya. Dalam tree sort ada istilah akar atau root dan daun atau leaf.

·       Pengurutan berdasarkan perbandingan (compation based sorting)

A.   Buble sort

Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.

Algoritma Bubble Sort

1. Membandingkan data ke-i dengan data ke-(i+1) (tepat bersebelahan). Jika tidak sesuai maka tukar (data ke-i = data ke-(i+1) dan data ke-(i+1) = data ke-i). Apa maksudnya tidak sesuai? Jika kita menginginkan algoritme menghasilkan data dengan urutan ascending (A-Z) kondisi tidak sesuai adalah data ke-i > data ke-i+1, dan sebaliknya untuk urutan descending (A-Z).
2. Membandingkan data ke-(i+1) dengan data ke-(i+2). Kita melakukan pembandingan ini sampai data terakhir. Contoh: 1 dgn 2; 2 dgn 3; 3 dgn 4; 4 dgn 5 … ; n-1 dgn n.
3. Selesai satu iterasi, adalah jika kita sudah selesai membandingkan antara (n-1) dgn n. Setelah selesai satu iterasi kita lanjutkan lagi iterasi berikutnya sesuai dengan aturan ke-1. mulai dari data ke-1 dgn data ke-2, dst.
4. Proses akan berhenti jika tidak ada pertukaran dalam satu iterasi.

keterangan:
- baris 5 -7    = adalah pendeklarasian variabel dan array yang akan digunakan
                         dalam program
- baris 10-13 = Proses inputan yang disimpan dalam array yang dilakukan
                         dalam perulangan
- baris 14-26 = Proses pengurutan antara elemen satu dengan yang lain dan
                         apabila elemen satu lebih kecil daripada elemen berikutnya
                         (mengurtkan besar ke kecil) maka proses pertukaran akan
                         terjadi pada pada baris 23- 25.
- baris 29-32 = Setelah pengurutan berhasil maka nilai akan dicetak/
                         ditampilkan pada baris ini.


Maka apabila di compile maka hasilnya akan menjadi : 

Bagi yang ingin mencoba berikut kodingan:
#include<iostream>
using namespace std;

int main()
{   int a,k,c,d,g;
    k=4;
    int b[4];

    cout<<"BUBBLE SORT BY ZEFTAADETYA.BLOGSPOT.COM"<<endl;
    cout<<"mengurutkan nilai dari besar ke kecil"<<endl<<endl;
    for(a=0;a<k;a++)
    {
        cout<<"Masukkan nilai "<<a+1<<" : ";cin>>b[a];
    }
    for(a=0;a<k-1;a++)
    {

        for(d=a+1;d<k;d++)
        {
        c=a;
            if(b[c]<b[d])
            {
                c=d;
            }
        g=b[c];
        b[c]=b[a];
        b[a]=g;
        }

    }
    cout<<"\n setelah diurutkan akan menjadi : \n";
    for(a=0;a<k;a++)
    {
        cout<<b[a]<<" \n";
    }
}

B.   Exchange sort

Pada exchange sort cara kerjanya adalah dengan mengurutkan data yang ada dengan cara membandingkan tiap elemen, lalu dilakukan penukaran bila perlu.

Berikut codingnya :

#include <stdio.h>

#include <conio.h>

main()

{

int input;

int data[10],data2[10];

int i,j,x;

clrscr();

tengah("===Program Exchange Sort===",2);

printf("\nInputkan Jumlah Data : ");scanf("%d",&input);

for(i=1;i<=input;i=i+1)

{printf("Masukkan Nilai ke %d : ",i);scanf("%d",&data[i]);}

data2[i]=data[i];

·       Pengurutan berdasarkan prioritas(priority queque sorting method)

A.  Selection sort

Selection short adalah tehnik pengurutan dengan cara memilih elemen atau proses kerja dengan cara memilih elemen terkecil untuk kemudian dibandingkan & ditukarkan dengan elemen data awal dab seterusnya sampai dengan seluruh elemen,sehingga akan menghasilkan pola data yang telah di short.

Prinsip kerja selection short:

1. Pengecekan dimulai data ke-1 sampai dengan data ke-n

2. Tentukan bilangan dengan Index terkeci dari data bilangan tersebut
3. Tukar bilangan dengan Index terkecil tersebut dengan bilangan pertama ( I = 1 ) dari data bilangan tersebut
4. Lakukan langkah 2 dan 3 untuk bilangan berikutnya ( I= I+1 ) sampai didapatkan urutan yg optimal

Berikut programnya :

Dan ini hasil dari program di atas...

B.   Heap sort

               heapsort adalah algoritma sorting-perbandingan berbasis. Heapsort dapat dianggap sebagai peningkatan semacam seleksi: seperti algoritma itu, membagi input menjadi diurutkan dan wilayah disortir, dan iteratif menyusut wilayah disortir dengan mengekstraksi elemen terbesar dan bergerak yang ke wilayah diurutkan. Peningkatan tersebut terdiri dari penggunaan struktur data tumpukan daripada pencarian linear-waktu untuk menemukan maksimal. Meskipun agak lambat dalam praktek pada kebanyakan mesin dari quicksort yang dilaksanakan, ini memiliki keunggulan yang lebih menguntungkan terburuk O (n log n) runtime. Heapsort adalah algoritma di tempat, tapi itu bukan semacam stabil. Heapsort diciptakan oleh JWJ Williams pada tahun 1964. Hal ini juga kelahiran tumpukan, disajikan sudah oleh Williams sebagai struktur data yang berguna dalam dirinya sendiri. Pada tahun yang sama, RW Floyd menerbitkan sebuah versi perbaikan yang bisa mengurutkan array di tempat, melanjutkan penelitian sebelumnya ke dalam algoritma Treesort. Algoritma heapsort sendiri memiliki O (n log n) kompleksitas waktu baik menggunakan versi heapify. 

procedure heapify(a,count) is

(end is assigned the index of the first (left) child of the root)

     end := 1

     while end < count

         (sift up the node at index end to the proper place such that all nodes above

          the end index are in heap order)

         siftUp(a, 0, end)

         end := end + 1

     (after sifting up the last node all nodes are in heap order)

 procedure siftUp(a, start, end) is

     input:  start represents the limit of how far up the heap to sift.

                   end is the node to sift up.

     child := end 

     while child > start

         parent := floor((child-1) / 2)

         if a[parent] < a[child] then (out of max-heap order)

             swap(a[parent], a[child])

             child := parent (repeat to continue sifting up the parent now)

         else

             return

·       Pengurutan berdasarkan pembagian  dan penguasaan(devide and conquer method)

A.   Quick sort

Teknik sorting ini dibuat dengan cara yang menggunakan partisi. Pada teknik ini, data dibagi menjadi dua bagian, yaitu data disebelah kiri partisi selalu lebih kecil dari data disebelah kanan. Namun data pada kedua patisi belum terurut, sehingga untuk mengurutkannya, proses pengurutan dilakukan pada kedua partisi secara terpisah. Selanjutnya, data di sebelah kiri dan kanan dipartisi lagi.Merupakan proses penyusunan elemen yang membandingkan suatu elemen (pivot) denan elemen yang lain, dan menyusunnya sedemikian rupa sehingga elemen –elemen lain yang lebih kecil dari pivot terletak disebelah kiri pivot. Dan elemen yang lebih besar dari pivot terletak disebelah kanan pivot.Dengan demikian akan terbentuk dua sublist, yang terletak disebelah kanan dan kiri pivot.Lalu pada sublist kiri dan kanan itu kita anggap sebuah list baru, dan kita kerjakan proses yang sama seperti yang sebelumnya.Demikian seterusnya sampai tidak terdapat sublist lagi.

Contoh procedure quick sort secara ascending :

Procedure asc_quick (l , r :integer) ;

Var

i, j : integer;

begin

if l < r then

begin

i := l ;    j := r+1;

repeat

repeat inc (i) until data [i] >= data [l] ;

repeat dec (j) until data [j] <= data [l] ;

if i<j then tukardata (data [i], data [j]) ;

until i>j ;

tukardata (data [l], data [j] );

asc_quick (l, j-1);

asc_quick (j+1, r);

end;

end;

B.   Merge sort

Merge sort adalah sort yang dilakukan dengan teknik merge (menggabungkan) dua buah array kedalam sebuah array yang baru. Algoritma merge sort membagi tabel menjadi dua tabel yang sama besar. Masing-masing tabel diurutkan secara rekursif, dan kemudian digabungkan kembali untuk membentuk tabel yang terurut. Implementasi dasar dari algoritma merge sort memakai tiga buah tabel, dua untuk menyimpan elemen dari tabel yang telah di bagi dua dan satu untuk menyimpan elemen yang telah terurut. Namun algoritma ini dapat juga dilakukan langsung pada dua tabel, sehingga menghemat ruang atau memori yang dibutuhkan.

·       Pengurutan berkurang menurun (diminishing increment sort method)

A.   Shell sort (pengembangan insertion)

Shell sort merupakan Metode Pertambahan Menurun yang dikembangkan oleh Donald L. Shell (1959). Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu sehingga dibentuk sub-list, kemudian dilakukan pertukaran jika diperlukan.

# Sort an array a[0...n-1].

gaps = [701, 301, 132, 57, 23, 10, 4, 1]

                               

# Start with the largest gap and work down to a gap of 1

foreach (gap in gaps)

{

    # Do a gapped insertion sort for this gap size.

    # The first gap elements a[0..gap-1] are already in gapped order

    # keep adding one more element until the entire array is gap sorted

    for (i = gap; i < n; i += 1)

    {

        # add a[i] to the elements that have been gap sorted

        # save a[i] in temp and make a hole at position i

        temp = a[i]

        # shift earlier gap-sorted elements up until the correct location for a[i] is found

        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)

        {

            a[j] = a[j - gap]

        }

        # put temp (the original a[i]) in its correct location

        a[j] = temp

    }

}