Apa itu Sort dalam C++?
Sort dalam C++ adalah konsep di mana elemen-elemen array disusun ulang dalam urutan yang logis. Urutan ini bisa dari terendah ke tertinggi atau tertinggi ke terendah. Mengurutkan array yang tidak disortir membantu menyelesaikan banyak masalah seperti mencari elemen minimum atau maksimum, dll.
Menyusun berbagai hal secara terurut akan memudahkan analisis dan pencarian elemen tertentu di antara kumpulan elemen.
Misalnya, dalam contoh di bawah ini, kita mengurutkan atau menata elemen-elemen array yang tidak diurutkan dalam urutan menaik, yakni dari terendah ke tertinggi.
Kategori Sort dalam C++
Kategori Sort adalah:
- Penyortiran internal
- Penyortiran eksternal
Kita tahu bahwa semua program disimpan di dalam hard disk, dan setiap kali kita menjalankan program di C++ , program itu akan masuk ke RAM.
Dalam pengurutan internal, data yang akan diurutkan ada di memori utama atau RAM, dan proses pengurutan juga akan terjadi di memori utama itu sendiri. Contoh pengurutan internal adalah pengurutan gelembung , pengurutan penyisipan , pengurutan pemilihan.
Sedangkan pada kasus pengurutan eksternal, data tidak selalu ada di RAM karena datanya besar. Jadi data diisi di RAM atau memori utama dalam porsi kecil. Contoh pengurutan eksternal adalah pengurutan Merge.
Jenis-jenis Teknik Sortiran
Ada berbagai jenis teknik pengurutan dalam C++. Kita akan mempelajari yang paling populer dalam artikel ini.
- Sortir gelembung
- Sortir seleksi
- Urutkan penyisipan
- Urutkan cepat
Sortir Gelembung
Bubble sort merupakan salah satu algoritma pengurutan yang paling mudah. Dalam teknik pengurutan ini, kita mulai dengan membandingkan dua elemen pertama dari array dan memeriksa apakah elemen pertama lebih besar dari elemen kedua; jika ya, kita akan menukar elemen-elemen tersebut dan beralih ke elemen berikutnya.
Jika elemen pertama tidak lebih besar dari elemen kedua, maka kita tidak perlu menukarnya. Dan proses ini akan terus berulang hingga akhir array.
contoh Pemrograman Bubble sort :
Seperti yang bisa kita lihat pada contoh di atas, kita memiliki array berisi elemen yang tidak diurutkan
12, 3, 1, 5, 18, 10, 7 dan 35. Dua perulangan for digunakan untuk mengurutkan larik ini, perulangan for pertama melakukan iterasi dari 0 hingga 8, dan perulangan kedua mengulangi dari i+1 hingga 8. Kapan i berada pada 0, maka j akan berada pada 0+1 yaitu indeks 1, sehingga akan terjadi perbandingan antara elemen pada indeks1 dan elemen 0.
QUICK SORT
Quick Sort merupakan metode tercepat dalam proses pengurutan data dengan menggunakan prinsip rekursif. Metode ini menggunakan strategi “pecah-belah” dengan mekanisme berikut ini.
CONTOH QUICK SORT
Sortir Seleksi
Dalam teknik pengurutan pilihan, elemen terkecil diambil dengan membandingkan dirinya dengan elemen lainnya dan diurutkan berdasarkan posisi pertama array. Array lengkap dibagi menjadi dua bagian, subarray yang diurutkan di sebelah kiri dan subarray yang tidak disortir di sebelah kanan. Setelah elemen pertama diurutkan, pencarian elemen minimum kedua dimulai dari sisa array dan ditempatkan di tempat kedua.
contoh Selection Sort
Seperti yang dapat kita lihat pada contoh, kita telah mengambil input array dari pengguna. Elemen-elemen array ini tidak diurutkan. Jadi dengan menggunakan sorting pilihan, kita akan mengurutkan elemen-elemen array ini.
Perulangan for pertama akan diulang dari 0 ke angka-1. Di dalam blok perulangan for, elemen pertama ditugaskan ke variabel min ini dan indeks elemen ke variabel P.
Setelah itu, loop for lainnya digunakan untuk melakukan iterasi dari j+1 ke num. Di dalam perulangan for, terdapat pernyataan if yang menyatakan bahwa jika arr[j] lebih kecil dari elemen min, kita akan menetapkan elemen tersebut ke variabel min, dan demikian pula, kita akan menetapkan indeks elemen tersebut ke P.
Karena indeks ditetapkan ke P, maka kita akan menukar arr[i] dengan arr[P]. Setelah pertukaran selesai, kami akan mencetak array yang diurutkan.
Insertion Sort
Dalam teknik pengurutan ini, elemen diurutkan dengan cara membandingkan elemen tersebut dengan elemen sebelumnya. Dimulai dengan membandingkan elemen kedua dengan elemen pertama. Jika elemen kedua lebih kecil dari elemen pertama, maka kita akan menukarnya.
Setelah itu, kita akan membandingkan elemen ketiga dengan semua elemen sebelumnya. Begitu pula dengan elemen keempat dan seterusnya. Setelah semua perbandingan dilakukan, elemen-elemen tersebut akan diurutkan.
Merge Sort
Merge Sort adalah salah satu algoritma pengurutan paling populer yang didasarkan pada prinsip Algoritma Divide and Conquer .
Di sini, suatu masalah dibagi menjadi beberapa sub-masalah. Setiap sub-masalah diselesaikan secara individual. Terakhir, sub-masalah digabungkan untuk membentuk solusi akhir.
Contoh Pemrograman Merge Sort
#include <iostream>
using namespace std;
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
int i = 0;
int j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = { 38, 27, 43, 3, 9, 82, 10 };
int arrSize = sizeof(arr) / sizeof(arr[0]);
cout << "Array sebelum diurutkan:" << endl;
printArray(arr, arrSize);
mergeSort(arr, 0, arrSize - 1);
cout << "Array setelah diurutkan:" << endl;
printArray(arr, arrSize);
return 0;
}
0 Comments