Contoh Program Bahasa C++ Tentang Quick Sort Dan Merge Sort
1. algoritma pengurutan quick sort secara ascending
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 20
int Partition(int arr[], int p, int r)
{
int i, j;
int pivot, temp;
pivot = arr[p]; // pivot pada index 0
i = p;
j = r;
while (i <= j)
{
while (pivot < arr[j])
j--;
while (pivot > arr[i])
i++;
if (i < j)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
j--;
i++;
}
else
return j;
}
return j;
}
void QuickSort(int arr[], int p, int r)
{
int q;
if (p < r)
{
q = Partition(arr, p, r);
QuickSort(arr, p, q);
QuickSort(arr, q + 1, r);
}
}
int main()
{
int data_awal[MAX], data_urut[MAX];
int i;
time_t k1, k2;
printf("Sebelum pengurutan : \n");
for (i = 0; i < MAX; i++)
{
srand(time(NULL) * (i + 1));
data_awal[i] = rand() % 100 + 1;
printf("%d ",
data_awal[i]);
}
printf("\nSetelah pengurutan : \n");
for (i = 0; i < MAX; i++)
data_urut[i] = data_awal[i];
time(&k1);
QuickSort(data_urut, 0, MAX - 1);
time(&k2);
for (i = 0; i < MAX; i++)
printf("%d ", data_urut[i]);
printf("\nWaktu = %ld\n", k2 - k1);
}
2. algoritma pengurutan merge sort secara ascending.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 20
void Merge(int arr[], int left, int median, int right)
{
int temp[MAX];
int kiri1, kanan1, kiri2, kanan2, i, j;
kiri1 = left;
kanan1 = median;
kiri2 = median + 1;
kanan2 = right;
i = left;
while ((kiri1 <= kanan1) && (kiri2 <= kanan2))
{
if (arr[kiri1] <= arr[kiri2])
{
temp[i] = arr[kiri1];
kiri1++;
}
else
{
temp[i] = arr[kiri2];
kiri2++;
}
i++;
}
while (kiri1 <= kanan1)
{
temp[i] = arr[kiri1];
kiri1++;
i++;
}
while (kiri2 <= kanan2)
{
temp[i] = arr[kiri2];
kiri2++;
i++;
}
j = left;
while (j <= right)
{
arr[j] = temp[j];
j++;
}
}
void MergeSort(int arr[], int l, int r)
{
int med;
if (l < r)
{
med = (l + r) / 2;
MergeSort(arr, l, med);
MergeSort(arr, med + 1, r);
Merge(arr, l, med, r);
}
}
int main()
{
int data_awal[MAX], data_urut[MAX];
int i;
time_t k1, k2;
printf("Sebelum pengurutan : \n");
for (i = 0; i < MAX; i++)
{
srand(time(NULL) * (i + 1));
data_awal[i] = rand() % 100 + 1;
printf("%d ", data_awal[i]);
}
printf("\nSetelah pengurutan : \n");
for (i = 0; i < MAX; i++)
data_urut[i] = data_awal[i];
time(&k1);
MergeSort(data_urut, 0, MAX - 1);
time(&k2);
for (i = 0; i < MAX; i++)
printf("%d ", data_urut[i]);
printf("\nWaktu = %ld\n", k2 - k1);
}
0 comments:
Posting Komentar