Algoritma Pengurutan ( Sorting)

Adanya kebutuhan terhadap proses pengurutan memunculkan bermacam-macam algoritma pengurutan. Ada banyak algoritma pengurutan yang telah ditemukan. Hal ini menunjukan bahwa persoalan pengurutan adalah persoalan yang kaya dengan solusi algoritma. Beberapa Algoritma pengurutan yang sudah dikenal antara lain Bubble Sort, Selection Sort, Insertion Sort, Heap Sort, Shell Sort, Quick Sort, Merge Sort, Radix Sort, Tree Sort, Dan Lain sebagainya.

Tidak semua algoritma pengurutan akan saya bahas di artikel kali ini, tetapi cukup beberapa algoritma pengurutan yang sederhana yang perlu diketahui saja oleh orang yang belajar pemrograman dasar.

Di artikel kali ini saya akan membahas beberapa algoritma pengurutan saja, yaitu:

1. algoritma pengurutan apung ( Bubble Sort).
2. algoritma pengurutan seleksi ( Selection Sort).
3. algoritma pengurutan sisip ( Insertion Sort).

Dua algoritma pengurutan pertama yaitu; bubble sort dan selection sort melakukan prinsip pertukaran elemen dalam proses pengurutannya sehingga keduanya dinamakan pengurutan dengan pertukaran ( exchange sorts), sedangkan algoritma  Insertion Sort melakukan prinsip geser dan sisip elemen didalam proses pengurutannya ( shift and insert sorts). Semua algoritma pengurutan selalu melakukan operasi perbandingan elemen untuk menemukan posisi urutan yang tepat.

1. Algoritma Pengurutan Apung ( Bubble Sort)

Algoritma pengurutan apung ( Bubble Sort) diinspirasikan oleh gelembung sabun yang berada diatas permukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka dari itu gelembung sabun selalu terapung diatas air. Secara umum, benda-banda yang berat akan terbenam dan benda-benda yang ringan akan terapung keatas permukaan air.

Mekanisme kerja Algoritma Bubble Sort adalah sebagai berikut:

1. membandingka data ke-1 dengan data ke-2, jika ke-1 lebih besar, maka kedua data ditukar.
2. kemudian membandingkan data ke-2 dengan data ke-3, jika data ke-2 lebih besar, kedua data ditukar.
3. demikian seterusnya sampai data terakhir, sehingga data kedudukannya akan bergeser-geser.

Contoh Program Bubble Sort C++ :

#include <iostream>
#include <conio.h>
using namespace std;
    int data[8], data2[8];
    int n;

int tukar (int a,int b){
    int t;
    t=data[b];
    data[b]=data[a];
    data[a]=t;
}

int input(){
    cout<<"Masukan Jumlah Data = ";
cin>>n;

cout<<endl;

    for (int i=0;i<n;i++){
    cout<<"Masukan Data Ke-"<<i+1<<" = ";
    cin>>data[i];

    data2[i]=data[i];
}
cout<<endl;
}

int tampil(){
for (int i=0;i<n;i++){
     cout<<"["<<data[i]<<"] ";
}
cout<<endl;
}

int bubble_sort(){
for (int i=1; i<n;i++){
for (int j=n-1; j>=i;j--){
if (data[j]<data[j-1]){
tukar(j,j-1);
}
}
tampil();
}
cout<<endl;
}


int main()
  {
  cout<<"ALGORITMA BUBBLE SORT"<<endl;
  cout<<"----------------------"<<endl;
input();
cout<<"Proses Bubble Sort"<<endl;
tampil();
bubble_sort();
  getch();
  }

 

Hasil Output Program Bubble Sort:

      2. Algoritma Pengurutan Seleksi ( Selction Sort )

Algoritma ini disebut pengurutan seleksi ( Selection Sort ) karena gagasan dasarnya adalah memilih elemen maksimum atau minimum dari larik, lalu menempatkan elemen tersebut pada awal atau akhir larik. Selanjutnya elemen terujung tersebut diisolasi dan tidak disertakan pada proses selanjutnya. Proses yang sama diulang untuk elemen-elemen larik yang tersisa.

Mekanisme kerja Algoritma Selection Sort:

1. Variabel index diberinilai 1 kemudian data index dibandingkan dengan data ke-2. Jika data index lebih besar maka nilai indexnya diganti dengan 2, jika tidak nilai indexnya tetap. Kemudian data index dibandingkan lagi dengan data yang ada seterusnya.
2. Variabel index diberi nilai 2 kemudian data index dibandingkan dengan data ke-3. Jika data index lebih besar maka nilai indexnya diganti dengan data 3. Kemudian data index dibandingkan lagi dengan data ke-4.
3. Demikian untuk proses selanjutnya dimana banyak prosesnya adalah jumlah elemen array dikurangi 1.

Contoh Program Selection Sort C++:

#include<iostream>

using namespace std;

int main()

{   int a,b,c,d,e;

    b=6;

    int f[6];

    cout<<"SELECTION SORT BY Syarifsoden.BLOGSPOT.COM"<<endl;

    cout<<"mengurutkan nilai dari besar ke kecil"<<endl<<endl;

    for(a=0;a<b;a++)

    {

        cout<<"Masukkan nilai: "<<a+1<<" : ";cin>>f[a];

    }

    for(a=0;a<b-1;a++)

    {

    c=a;

        for(d=a+1;d<b;d++)

        {

            if(f[c]<f[d])

            {

                c=d;

            }

        }

        e=f[c];

        f[c]=f[a];

        f[a]=e;

    }

    cout<<"\n setelah diurutkan akan menjadi: \n";

    for(a=0;a<b;a++)

    {

        cout<<f[a]<<" \n";

    }

}

Hasil Output Program Selection Sort:

      3. Algoritma Pengurutan Sisip (Insertion Sort)

Pengurutan sisip ( Insertion Sort ) adalah algoritma pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat. Pencarian posisi yang tepat dilakukan dengan cara menyisir larik. Selama penyisiran dilakukan pergeseran elemen larik. Algoritma pengurutan sisip cocok untuk persoalan menyisipkan elemen baru ke dalam sekumpulan elemen yang sudah terurut.

Cara kerja algoritma pengurutan sisip ( Insertion Sort)

1. Pengurutan dimulai dari data ke-2 sampai data terakhir.
2. Jika ditemukan data yang lebih kecil atau lebih besar, maka akan ditempatkan ( diinsert) diposisi yang seharusnya.

Contoh program Insertion Sort C++:

#include <iostream>

using namespace std;

int main(){

int z;

cout<<"masukan banyak array: ";

cin>>z;

int y[z];

for(int i=0; i<z; i++){

cout<<"masukan angka ke "<<i<<" :";

cin>>y[i];

cout<<endl;

}

for(int i=1; i<z; i++){

int key = y[i];

int j = i-1;

while(j>=0 && y[j] > key){

y[j+1] = y[j];

j--;

}

y[j+1] = key;

cout<<"proses sorting"<<endl;

for(int m=0;m<z;m++){

cout<<y[m]<<" ";

    }

    cout<<endl;

}

cout<<"hasil akhir"<<endl;

for(int m=0;m<z;m++){

cout<<y[m]<<" ";

}

}

Hasil Output Program Insertion Sort C++: