Programming C++: Sorting

Pengurutan(sorting) diartikan sebagai proses penyusunan kembali sekumpulan objek ke dalam urutan tertentu. Tujuan pengurutan adalah mendapatkan kemudahan dalam pencarian anggota dari suatu himpunan, disamping dapat mempercepat mengetahui data terbesar dan data terkecil, misalkan kita ingin mengetahui perolehan nilai tertinggi dan nilai terendah dari hasil ujian. Contoh objek terurutkan adalah daftar isi, daftar pustaka, dan lain-lain.

Selection Sort

Pengurutan Naik (Ascending)

Proses pengurutan dengan menggunakan metode Selection Sort secara terurut naik adalah sebagai berikut:

• Mencari data terkecil dari data pertama sampai data terakhir, kemudian ditukarkan posisinya dengan data pertama.
• Mencari data terkecil dari data kedua sampai data terakhir, kemudian ditukarkan posisinya dengan data kedua.
• Mencari data terkecil dari data ketiga sampai data terakhir, kemudian ditukarkan posisinya dengan data ketiga.
• Dan seterusnya sampai semua data terurut naik. Apabila terdapat n buah data yang akan diurutkan, maka membutuhkan (n-1) langkah pengurutan, dimana data terakhir yaitu data ke-n tidak perlu diurutkan karena hanya tinggal satu-satunya.
• Cara pengurutannya: seleksi data yang ada kemudian dilakukan swap (pertukaran posisi).
• Pada Ascending : seleksi data terkecilkemudian swap.
• Pada descending : seleksi data terbesarkemudian swap.

Algoritma Selection Sort (Ascending)

1. Tampung data ke-i
2. Seleksi data terkecil
3. Cek apakah data yang ditampung lebih besar dari data hasil seleksi (data terkecil).
4. Jika pengecekan langkah 3 bernilai “true” :  lakukan pertukaran posisi antara data yang ditampung dengan data terkecil.
5. Ulangi langkah 1 sampai 4, hingga nilai i sama dengan n.

Ilustrasi Selection Sort:

Contoh Program Selection Sort:
*Source Code dibawah ini di compile menggunakan Code::Blocks

	#include <iostream>
	#include <conio.h>
	using namespace std;
	int data[20],data2[20];
	int n;
	void tukar(int a, int b)
	{
	int t;
	t = data[b];
	data[b] = data[a];
	data[a] = t;
	}
	void selection_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()
	{
	//Input Data
	cout<<"Masukkan Jumlah Data : ";
	cin>>n;
	cout<<endl;
	for(int i=1;i<=n;i++)
	{
	cout<<"Masukkan Data Ke- "<<i<<" : ";
	cin>>data[i];
	data2[i]=data[i];
	}
	selection_sort();
	cout<<endl;
	cout<<endl;
	//tampilkan data
	cout<<"Data Setelah di Sort : "<<endl;
	for(int i=1; i<=n; i++)
	{
	cout<<" "<<data[i];
	}
	getch();
	}

view raw Sorting (Selection Sort) hosted with ❤ by GitHub

Tampilan Program:

Insertion Sort

Proses yang terjadi pada pengurutan dengan menggunakan metode Insertion Sort dimulai dari data ke-2, kemudian, kemudian disisipkan pada tempat yang sesuai. data pada posisi pertama diandaikan memang sudah pada tempatnya

Cara Pengurutannya:

• Cara pengurutannya: dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya.
• Ascending : ketika perbandingan ambil data yang paling kecil.
• Descending : ketika perbandingan ambil data yang paling besar

Algoritma Insertion Sort (Ascending)

1. Ambil satu data ke-i simpan di temp.
2. Bandingkan data temp dengan data yang ada disebelah kiri satu per-satu.
3. Cek apakah data temp lebih kecil dari data sebelah kiri.
4. Jika langkah nomor 3 bernilai “true” : lakukan pergeseran data satu-persatu kemudian pada posisi yang tepat sisipkan data temp.
5. Ulangi langkah 1 sampai 4, hingga i sama dengan n

Ilustrasi Insertion Sort

Contoh Program Insertion Sort:
*Source Code dibawah ini di compile menggunakan Code::Blocks

	// KEPALA PROGRAM
	#include <iostream>
	#include <conio.h>
	using namespace std;
	// TIPE DATA DAN VARIABLE
	int data[30],data2[30];
	int n, t, temp, i, j;
	// PROSES SORT
	void tukar(int a, int b)
	{
	t = data[b];
	data[b] = data[a];
	data[a] = t;
	}
	void insertion_sort()
	{
	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()
	{
	// MENGINPUTKAN DATA
	cout<<"Masukkan Jumlah Data : ";
	cin>>n;
	cout<<endl;
	for(int i=1;i<=n;i++)
	{
	cout<<"Masukkan Data Ke- "<<i<<": ";
	cin>>data[i];
	data2[i]=data[i];
	}
	insertion_sort();
	cout<<endl<<endl;
	//MENAMPILKAN DATA
	cout<<"Data Setelah di Sort : "<<endl;
	for(int i=1; i<=n; i++)
	{
	cout<<" "<<data[i];
	}
	getch();
	}

view raw Sorting (Insertion Sort) hosted with ❤ by GitHub

Tampilan Program:

Baca Juga
Pemrograman C++: Variable
Pemrograman C++: Array 1 Dimensi dan 2 Dimensi
Pemrograman C++: Stack
Pemrograman C++: Queue
Pemrograman C++: Sorting
Pemrograman C++: Searching

Referensi:
10 Langkah Belajar Logika dan Algoritma, Menggunakan Bahasa C dan C++ by Ema Utami & Sukrisno
http://entin.lecturer.pens.ac.id/SD%20&%20Algoritma%20PJJ/Bulan%204/Minggu%2013%20Searching.pdf