Membuat Program C++ Algoritma Pengurutan (Sorting Algorithm): Insertion Sort, Merge Sort, Shell Sort, Quick Sort, Bubble Sort, Selection Sort
Algoritma adalah langkah-langkah atau langkah-langkah sistematis untuk mencapai hasil yang diinginkan. Sorting atau pengurutan adalah proses pengolahan data yang sebelumnya terorganisir dengan sampel atau sampel acak menjadi data yang terorganisir secara teratur menurut suatu pola atau aturan yang ditetapkan. Pengurutan dapat dilakukan berdasarkan nilai terkecil sampai terbesar (ascending) atau sebaliknya (descending). Dengan demikian, algoritma pengurutan adalah langkah sistematis dalam mengatur data dalam urutan atau susunan tertentu.
#include <iostream>
#include <conio.h>
#include <cstring>
#include <stdlib.h>
using namespace std;
int NIM[] = {2,1,1,0,8,1,7,1,1,0,0,0,8};
char nama[20] = {‘a’,’n’,’d’,’r’,’i’,’r’,’a’,’h’,’m’,’a’,’d’,’a’,’n’,’i’};
int sizeNIM = sizeof(NIM) / sizeof(NIM[0]);
int sizenama = sizeof(nama) / sizeof(nama[0]);
//=====================================================================
// Varabel Nama Sebelum diurutkan
//=====================================================================
int NIMSebelum[] = {2,1,1,0,8,1,7,1,1,0,0,0,8};
char namaSebelum[20] = {‘a’,’n’,’d’,’r’,’i’,’r’,’a’,’h’,’m’,’a’,’d’,’a’,’n’,’i’};
int sizeNIMSebelum = sizeof(NIM) / sizeof(NIM[0]);
int sizenamaSebelum = sizeof(nama) / sizeof(nama[0]);
//=====================================================================
// Print Array Nama Sebelum diurutkan
//=====================================================================
void printArrayNamaSebelum(char array[], int size) {
for (int i = 0; i < size; i++) {
cout << array[i] << ” “;
}
cout << endl;
}
//=====================================================================
// Print Array NIM Sebelum diurutkan
//=====================================================================
void printArrayNimSebelum(int array[], int size) {
int i;
for (i = 0; i < size; i++)
cout << array[i] << ” “;
cout << endl;
}
//=====================================================================
// Insertion sort in C++
//=====================================================================
void insertionSort(char array[], int size) {
for (int step = 1; step < size; step++) {
int key = array[step];
int j = step – 1;
while (key < array[j] && j >= 0) {
array[j + 1] = array[j];
–j;
}
array[j + 1] = key;
}
for (int i = 0; i < size; i++) {
cout << array[i] << ” “;
}
cout << endl;
}
//=====================================================================
// Function to print an array NIM
//=====================================================================
void printArray(int array[], int size) {
for (int i = 0; i < size; i++) {
cout << array[i] << ” “;
}
cout << endl;
}
//=====================================================================
//Merge Short
//=====================================================================
void merge(char arr[], int p, int q, int r) {
int n1 = q – p + 1;
int n2 = r – q;
int L[n1], M[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];
int i, j, k;
i = 0;
j = 0;
k = p;
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = M[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = M[j];
j++;
k++;
}
}
void mergeSort(char arr[], int l, int r) {
if (l < r) {
int m = l + (r – l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
//=====================================================================
// Shell sort
//=====================================================================
void shellSort(char array[], int n) {
for (int interval = n / 2; interval > 0; interval /= 2) {
for (int i = interval; i < n; i += 1) {
int temp = array[i];
int j;
for (j = i; j >= interval && array[j – interval] > temp; j -= interval) {
array[j] = array[j – interval];
}
array[j] = temp;
}
}
}
//=====================================================================
// Quick Sort
//=====================================================================
void swap(int * a, int * b) {
int t = * a;
* a = * b;
* b = t;
}
int partition(int array[], int low, int high) {
int pivot = array[high];
int i = (low – 1);
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
i++;
swap( & array[i], & array[j]);
}
}
swap( & array[i + 1], & array[high]);
return (i + 1);
}
void quickSort(int array[], int low, int high) {
if (low < high) {
int pi = partition(array, low, high);
// recursive call on the left of pivot
quickSort(array, low, pi – 1);
quickSort(array, pi + 1, high);
}
}
//=====================================================================
// Buble Sort
//=====================================================================
void bubbleSort(int array[], int size) {
for (int step = 0; step < (size – 1); ++step) {
int swapped = 0;
for (int i = 0; i < (size – step – 1); ++i) {
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
swapped = 1;
}
}
if (swapped == 0)
break;
}
}
void printArrayNama(char array[], int size) {
for (int i = 0; i < size; i++) {
cout << array[i] << ” “;
}
cout << endl;
}
//=====================================================================
// Selection Sort
//=====================================================================
void swapp(int * a, int * b) {
int temp = * a;
* a = * b;
* b = temp;
}
void selectionSort(int array[], int size) {
for (int step = 0; step < size – 1; step++) {
int min_idx = step;
for (int i = step + 1; i < size; i++) {
if (array[i] < array[min_idx])
min_idx = i;
}
swapp( & array[min_idx], & array[step]);
}
}
void printArrayNim(int array[], int size) {
int i;
for (i = 0; i < size; i++)
cout << array[i] << ” “;
cout << endl;
}
//=====================================================================
//Void Menampilkan Hasil Akhir Pengurutan
//=====================================================================
void show() {
cout << endl;
cout << “====================================” << endl;
cout << “Anda memilih pengurutan Insertion sort” << endl;
cout << “====================================” << endl;
cout << “nama sebelum diurutkan :n”;
printArrayNamaSebelum(namaSebelum, sizenamaSebelum);
cout << endl;
cout << “nama setelah diurutkan :n”;
insertionSort(nama, 14);
cout << “——————————————” << endl;
cout << endl
<< endl;
cout << “Tekan Apa Saja Untuk Melanjutkan!” << endl;
}
void showMergeSort() {
cout << endl;
cout << “====================================” << endl;
cout << “Anda memilih pengurutan Marge Short” << endl;
cout << “====================================” << endl;
cout << “nama sebelum diurutkan :n”;
printArrayNamaSebelum(namaSebelum, sizenamaSebelum);
cout << endl;
cout << “nama setelah diurutkan :n”;
mergeSort(nama, 0, sizenama – 1);
printArrayNama(nama, sizenama);
cout << “——————————————” << endl;
cout << endl
<< endl;
cout << “Tekan Apa Saja Untuk Melanjutkan!” << endl;
}
void showShellSort() {
cout << endl;
cout << “====================================” << endl;
cout << “Anda memilih pengurutan Shell Short” << endl;
cout << “====================================” << endl;
cout << “nama sebelum diurutkan :n”;
printArrayNamaSebelum(namaSebelum, sizenamaSebelum);
cout << endl;
cout << “nama setelah diurutkan :n”;
shellSort(nama, sizenama);
printArrayNama(nama, sizenama);
cout << “——————————————” << endl;
cout << endl
<< endl;
cout << “Tekan Apa Saja Untuk Melanjutkan!” << endl;
}
void showQuickSort() {
cout << endl;
cout << “====================================” << endl;
cout << “Anda memilih pengurutan Quick Sort” << endl;
cout << “====================================” << endl;
cout << “NIM sebelum diurutkan :n”;
printArrayNimSebelum(NIMSebelum, sizeNIMSebelum);
cout << endl;
cout << “NIM setelah diurutkan :n”;
quickSort(NIM, 0, sizeNIM – 1);
printArray(NIM, sizeNIM);
cout << “——————————————” << endl;
cout << endl
<< endl;
cout << “Tekan Apa Saja Untuk Melanjutkan!” << endl;
}
void showBubblekSort() {
cout << endl;
cout << “====================================” << endl;
cout << “Anda memilih pengurutan Bubble Sort” << endl;
cout << “====================================” << endl;
cout << “NIM sebelum diurutkan :n”;
printArrayNimSebelum(NIMSebelum, sizeNIMSebelum);
cout << endl;
cout << “NIM setelah diurutkan :n”;
bubbleSort(NIM, sizeNIM);
printArray(NIM, sizeNIM);
cout << “——————————————” << endl;
cout << endl
<< endl;
cout << “Tekan Apa Saja Untuk Melanjutkan!” << endl;
}
void showSelectionkSort() {
cout << endl;
cout << “====================================” << endl;
cout << “Anda memilih pengurutan Selection Sort” << endl;
cout << “====================================” << endl;
cout << “NIM sebelum diurutkan :n”;
printArrayNimSebelum(NIMSebelum, sizeNIMSebelum);
cout << endl;
cout << “NIM setelah diurutkan :n”;
selectionSort(NIM, sizeNIM);
printArray(NIM, sizeNIM);
cout << “——————————————” << endl;
cout << endl
<< endl;
cout << “Tekan Apa Saja Untuk Melanjutkan!” << endl;
}
// Driver code
int main() {
int NIMSebelum[] = {2,1,1,0,8,1,7,1,1,0,0,0,8};
char namaSebelum[20] = {‘a’,’n’,’d’,’r’,’i’,’r’,’a’,’h’,’m’,’a’,’d’,’a’,’n’,’i’};
int sizeNIMSebelum = sizeof(NIM) / sizeof(NIM[0]);
int sizenamaSebelum = sizeof(nama) / sizeof(nama[0]);
int pilih;
do
{
cout << “==========================================” << endl;
cout << ” SORTING ” << endl;
cout << “==========================================” << endl;
cout << “1. Insertion Sort” << endl;
cout << “2. Merge Sort” << endl;
cout << “3. Shell Sort” << endl;
cout << “4. Quick Sort” << endl;
cout << “5. Bubble Sort” << endl;
cout << “6. Seletion Sort” << endl;
cout << “7. Exit” << endl;
cout << “——————————————” << endl;
cout << “Masukkan Pilihan : “;
cin >> pilih;
system(“cls”);
switch (pilih)
{
case 1:
show();
getch();
system(“cls”);
break;
case 2:
showMergeSort();
getch();
system(“cls”);
break;
case 3:
showShellSort();
getch();
system(“cls”);
break;
case 4:
showQuickSort();
getch();
system(“cls”);
break;
case 5:
showBubblekSort();
getch();
system(“cls”);
break;
case 6:
showSelectionkSort();
getch();
system(“cls”);
break;
case 7:
cout << “nn==========================================” << endl;
cout << “Exit…” << endl;
cout << “Program was made by Andri Rahmadani (2110817110008)” << endl;
cout << “==========================================” << endl;
exit(0);
break;
}
} while (pilih < 12);
}