Keamanan informasi: 2021

Pengertian Sorting pada C++

Salah satu bagian penting dari struktur data adalah proses pengurutan data. Data terkadang akan berada dalam bentuk yang tidak berpola ataupun dengan pola tertentu yang tidak kita inginkan. Namun dalam penggunaannya, kita akan selalu ingin menggunakan data tersebut dalam bentuk yang rapi atau berpola sesuai dengan yang kita inginkan. Maka dari itu proses sorting adalah proses yang sangat penting dalam struktur data. Proses pengurutan banyak ditemukan dalam pemrosesan komputer. Data yang sudah terurut memiliki beberapa keuntungan. Selain mempercepat pencarian, data yang sudah terurut juga dapat dengan mudah menentukan Nilai terbesar atau terkecil.

Pengurutan data memang sangat relevan dan merupakan aktivitas yang sangat penting berkaitan dengan pemrosesan data. Bahkan pengurutan data telah banyak dilakukan dengan bantuan alat. Adanya kebutuhan terhadap peroses pengurutan memunculkan bermacam-macam metode pengurutan yang bertujuan untuk memperoleh metode pengurutan yang optimal.

1. Definisi Sorting pada C++

Pengurutan (sorting) adalah proses mengatur sekumpulan objek menurut urutan atau susunan tertentu. Urutan objek tersebut dapat menaik (ascending), yaitu urutan objek yang disusun mulai dari Nilai terkecil hingga terbesar atau menurun (descending), yaitu urutan objek yang disusun mulai dari Nilai terbesar hingga terkecil. Jika N buah objek atau data disimpan di dalam array Nilai, maka pengurutan menaik berarti menyusun elemen array sedemikian sehingga:

NILAI[0] ≤ NILAI[1] ≤ NILAI[2] ≤ … ≤ NILAI[N-1]

Sedangkan pengurutan menurun berarti menyusun elemen array sedemikian sehingga:

NILAI[0] ≥ NILAI[1] ≥ … ≥ NILAI[N-1]

Data yang diurut dapat berupa data bertipe data dasar atau tipe data bentukan. Jika data bertipe bentukan (structure), maka harus disebutkan berdasarkan field apa data tersebut akan diurutkan.

Sama halnya dengan pencarian, pengurutan juga dibedakan menjadi dua kelompok, yaitu:

Pengurutan Internal, yaitu pengurutan terhadap sekumpulan data yang disimpan di dalam memori komputere. Umumnya struktur internal yang dipakai untuk pengurutan ini adalah array, sehingga pengurutan internal disebut dengan pengurutan array.
Pengurutan Eksternal, yaitu pengurutan data yang disimpan di dalam memori sekunder. Biasanya data dengan berjumlah besar sehingga tidak mampu dimuat semuanya dalam memori komputer. Struktur eksternal yang dipakai adalah arsip (file), maka pengurutan ini juga sering disebut dengan pengurutan arsip.

Karena pengaksesan memori utama lebih cepat dari pada pengaksesan memori sekunder, maka pengurutan internal lebih cepat dibanding dengan pengurutan eksternal.

Beberapa metode yang dapat digunakan untuk pengurutan antara lain:

Bubble Sort
Selection Sort
Quick Sort
Merge Sort
Heap Sort
Shell Sort
Radix Sort
Tree Sort
Maximum Sort
Insertion Sort

Banyaknya metode pengurutan yang tersedia menimbulkan pertanyaan: algoritma manakah yang memiliki kinerja yang baik? Kinerja pengurutan data sangat menentukan kinerja sistem, karena itu pemilihan metode pengurutan yang cocok akan berperan dalam suatu aplikasi. Metode pengurutan yang akan dibahas adalah metode pengurutan Bubble Sort, Quick Sort, Maximum/Minimum Sort, Shell Sort, Merge Sort, dan Insertion.

2. Bubble Sort

Bubble Sort adalah metode yang membandingkan elemen yang sekarang dengan elemen-elemen berikutnya. Pembandingan elemen dapat dimulai dari awal atau mulai dari paling akhir. Apabila elemen yang sekarang lebih besar (untuk urut menaik) atau lebih kecil (untuk urut menaik) dari elemen berikutnya, maka posisinya ditukar, tetapi jika tidak maka posisinya tetap.

Contoh : Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan diurutkan secara menaik dengan metode Bubble Sort: 25, 71, 30, 45, 20, 15, 6, 50. Urutan langkah pengurutannya yang dimulai dari belakang seperti berikut dan programnya dapat dilihat pada program Lat_Sorting_01a.

proses bubble sort menaik

Perhatikan contoh pengurutan yang diperagakan di atas bahwa pada langkah 4 telah terurut, maka sebenarnya proses sudah dapat dihentikan. Untuk mengatasi hal itu dalam program Lat_Sorting_01b digunakan variabel bertipe Boolean. Demikian juga halnya pengurutan secara menaik di atas tetap menggunakan variabel bertipe Boolean untuk mengatasi hal yang sama.

/* Program Pengurutan Metode Bubble Sort
  Pengurutan Secara Menaik
  Nama File : Lat_Sorting_01a */

#include<iostream.h>
#include<conio.h>
#include<iomanip.h>

void main()
{
  int Nilai[20];
  int i, j, k, N;
  int temp;
  bool tukar;
  cout<<"Masukkan Banyak Bilangan : ";
  cin>>N;
  for(i=0; i<N; i++)
  {
    cout<<"Elemen ke-"<<i<<" : ";
    cin>>Nilai[i];
  }
}

//Proses Cetak Sebelum diurutkan
cout<<"\nData sebelum diurut : ";
for(i=0; i<N; i++)
  cout<<setw(3)<<Nilai[i];
  
//Proses Pengurutan
i=0;
tukar = true;
while ((i<=N-2) && (tukar))
{
  tukar = false;
  for(j=N-1; j>=i+1; j--)
  {
    if(Nilai[j] < Nilai[j-1])
    {
      {
        temp = Nilai[j];
        Nilai[j] = Nilai[j-1];
        Nilai[j-1] = temp;
        tukar = true;
        cout<<"\nUntuk j = " <<j<<" : ";
        for(k=0; k<N; k++)
          cout<<set(3)<<Nilai[k];
      }
    }
    i++;
  }
  
  //Proses Cetak Setelah diurutkan
  cout<<"\nData Setelah di urut : ";
  for(i=0; i<N; i++)
    cout<<setw(3)<<Nilai[i];
  getch();
}

3. Quick Sort

Quick Sort merupakan metode tercepat dalam proses pengurutan data dengan menggunakan prinsip rekursif. Metode ini menggunakan strategi “pecah-belah” dengan mekanisme berikut ini.

Misalkan kita mempunyai array Nilai[k..l]. Array dipartisi menjadi dua bagian array kiri Nilai[k..m] dan array kanan Nilai[m+1..l]. Dasar mempartisi array menjadi dua adalah dengan mengambil elemen pertama sebagai elemen pivot. Letakkan semua elemen array yang lebih kecil dari pivot ke sebelah pivot dan semua elemen array yang lebih besar dari pivot ke sebelah kanan pivot. Elemen-elemen yang di sebelah kiri elemen pivot merupakan elemen-elemen array Nilai[k..m] sedangkan elemen-elemen array Nilai[m+2..l] adalah semua elemen yang lebih besar dari pivot. Lakukan hal yang sama seperti di atas terhadap array Nilai[k..m] dan Nilai[m+1..l] hingga tidak dapat dipartisi lagi.

Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan diurutkan secara menaik dengan metode Maximum Sort: 25, 72, 30, 45, 20, 15, 6, 50. Urutan langkah pengurutannya seperti berikut dan programnya dapat dilihat pada program Lat_Sorting_02a.

Ambil elemen pertama sebagai elemen pivot, letakkan semua elemen array yang lebih kecil dari pivot ke sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih besar dari pivot ke sebelah kanan elemen pivot.

proses quick sort ke-1

Gunakan array Nilai[0..2]. Ambil elemen pertama sebagai elemen pivot, letakkan semua elemen array yang lebih kecil dari pivot ke sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih besar dari pivot ke sebelah kanan elemen pivot.

proses quick sort ke-2

Perhatikan array Nilai[2] tidak dapat lagi dipartisi maka berhenti sampai disana.

Gunakan array Nilai[0..1]. Ambil elemen pertama sebagai elemen pivot, letakkan semua elemen array yang lebih kecil dari pivot ke sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih besar dari pivot ke sebelah kanan elemen pivot.

proses quick sort ke-3

Perhatikan array Nilai[0] dan Nilai[1] tidak dapat lagi dipartisi maka berhenti sampai di sana.

Gunakan array Nilai[4..7]. Ambil elemen pertama sebagai elemen pivot, letakkan semua elemen array yang lebih kecil dari pivot ke sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih besar dari pivot ke sebelah kanan elemen pivot.

proses quick sort ke-4

Gunakan array Nilai[4..6]. Ambil elemen pertama sebagai elemen pivot, letakkan semua elemen array yang lebih kecil dari pivot ke sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih besar dari pivot ke sebelah kanan elemen pivot.

proses quick sort ke-5

Gunakan array Nilai[5..6]. Ambil elemen pertama sebagai elemen pivot, letakkan semua elemen array yang lebih kecil dari pivot ke sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih besar dari pivot ke sebelah kanan elemen pivot.

proses quick sort ke-6

Karena semua elemen array sudah tidak dapat dipartisi maka proses pengurutan berakhir dan hasilnya diperoleh seperti berikut (gabungkan mulai Nilai[0] hingga Nilai[7]):

Untuk melakukan proses pengurutan data secara menurun dengan metode Quick Sort dilakukan dengan meletakkan semua elemen array yang lebih kecil dari pivot ke sebelah kanan pivot dan semua elemen array yang lebih besar dari pivot ke sebelah kiri pivot.

/* Program Pengurutan Metode Quick Sort
  Pengurutan Secara Menaik
  Nama File : Lat_Sorting_02a */
  
#include<iostream.h>
#include<conio.h>
#include<iomanip.h>

void Cetak(int data[], int n)
{
  int i;
  for(i=0; i<n; i++)
    cout<<setw(3)<<data[i];
  cout<<"\n";
}

int Partisi(int data[], int p, int r)
{
  int x, i, j, temp;
  x = data[p];
  i=p;
  j=r;
  while(l)
  {
    while(data[j]>x)
      j--;
    while(data[i]<x)
      i++;
    if(i<j)
    {
      temp = data[i];
      data[i] = data[j];
      data[j] = temp;
    }
    else
      return j;
  }
}

void Quick_Sort(int data[], int p, int r)
{
  int q;
  if(p<r)
  {
    q=Partisi(data, p, r+1);
    Quick_Sort(data, p, 1);
    Quick_Sort(data, q+1, r);
  }
}

void main()
{
  int Nilai[20];
  int i, N;
  cout<<"Masukkan Banyak Bilangan : ";
  cin>>N;
  for(i=0; i<N; i++)
  {
    cout<<"Elemen ke-"<<i<<" : ";
    cin>>Nilai[i];
  }
  cout<<"\nData Sebelum di urut : ";
  Cetak(Nilai, N);
  cout<<endl;
  Quick_Sort(Nilai, 0, N-1);
  cout<<"\nData Setelah di urut : ";
  Cetak(Nilai,N);
  getch();
}

4. Metode Maximum/Minimum Sort

Metode Maximum/Minimum Sort dilakukan berdasarkan pemilihan elemen maksimum/minimum, maka metode ini disebut juga dengan metode pemilihan/seleksi (Selection Sort).

4.1 Metode Maximum Sort

Metode ini disebut dengan metode Maximum karena didasarkan pada pemilihan elemen maksimum sebagai dasar pengurutan. Konsepnya adalah memilih elemen maksimum kemudian mempertukarkan elemen maksimum tersebut dengan elemen paling akhir untuk urut menaik dan elemen pertama untuk urut menurun. Selanjutnya elemen paling akhir/awal tersebut di-“isolasi”, artinya elemen tersebut tidak disertakan lagi untuk tahapan berikutnya. Proses yang sama dilakukan kembali terhadap elemen array yang tersisa, yaitu memilih elemen maksimum kemudian mempertukarkan elemen maksimum tersebut dengan elemen paling akhir/awal dari array yang tersisa tadi. Kemudian diisolasi kembali. Demikian seterusnya hingga semua elemen terurut.

Langkah -1: Cari elemen maksimum di dalam array Nilai[0..7] → Nilai[1]=72 kemudian tukarkan dengan elemen array paling akhir Nilai[7] sehingga diperoleh array:

Langkah -2: Cari elemen maksimum di dalam array yang tersisa Nilai[1..7] → Nilai[1]=50 kemudian tukarkan dengan elemen paling akhir array yang tersisa Nilai[6] sehingga diperoleh array:

Langkah -3: Cari elemen maksimum di dalam array yang tersisa Nilai[2..7] → Nilai[3]=45 kemudian tukarkan dengan elemen paling akhir array yang tersisa Nilai[5] sehingga diperoleh array:

Langkah -4: Cari elemen maksimum di dalam array yang tersisa Nilai[3..7] → Nilai[2]=30 kemudian tukarkan dengan elemen paling akhir array yang tersisa Nilai[4] sehingga diperoleh array:

Langkah -5: Cari elemen maksimum di dalam array yang tersisa Nilai[4..7] → Nilai[0]=25 kemudian tukarkan dengan elemen paling akhir array yang tersisa Nilai[3] sehingga diperoleh array:

Langkah -6: Cari elemen maksimum di dalam array yang tersisa Nilai[5..7] → Nilai[2]=20 kemudian tukarkan dengan elemen paling akhir array yang tersisa Nilai[2], sehingga diperoleh array:

Langkah -7: Cari elemen maksimum di dalam array yang tersisa Nilai[6..7] → Nilai[0]=15 kemudian tukarkan dengan elemen paling akhir array yang tersisa Nilai[1], sehingga diperoleh array:

Selesai. Dan array telah terurut secara menarik. Program mengurutkan secara menaik dengan metode Maximum Sort dapat dilihat pada program Lat_Sorting_04a.

/* Program Pengurutan Metode Maximum Sort
  Pengurutan Secara Menaik
  Nama File : Lat_Sorting_04a */
  
#include<iostream.h>
#include<conio.h>
#include<iomanip.h>

void main()
{
  int Nilai[20];
  int i, j, N, l;
  int temp, U, Imaks;
  cout<<"Masukkan Banyak Bilangan : ";
  cin>>N;
  for(i=0; i<N; i++)
  {
    cout<<"Elemen ke-"<<i<<" : ";
    cin>>Nilai[i];
  }
  
  //Proses Cetak Sebelum diurutkan
  cout<<"\nData sebelum diurut : ";
  for(i=0; i<N; i++)
    cout<<setw(3)<<Nilai[i];
    
  //Proses Pengurutan
  U=N-1;
  for(i=0; i<=N-2; i++)
  {
    Imaks = 0;
    for(j=1; j<=U; j++)
    {
      if(Nilai[j] > Nilai[Imaks])
      Imaks = j;
    }
    temp = Nilai[U];
    Nilai[U] = Nilai[Imaks];
    Nilai[Imaks] = temp;
    U--;
    cout<<endl;
    for(l=0; l<N; l++)
      cout<<setw(3)<<Nilai[l];
  }
  cout<<"\nData Setelah di urut : ";
  for(i=0; i<N; i++)
    cout<<setw(3)<<Nilai[i];
  getch();
}

Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan diurutkan secara menurun dengan metode Maximum Sort 25, 72, 30, 45, 20, 15, 6, 50. Urutan langkah pengurutannya seperti berikut dan programnya dapat dilihat pada program Lat_Sorting_04b.

Langkah -1: Cari elemen maksimum di dalam array Nilai[0..7] → Nilai[1]=72 kemudian tukarkan dengan elemen pertama array Nilai[0]=25 sehingga diperoleh array:

Langkah -2: Cari elemen maksimum di dalam array yang tersisa Nilai[1..7] → Nilai[7]=50 kemudian tukarkan dengan elemen pertama array yang tersisa Nilai[1]=25 sehingga diperoleh array:

Langkah -3: Cari elemen maksimum di dalam array yang tersisa Nilai[2..7] → Nilai[3]=45 kemudian tukarkan dengan elemen pertama array yang tersisa Nilai[2]=30 sehingga diperoleh array:

Langkah -4: Cari elemen maksimum di dalam array yang tersisa Nilai[3..7] →Nilai[3]=3- kemudian tukarkan dengan elemen pertama array yang tersisa Nilai[3]=30 sehingga diperoleh array:

Langkah -5: Cari elemen maksimum di dalam array yang tersisa Nilai[4..7] → Nilai[7]=35 kemudian tukarkan dengan elemen pertama array yang tersisa Nilai[4]=30 sehingga diperoleh array:

Langkah -6: Cari elemen maksimum di dalam array yang tersisa Nilai[5..7] → Nilai[7]=20 kemudian tukarkan dengan elemen pertama array yang tersisa Nilai[5]=15 sehingga diperoleh array:

Langkah -7: Cari elemen maksimum di dalam array yang tersisa Nilai[6..7] → Nilai[7]=15 kemudian tukarkan dengan elemen pertama array yang tersisa Nilai[6]=6 sehingga diperoleh array:

Selesai. Dan array telah terurut secara menurun. Program mengurutkan secara menurun dengan metode Maximum Sort dapat dilihat pada program Lat_Sorting_04b.

/* Program Pengurutan Metode Maximum Sort
  Pengurutan Secara Menurun
  Nama File : Lat_Sorting_04b */
  
#include<iostream.h>
#include<conio.h>
#include<iomanip.h>

void main()

{
  int Nilai[20];
  int i, j, N, l;
  int temp, U, Imaks;
  cout<<"Masukkan Banyak Bilangan : ";
  cin>>N;
  for(i=0; i<N; i++)
  {
    cout<<"Elemen ke-"<<i<<" : ";
    cin>>Nilai[i];
  }
  
  //Proses Cetak Sebelum diurutkan
  cout<<"\nData sebelum diurut : ";
  for(i=0; i<N; i++)
    cout<<setw(3)<<Nilai[i];
  
  //Proses Pengurutan
  U=N-1;
  for(i=0; i<=N-2; i++)
  {
    Imaks = i;
    for(j=i+1; j<=U; j++)
    {
      if(Nilai[j] > Nilai[Imaks])
        Imaks = j;
    }
    temp = Nilai[i];
    Nilai[i] = Nilai[Imaks];
    Nilai[Imaks] = temp;
    cout<<endl;
    for(l=0; l<N; l++)
      cout<<setw(3)<<Nilai[l];
  }
  cout<<"\nData Setelah di urut : ";
  for(i=0; i<N; i++)
    cout<<setw(3)<<Nilai[i];
  getch();
}

4.2. Metode Minimum Sort

Metode ini disebut dengan metode minimum karena didasarkan pada pemilihan elemen minimum sebagai dasar pengurutan. Konsepnya adalah memilih elemen minimum kemudian mempertukarkan elemen minimum tersebut dengan elemen paling akhir untuk urut menaik dan elemen pertama untuk urut menurun. Selanjutnya elemen paling akhir/pertama tersebut di “isolasi” artinya elemen tersebut tidak disertakan lagi untuk tahapan berikutnya. Proses yang sama dilakukan kembali terhadap elemen array yang tersisa, yaitu memilih elemen minimum kemudian mempertukarkan elemen minimum tersebut dengan elemen paling akhir/pertama dari array yang tersisa tadi. Kemudian diisolasi kembali. Demikian seterusnya hingga semua elemen terurut.

Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan diurutkan secara menaik dengan metode Minimum Sort: 25, 72, 30, 45, 20, 15, 6, 50. Urutan langkah pengurutannya seperti berikut dan programnya dapat dilihat pada program Lat_Sorting_05a.

Langkah -1: Cari elemen minimum di dalam array Nilai[0..7] → Nilai[6]=6 kemudian tukarkan dengan elemen pertama array Nilai[0]=25 sehingga diperoleh array:

Langkah -2: Cari elemen minimum di dalam array Nilai[1..7] → Nilai[5]=15 kemudian tukarkan dengan elemen pertama array yang tersisa Nilai[1]=72 sehingga diperoleh array:

Langkah -3: Cari elemen minimum di dalam array Nilai[2..7] → Nilai[4]=2- kemudian tukarkan dengan elemen pertama array yang tersisa Nilai[2]=30 sehingga diperoleh array:

Langkah -4: Cari elemen minimum di dalam array Nilai[3..7] → Nilai[6]=25 kemudian tukarkan dengan elemen pertama array yang tersisa Nilai[3]=45 sehingga diperoleh array:

Langkah -5: Cari elemen minimum di dalam array Nilai[4..7] → Nilai[4]=30 kemudian tukarkan dengan elemen pertama array yang tersisa Nilai[4]=30 sehingga diperoleh array:

5. Metode Shell Sort

Metode ini dinamakan sesuai dengan penciptanya, yaitu D.L. Shell. Metode ini mirip dengan metode Bubble Sort, hanya saja perbandingan dilakukan bukan antara dua bilangan yang berurutan, akan tetapi antara dua bilangan dengan jarak tertentu. Jarak ditentukan dengan N Div 2, dimana N adalah banyaknya elemen array. Lakukan pertukaran tempat jika setiap kali perbandingan dipenuhi (lebih besar untuk urut menaik dan lebih kecil untuk urut menurun). Setiap kali perbandingan terhadap keseluruhan elemen selesai dilakukan, maka perbandingan yang baru dilakukan kembali dimana jarak diperoleh dengan Jarak Div 2 (jarak diperoleh dari Nilai jarak sebelumnya). Perbandingan keseluruhan dilakukan sampai Nilai jarak sama dengan 1 (satu). Pada saat jarak berNilai 1, maka metode Shell Sort sama dengan metode Bubble Sort.

Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan diurutkan secara menaik dengan metode Shell Sort: 25, 72, 30, 45, 20, 15, 6, 59. Urutan langkah pengurutannya seperti berikut.

Untuk pertama kalinya Nilai jarak (K) = 8 div 2 = 4 dan kita buat suatu counter C=0. Kemudian proses perbandingan dilakukan berturut-turut antara Nilai[0] dengan Nilai[4], jika Nilai[0]>Nilai[4] maka lakukan pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[1] dengan Nilai[5], jika Nilai[1]>Nilai[5] maka lakukan pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[2] dengan Nilai[6], jika Nilai[2]>Nilai[6] maka lakukan pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[3] dengan Nilai[7], jika Nilai[3]>Nilai[7] maka lakukan pertukaran tempat kemudian Nilai C=1.

metode shell sort

Karena Nilai K masih sama dengan 4 dan Nilai C=1, maka lakukan kembali proses perbandingan dengan menghitung Nilai jarak (K) sama dengan 4 div 2 =2 dan membuat Nilai C=0, sekarang proses perbandingan dilakukan berturut-turut antara Nilai[0] dengan Nilai[2], jika Nilai[0]>Nilai[2] maka lakukan pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[1] dengan Nilai[3], jika Nilai[1]>Nilai[3] maka lakukan pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[2] dengan Nilai[4], jika Nilai[2]>Nilai[4] maka lakukan pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[3] dengan Nilai[5], jika Nilai[3]>Nilai[5] maka lakukan pertukaran dan jika tidak lanjutkan terhadap Nilai[4] dengan Nilai[6], jika Nilai[4]>Nilai[6] maka lakukan pertukaran dan jika tidak lanjutkan terhadap Nilai[5] dengan Nilai[7], jika Nilai[5]>Nilai[7] maka lakukan pertukaran tempat kemudian Nilai C=1.

metode shell sort

Karena Nilai K masih sama dengan 2 dan Nilai C=1, maka lakukan kembali proses perbandingan dengan menghitung Nilai jarak(K) sama dengan 2 div 2 = 1 dan membuat Nilai C=0, sekarang proses perbandingan dilakukan berturut-turut antara Nilai[0] dengan Nilai[1], Nilai[1] dengan Nilai[2], Nilai[2] dengan Nilai[3], Nilai[3] dengan Nilai[4], Nilai[4] dengan Nilai[5], Nilai[5] dengan Nilai[6], dan Nilai[6]>Nilai[7], kemudian Nilai C=1 akan diperoleh hasil pertukaran setelah perbandingan seperti berikut.

6 15 20 25 45 30 50 72

Walaupun K telah berNilai sama dengan satu, tetapi Nilai C masih berNilai sama dengan 1 maka perbandingan harus diulang kembali dengan memberi Nilai C=0 dan Nilai K sama seperti sebelumnya yaitu sama dengan 1. Setelah dilakukan perbandingan maka hasilnya dapat diperoleh seperti berikut:

6 15 20 25 30 45 50 72

Karena Nilai C tidak lagi berubah menjadi 1 maka perbandingan telah berakhir dan hasil terakhir merupakan hasil pengurutan yang diharapkan.

/* Program Pengurutan Metode Shell Sort
  Pengurutan Secara Menaik
  Nama File : Lat_Sorting_06a */
  
#include<iostream.h>
#include<conio.h>
#include<iomanip.h>

void main()
{
  int Nilai[20];
  int i, N, l, k;
  int temp, jarak, s;
  cout<<"Masukkan Banyak Bilangan : ";
  cin>>N;
  for(i=0; i<N; i++)
  {
    cout<<"Elemen ke-"<<i<<" : ";
    cin>>Nilai[i];
  }
  
  //Proses Cetak Sebelum diurutkan
  cout<<"\nData sebelum diurut : ";
  for(i=0; i<N; i++)
    cout<<setw(4)<<Nilai[i];
    
  //Proses Pengurutan
  jarak = N / 2;
  cout<<"\nJarak = "<<jarak;
  while(jarak >=1)
  {
    do
    {
      s=0;
      for(i=0; i<=(N-jarak)-1; i++)
      {
        k=i+jarak;
        if(Nilai[i] > Nilai[k])
        {
          temp = Nilai[i];
          Nilai[i] = Nilai[k];
          Nilai[k] = temp;
          s=1;
          for(l=0; l<N; l++)
            cout<<setw(4)<<Nilai[i];
          cout<<"\n\t";
          getch();
        }
      }
    }
    while(s!=0);
    jarak /= 2;
    cout<<"\nJarak= "<<jarak;
  }
  cout<<"\nData Setelah di urut : ";
  for(i=0; i<N; i++)
    cout<<setw(4)<<Nilai[i];
  getch();
}

Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan diurutkan secara menurun dengan metode Shell Sort: 25, 72, 30, 45, 20, 15, 6, 50. Urutan langkah pengurutannya seperti berikut.

Dengan cara yang sama untuk pengurutan secara menaik, dengan mengganti tanda > menjadi < maka akan diperoleh elemen array yang terurut secara menurun. Gunakan program Lat_Sorting_06b.

/* Program Pengurutan Metode Shell Sort
  Pengurutan Secara Menaik
  Nama File : Lat_Sorting_06a */
  
#include<iostream.h>
#include<conio.h>
#include<iomanip.h>

void main()
{
  int Nilai[20];
  int i, N, l, k;
  int temp, jarak, s;
  cout<<"Masukkan Banyak Bilangan : ";
  cin>>N;
  for(i=0; i<N; i++)
  {
    cout<<"Elemen ke-"<<i<<" : ";
    cin>>Nilai[i];
  }
  
  //Proses Cetak Sebelum diurutkan
  cout<<"\nData sebelum diurut : ";
  for(i=0; i<N; i++)
    cout<<setw(4)<<Nilai[i];
    
  //Proses Pengurutan
  jarak = N / 2;
  cout<<"\nJarak = "<<jarak;
  while(jarak >=1)
  {
    do
    {
      s=0;
      for(i=0; i<=(N-jarak)-1; i++)
      {
        k=i+jarak;
        if(Nilai[i] > Nilai[k])
        {
          temp = Nilai[i];
          Nilai[i] = Nilai[k];
          Nilai[k] = temp;
          s=1;
          for(l=0; l<N; l++)
            cout<<setw(4)<<Nilai[i];
          cout<<"\n\t";
          getch();
        }
      }
    }
    while(s!=0);
    jarak /= 2;
    cout<<"\nJarak= "<<jarak;
  }
  cout<<"\nData Setelah di urut : ";
  for(i=0; i<N; i++)
    cout<<setw(4)<<Nilai[i];
  getch();
}

6. Metode Merge Sort

Metode ini memanfaatkan keteraturan yang diperoleh dari hasil merging dua buah array. Suatu array Nilai yang mempunyai N elemen (Nilai[0..N-1]) dianggap terdiri dari N array yang masing-masing terdiri dari satu elemen. Untuk pasangan array yang berdekatan kita lakukan merging sehingga diperoleh N/2 buah array yang masing-masing array memiliki 2 elemen (jika N ganjil, akan terdapat sebuah array dengan 1 elemen). Pada saat melakukan proses merging dilakukan pengaturan posisi dengan cara elemen yang lebih kecil diletakkan di posisi awal (untuk pengurutan secara menaik) dan elemen yang lebih besar diletakkan di posisi awal(untuk pengurutan secara menurun). Kemudian dilakukan merging kembali untuk setiap pasanga array seperti cara di atas sehingga kita peroleh N/2 buah array yang masing-masing array memiliki 4 elemen. Langkah ini kita teruskan hingga kita memperoleh sebuah array yang sudah dalam keadaan terurut.

Misalkan kita memiliki array Nilai[0..13] = {45, 12, 4, 78, 90, 74, 40, 20, 10, 15, 25, 22, 95, 81} maka dengan menggunakan metode Merge Sort secara menaik dapat dilakukan seperti pada gambar.

metode merge sort

7. Metode Insertion Sort

Metode Insertion Sort merupakan metode pengurutan dengan cara menyisipkan elemen array pada posisi yang tepat. Pencarian yang tepat dilakukan dengan melakukan pencarian beruntun di dalam array. Selama pencarian posisi yang tepat dilakukan pergeseran elemen array. Algoritma pengurutan ini tepat untuk persoalan menyisipkan elemen baru ke dalam array yang sudah terurut. Misalnya dalam permainan kartu, kartu yang dicabut biasanya disisipkan oleh pemain pada posisi yang tepat sehingga penambahan kartu tersebut membuat semua kartu tetap terurut.

Misalkan kita memiliki suatu array dengan N maka pengurutan secara menaik dengan metode Insertion Sort sebagai berikut:

Langkah -1: elemen pertama Nilai[0] diasumsikan telah sesuai tempatnya.

Langkah -2: ambil elemen ke dua (Nilai[1]), cari lokasi yang tepat pada Nilai[0..0] untuk Nilai Nilai[1]. Lakukan pergeseran ke kanan jika Nilai[0..1] lebih besar (untuk urut menaik) atau lebih kecil (untuk urut menurun) dari Nilai[1]. Misalnya posisi yang tepat adalah j, maka sisipkanlah Nilai[1] pada Nilai[j].

Langkah -3: ambil elemen ke tiga (Nilai[2]), cari lokasi yang tepat pada Nilai[0..1] untuk Nilai[2]. Lakukan pergeseran ke kanan jika Nilai[0..2] lebih besar (untuk urut menaik) atau lebih kecil (untuk urut menurun) dari Nilai[2]. Misalnya posisi yang tepat adalah j, maka sisipkanlah Nilai[2] pada Nilai[j].

Langkah -4: ambil elemen ke empat (Nilai[3]), cari lokasi yang tepat pada Nilai[0..3] untuk Nilai Nilai[3]. Lakukan pergeseran ke kanan jika Nilai[0..2] lebih besar (untuk urut menaik) atau lebih kecil (untuk urut menurun) dari Nilai[3]. Misalnya posisi yang tepat adalah j, maka sisipkanlah Nilai[3] pada Nilai[j].

…

Langkah –N: ambil elemen ke N (Nilai[N]), cari lokasi yang tepat pada Nilai[0..N-1] untuk Nilai Nilai[N]. Lakukan pergeseran ke kanan jika Nilai[0..N-1] lebih besar (untuk urut menaik) atau lebih kecil (untuk urut menurun) dari Nilai[N]. Misalnya posisi yang tepat adalah j, maka sisipkanlah Nilai[N] pada Nilai[j].

Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan diurutkan secara menaik dengan metode Insertion Sort: 25, 72, 30, 45, 20, 15, 6, 50. Urutan langkah pengurutannya seperti berikut:

Langkah -1: Nilai[0] diasumsikan telah terurut.

Langkah -2: cari lokasi yang tepat untuk Nilai[1] pada Nilai[0..0]. Dalam hal ini, ternyata 72 tidak lebih besasr dari 25 maka tidak terjadi pergeseran, sehingga diperoleh array seperti berikut:

Langkah -3: cari lokasi yang tepat untuk Nilai[2] pada Nilai[0..1]. Dalam hal ini, ternyata lokasi yang tepat adalah 1, maka Nilai[1] digeser ke kanan sehingga Nilai[2] di posisi ke 1, sehingga diperoleh array sebagai berikut:

Langkah -4: cari lokasi yang tepat untuk Nilai[3] pada Nilai[0..2]. Dalam hal ini, ternyata lokasi yang tepat adalah 2, maka Nilai[2] digeser ke kanan sehingga Nilai[3] di posisi ke 3, sehingga diperoleh array seperti berikut:

Langkah -5: cari lokasi yang tepat untuk Nilai[4] pada Nilai[0..3]. Dalam hal ini, ternyata lokasi yang tepat adalah 0, maka Nilai[0], Nilai[1], Nilai[2], Nilai[3] digeser masing-masing satu posisi ke kanan sehingga Nilai[4] di posisi ke 0, sehingga array seperti berikut:

proses insertion sort menaik ke-5

Langkah -6: cari lokasi yang tepat untuk Nilai[5] pada Nilai[0..4]. Dalam hal ini, ternyata lokasi yang tepat adalah 0, maka Nilai[0], Nilai[1], Nilai[2], Nilai[3] dan Nilai[4] digeser masing-masing satu posisi ke kanan sehingga Nilai[6] di posisi ke 0, diperoleh array seperti berikut:

proses insertion sort menaik ke-6

Langkah -7: cari lokasi yang tepat untuk Nilai[6] pada Nilai[0..5]. Dalam hal ini, ternyata lokasi yang tepat adalah 0, maka Nilai[0], Nilai[1], Nilai[2], Nilai[3], Nilai[4] dan Nilai[5] digeser masing-masing satu posisi ke kanan sehingga Nilai[6] di posisi ke 0, diperoleh array seperti berikut:

Langkah -8: cari lokasi yang tepat untuk Nilai[7] pada Nilai[0..6]. Dalam hal ini, ternyata lokasi yang tepat adalah 6, maka Nilai[6] digeser satu posisi ke kanan sehingga Nilai[7] di posisi ke 6, diperoleh array seperti berikut:

Selesai. Dan array telah terurut secara menaik. Program untuk mengurutkan elemen array secara menaik dengan metode Insertion Sort dapat dilihat pada program Lat_Sorting_07a.

/* Program Pengurutan Metode Insertion Sort
  Pengurutan Secara Menaik
  Nama File : Lat_Sorting_07a */

#include<iostream.h>
#include<conio.h>
#include<iomanip.h>

void main()
{
  int Nilai[20];
  int i, j, k, N;
  int temp;
  cout<<"Masukkan Banyak Bilangan : ";
  cin>>N;
  for(i=0; i<N; i++)
  {
    cout<<"Elemen ke-"<<i<<" : ";
    cin>>Nilai[i];
  }
  
  //Proses Cetak sebelum diurutkan
  cout<<"\nData sebelum diurut : ";
  for(i=0; i<N; i++)
    cout<<setw(3)<<Nilai[i];
    
  //Proses Pengurutan
  for(i=1; i<N; i++)
  {
    temp = Nilai[i];
    j=i-1;
    while((temp <= Nilai(j)) && (j>=1))
    {
      Nilai[j+1] = Nilai[j];
      j--;
    }
    if(temp >= Nilai[j])
      Nilai[j+1] = temp;
    else
    {
      Nilai[j+1] = Nilai[j];
      Nilai[j] =  temp;
    }
    cout<<endl;
    for(k=0; k<N; k++)
      cout<<setw(3)<<Nilai[k];
  }
  
  //Proses Cetak Setelah diurutkan
  cout<<"\nData Setelah di urut : ";
  for(i=0; i<N; i++)
    cout<<setw(3)<<Nilai[i];
  getch();
}

Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan diurutkan secara menurun dengan metode Insertion Sort: 25, 72, 30, 45, 20, 15, 6, 50. Urutan langkah pengurutannya seperti berikut:

Langkah -1: Nilai[0] diasumsikan telah terurut

Langkah -2: cari lokasi yang tepat untuk Nilai[2] pada Nilai[0..0]. Dalam hal ini, ternyata lokasi yang tepat adalah 0, maka Nilai[0] digeser ke kanan satu posisi dan Nilai[1] menempati posisi ke 0, sehingga diperoleh array seperti berikut:

Langkah -3: cari lokasi yang tepat untuk Nilai[2] pada Nilai[0..1]. Dalam hal ini, ternyata lokasi yang tepat adalah 1, maka Nilai[1] digeser satu posisi ke kanan sehingga Nilai[2] di posisi ke 1, sehingga diperoleh array seperti berikut:

Langkah -4: cari lokasi yang tepat untuk Nilai[3] pada Nilai[0..2]. Dalam hal ini, ternyata lokasi yang tepat adalah 1, maka Nilai[1] dan Nilai[2] digeser satu posisi ke kanan sehingga Nilai[3] di posisi ke 1, sehingga diperoleh array seperti berikut:

Langkah -5: cari lokasi yang tepat untuk Nilai[4] pada Nilai[0..3]. Dalam hal ini, ternyata lokasi yang tepat adalah 4, tapi karena oleh dirinya sendiri maka tidak ada pergeseran, sehingga array seperti berikut:

Langkah -6: cari lokasi yang tepat untuk Nilai[5] pada Nilai[0..4]. Dalam hal ini, ternyata lokasi yang tepat adalah 5, tapi karena oleh dirinya sendiri maka tidak ada pergeseran, sehingga array seperti berikut:

Langkah -7: cari lokasi yang tepat untuk Nilai[6] pada Nilai[0..5]. Dalam hal ini, ternyata lokasi yang tepat adalah 6, tapi karena oleh dirinya sendiri maka tidak ada pergeseran, sehingga array seperti berikut:

Langkah -8: cari lokasi yang tepat untuk Nilai[7] pada Nilai[0..6]. Dalam hal ini, ternyata lokasi yang tepat adalah 1, maka Nilai[1], Nilai[2], Nilai[3], Nilai[4], Nilai[5], Nilai[6] digeser satu posisi ke kanan sehingga Nilai[7] di posisi ke 1, diperoleh array seperti berikut: