Struktur Data - Sorting

Artikel ini merupakan lanjutan dari artikel yang saya tulis sebelumnya, yaitu Queue

Sorting merupakan proses pengurutan data, baik dari kecil ke besar (ascending) maupun besar ke kecil (descending). Ada banyak algoritma proses pengurutan data ini, namun disini saya hanya membahas proses pengurutan data menggunakan algoritma insertion sort dan selection sort.

a.       Selection Sort

Selection sort dilakukan dengan cara mencari data terkecil kemudian dikumpulkan pada indeks teratas (pada model ascending) atau mencari data terbesar kemudian dikumpulkan pada indeks teratas ( pada model descending)

Skema Selection Sort

Data awal

                5 8 4 3

o   Fase 1

Temp = 5

Cek 5 kurang dari 8 ? dilewati

Cek 5 kurang dari 4 ? diswap , sehingga temp = 4

Cek 4 kurang dari 3 ? diswap, sehingga temp=3

Mengisi nilai temp ke indeks teratas, sehingga data pada fase 1 menjadi 3 8 5 4

o   Fase 2

Temp = 8

Cek 8 kurang dari 5 ? diswap, sehingga temp=5

Cek 4 kurang dari 5 ? diswap, sehingga temp=4

Mengisi nilai temp ke indeks ke 1 sehingga data pada fase 2 menjadi 3 4 8 5

o   Fase 3

Temp = 8

Cek 8 kurang dari 5 ? diswap, sehingga temp=5

Mengisi nilai temp ke indeks ke 3 sehingga data menjadi 3 4 8 5

Studi kasus : Buatlah Program untuk mengurutkan data menggunakan algoritma selection sort!

#include<iostream.h> #include<conio.h> int data[5],temp; void tukar(int a, int b) { int t; t=data[b]; data[b]=data[a]; data[a]=t; } void main() { for(int i=0;i<5;i++) { cout << "Inputkan data yang ingin diurutkan pada indeks ke-" << i << " : "; cin >> data[i]; } int pos,i,j; for(i=0;i<5;i++) { pos=i; for(j=i+1;j<5;j++) { if(data[j]<data[pos])pos=j; } if(pos!=i) tukar(pos,i); } cout<<"selection sort selesai !"<<endl; cout<<"Data : "<<endl; for(int i=0;i<5;i++) { cout<<data[i]<<" "; } cout<<endl; getch(); }

b.       Insertion Sort

Insertion Sort adalah sebuah metode pengurutan data dengan menempatkan setiap elemen data pada pososinya dengan cara melakukan perbandingan dengan data – data yang ada. Insertion sort ini bekerja seperti kita melakukan pengurutan kartu. Yaitu dengan cara menggeser geser kartu tersebut. Dan menyisipkan kartu dengan nilai tertentu.

Cara kerja algoritma ini :

Contoh  data Awal = 5 2 6 4
Maka :

• Temp=5
• Proses 1 = 2 5 6 4
• Proses 2 = 2 5 6 4
• Proses 3 = 2 4 5 6
• Selesai !

Studi kasus : Buatlah program pengurutan data insertion sort!

#include<iostream.h> #include<conio.h> int data[5],temp; void tukar(int a, int b) { int t; t=data[b]; data[b]=data[a]; data[a]=t; } void main() { for(int i=0;i<5;i++) { cout << "Inputkan data yang ingin diurutkan pada indeks ke-" << i << " : "; cin >> data[i]; } int temp,i,j; for(i=1;i<5;i++) { temp=data[i]; j=i-1; while(data[j]>temp && j>=0) { data[j+1]=data[j]; j--; } data[j+1]=temp; } cout<<"Insertion sort selesai ! "<<endl; cout<<"Data : "<<endl; for(int i=0;i<5;i++) { cout<<data[i]<<" "; } cout<<endl; getch(); }

Terimakasih. Sumber : Materi Slide Power Point dan script C++ Dosen Matakuliah Praktikum Struktur Data STMIK STIKOM BALI, Ida Bagus Surya Arnawa