SORTING (Selection Sort dan Insertion Sort)

A. Selection Sort
Metode selection sort merupakan perbaikan dari metode bubble sort dengan mengurangi jumlah perbandingan. Selection sort merupakan metode pengurutan dengan mencari nilai data terkecil dimulai dari data diposisi 0 hingga diposisi N-1. Jika terdapat N data dan data terkoleksi dari urutan 0 sampai dengan N-1 maka algoritma pengurutan dengan metode selection sort adalah sebagai berikut:

Ø Cari data terkecil dalam interval j = 0 sampai dengan j = N-1
Ø Jika pada posisi pos ditemukan data yang terkecil, tukarkan data diposisi pos dengan data di posisi i jika k.

Ø Ulangi langkah 1 dan 2 dengan j = j+i sampai dengan j = N-1, dan seterusnya sampai j = N - 1.

contoh coding selection sort
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
int Data[MAX];

// Fungsi pertukaran bilangan
void Tukar (int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void SelectionSort()
{
int i, j, k;
for(i=0; i<MAX-1;i++)
{
k = i;
for (j=i+1; j<MAX; j++)
if(Data[k] > Data[j])
k = j;
Tukar(&Data[i], &Data[k]);
}
}
void main()
{
int i;
srand(0);
// Membangkitkan bilangan acak
printf("DATA SEBELUM TERURUT");
for(i=0; i<MAX; i++)
{
Data[i] = (int) rand()/1000+1;
printf("\nData ke %d : %d ", i, Data[i]);
}
SelectionSort();
// Data setelah terurut
printf("\nDATA SETELAH TERURUT");
for(i=0; i<MAX; i++)
{
printf("\nData ke %d : %d ", i, Data[i]);
}
getch();
}
hasil dari coding

B. Insertion Sort
Metode penyisipan (Insertion sort) yang bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array berhasil diurutkan. Metode ini mengurutkan bilangan-bilangan yang telah dibaca dan berikutnya secara berulang akan menyisipkan bilangan-bilangan dalam array yang belum terbaca ke sisi kiri array yang telah terurut.

contoh coding insertion sort
#include <iostream.h>
#include <conio.h>

int data[10],data2[10];
int n;

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

void insertion_sort()
{
int temp,i,j;
for(i=1;i<=n;i++)
{
temp = data[i];
j = i -1;
while(data[j]>temp && j>=0)
{
data[j+1] = data[j];
j--;
}
data[j+1] = temp;
}
}
int main()
{
cout<<"------METODE INSERTION SORT------"<<endl<<endl;

//Input Data
cout<<"Masukkan Jumlah Data : ";
cin>>n;
for(int i=1;i<=n;i++)
{
cout<<"Masukkan data ke "<<i<<" : ";
cin>>data[i];
data2[i]=data[i];
}

insertion_sort();

cout<<"\n\n";
//tampilkan data
cout<<"Data Setelah di Sort : ";
for(int i=1; i<=n; i++)
{
cout<<" "<<data[i];
}
cout<<"\n\nSorting Selesai";
getch();
return 0;
}

hasil dari coding

referensi :   materi dari ppt. teori struktur data/ STIKOM-Bali
                 Coding dari dosen praktikum struktur data/ STIKOM-Bali/ dengan sedikit perubahan