Materi Sorting

 Sorting

Outline

Sorting Definition
Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
·         Sorting Definition
·         Sorting of number, alphabet, word or other value with certain rule
·        
Illustrate problem
solving
·        
Technique of using
selection, looping, method and array
·        
Demonstrate
perform/algorithm complexity
·        
Accelerate searching
process
·         Sorting Algorithm
·         Basic sorting algorithm:

·         Bubble Sort

·         Insertion Sort

·         Selection Sort

·         Advanced sorting algorithm:

·         Merge Sort

·         Quick Sort

·         Bucket Sort

·         Shell Sort

·         Radix Sort

·         External Sort

·         Bubble Sort
·         Also call as sinking sort or exchange sort

·         Ascending : sorting from small to big

·         Descending : sorting from big to small

·         Value into array

·         Adjacent value compared

·         If increasing, then change to become  decreasing

·         At round:

·         1, array at 1 (index 0) is a smallest value

·         2, array at 2 (index 1)  is a second smallest value

·         n-1, array at n (index n-1) is a biggest value

·         Number of round = n-1

·         Prosedur swap
·         void swap(int& a, int& b) {
·        
    int
temp = a;
·        
    a
= b;
·        
    b
= temp;
·        
}
·         bubbleSort
·         void bubbleSort(int arr[], int n) {
·        
    for
(int i = 0; i < n - 1; i++) {
·        
        for
(int j = n - 1; j > i; j--) {  // Mulai dari belakang
·        
            if
(arr[j] < arr[j - 1]) {
·        
                swap(arr[j],
arr[j - 1]);
·        
            }
·        
        }
·        
    }
·        
}
·         main
·         int main() {
·        
    int
arr[] = {5, 1, 4, 2, 8};
·        
    int
n = sizeof(arr) / sizeof(arr[0]);
·        
    bubbleSort(arr,
n);
·        
    for
(int i = 0; i < n; i++) {
·        
        cout
<< arr[i] << " ";
·        
    }
·        
    cout
<< endl;
·        
    return
0;
·        
}
·         election Sort
·         Value sent into array

·         Search for the biggest value put at the end of array

·         At round:

·         1, array at 1 (index 0) is a small value

·         2, array at 2 (index 1) is a second small value

·         n-1, array at n (index n-1) is a biggest value

·         Number of round = n-1

·         Kode selectionSort
·         void selectionSort(int arr[], int n) {
·        
    for
(int i = n - 1; i >= 0; i--) {
·        
        int
maxIdx = 0;
·        
        for
(int j = 1; j <= i; j++) {
·        
            if
(arr[j] > arr[maxIdx]) {
·        
                maxIdx
= j;
·        
            }
·        
        }
·        
        //
Tukar elemen terbesar dengan elemen di posisi i
·        
        swap(arr[maxIdx],
arr[i]);
·        
    }
·        
}
·         main
·         int main() {
·        
    int
arr[] = {64, 25, 12, 22, 11};
·        
    int
n = sizeof(arr) / sizeof(arr[0]);
·        
    
·        
    cout
<< "Array sebelum sorting: ";
·        
    for
(int i = 0; i < n; i++) {
·        
        cout
<< arr[i] << " ";
·        
    }
·        
    cout
<< endl;
·        
    
·        
    selectionSort(arr,
n);
·        
    
·        
    cout
<< "Array setelah sorting descending: ";
·        
    for
(int i = 0; i < n; i++) {
·        
        cout
<< arr[i] << " ";
·        
    }
·        
    cout
<< endl;
·        
    
·        
    return
0;
·        
}
·         Insertion Sort
·         Value sent into array
·        
Using helper container
·        
Value compared with
index previously
·        
Every round did not
produce the biggest value or the smallest value.
·        
Number of round = n-1
·         Kode Insertion
·         void insertionSort(int arr[], int n) {
·        
    for
(int i = 1; i < n; i++) {
·        
        int
key = arr[i];
·        
        int
j = i - 1;
·        
        
·        
        //
Geser elemen yang lebih besar dari key ke kanan
·        
        while
(j >= 0 && arr[j] > key) {
·        
            arr[j
+ 1] = arr[j];
·        
            j--;
·        
        }
·        
        
·        
        //
Sisipkan key di posisi yang tepat
·        
        arr[j
+ 1] = key;
·        
    }
·        
}
·         main
·         int main() {
·        
    int
arr[] = {12, 11, 13, 5, 6};
·        
    int
n = sizeof(arr) / sizeof(arr[0]);
·        
    
·        
    cout
<< "Array sebelum sorting: ";
·        
    for
(int i = 0; i < n; i++) {
·        
        cout
<< arr[i] << " ";
·        
    }
·        
    cout
<< endl;
·        
    
·        
    insertionSort(arr,
n);
·        
    
·        
    cout
<< "Array setelah sorting: ";
·        
    for
(int i = 0; i < n; i++) {
·        
        cout
<< arr[i] << " ";
·        
    }
·        
    cout
<< endl;
·        
    
·        
    return
0;
·        
}
·         Kode Lengkap
·         #include <iostream>
·         using namespace std;
·          
·         void insertionSort(int arr[], int n) {
·             for (int i = 1; i < n; i++) {
·                 int key = arr[i];
·                 int j = i - 1;
·                 
·                 // Geser elemen yang lebih besar dari key ke kanan
·                 while (j >= 0 && arr[j] > key) {
·                     arr[j + 1] = arr[j];
·                     j--;
·                 }
·                 
·                 // Sisipkan key di posisi yang tepat
·                 arr[j + 1] = key;
·             }
·         }
·         int main() {
·        
    int
arr[] = {12, 11, 13, 5, 6};
·        
    int
n = sizeof(arr) / sizeof(arr[0]);
·        
    
·        
    cout
<< "Array sebelum sorting: ";
·        
    for
(int i = 0; i < n; i++) {
·        
        cout
<< arr[i] << " ";
·        
    }
·        
    cout
<< endl;
·        
    
·        
    insertionSort(arr,
n);
·        
    
·        
    cout
<< "Array setelah sorting: ";
·        
    for
(int i = 0; i < n; i++) {
·        
        cout
<< arr[i] << " ";
·        
    }
·        
    cout
<< endl;
·        
    
·        
    return
0;
·        
}
·         Merge Sort
·         Value sent into array
·        
divided data become
two based on index
·        
Each one sorted
·        
Re-Merge data 
·         Kode merge
·         // Fungsi untuk menggabungkan dua bagian array yang sudah terurut
·        
void
merge(vector<int>& arr, int left, int mid, int right) {
·        
    int
n1 = mid - left + 1;
·        
    int
n2 = right - mid;
·        
    
·        
    //
Buat array sementara
·        
    vector<int>
L(n1), R(n2);
·        
    
·        
    //
Salin data ke array sementara
·        
    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];
·        
    
·        
    //
Gabungkan array sementara kembali ke arr
·        
    int
i = 0, j = 0, k = left;
·        
    while
(i < n1 && j < n2) {
·        
        if
(L[i] <= R[j]) {
·        
            arr[k]
= L[i];
·        
            i++;
·        
        }
else {
·        
            arr[k]
= R[j];
·        
            j++;
·        
        }
·        
        k++;
·        
    }
·         / Salin sisa elemen
·             while (i < n1) {
·                 arr[k] = L[i];
·                 i++;
·                 k++;
·             }
·             while (j < n2) {
·                 arr[k] = R[j];
·                 j++;
·                 k++;
·             }
·         }
·          
·         // Fungsi rekursif untuk merge sort
·         void mergeSort(vector<int>& arr, int left, int right) {
·             if (left < right) {
·                 int mid = left + (right - left) / 2;
·                 
·                 // Urutkan bagian kiri dan kanan
·                 mergeSort(arr, left, mid);
·                 mergeSort(arr, mid + 1, right);
·                 
·                 // Gabungkan
·                 merge(arr, left, mid, right);
·             }
·         }
·         main
·         int main() {
·        
    vector<int>
arr = {12, 11, 13, 5, 6, 7};
·        
    int
n = arr.size();
·        
    
·        
    cout
<< "Array sebelum sorting: ";
·        
    for
(int i : arr) cout << i << " ";
·        
    cout
<< endl;
·        
    
·        
    mergeSort(arr,
0, n - 1);
·        
    
·        
    cout
<< "Array setelah sorting: ";
·        
    for
(int i : arr) cout << i << " ";
·        
    cout
<< endl;
·        
    
·        
    return
0;
·        
}
·         int main() {
·        
    vector<int>
arr = {12, 11, 13, 5, 6, 7};
·        
    int
n = arr.size();
·        
    
·        
    cout
<< "Array sebelum sorting: ";
·        
    for
(int i : arr) cout << i << " ";
·        
    cout
<< endl;
·        
    
·        
    mergeSort(arr,
0, n - 1);
·        
    
·        
    cout
<< "Array setelah sorting: ";
·        
    for
(int i : arr) cout << i << " ";
·        
    cout
<< endl;
·        
    
·        
    return
0;
·        
}
·         Kode Lengkap
·         #include <iostream>
·         #include <vector>
·          
·         using namespace std;
·          
·         // Fungsi untuk menggabungkan dua bagian array yang sudah terurut
·         void merge(vector<int>& arr, int left, int mid, int right) {
·             int n1 = mid - left + 1;
·             int n2 = right - mid;
·             
·             // Buat array sementara
·             vector<int> L(n1), R(n2);
·             
·             // Salin data ke array sementara
·             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];
·             
·             // Gabungkan array sementara kembali ke arr
·             int i = 0, j = 0, k = left;
·             while (i < n1 && j < n2) {
·                 if (L[i] <= R[j]) {
·                     arr[k] = L[i];
·                     i++;
·                 } else {
·                     arr[k] = R[j];
·                     j++;
·                 }
·                 k++;
·             }
·             
·             // Salin sisa elemen
·             while (i < n1) {
·                 arr[k] = L[i];
·                 i++;
·                 k++;
·             }
·         Exercise
·         Create a program that allows to input user authentication details, show the inputted data, sorting name data by ascending. 

Komentar

Posting Komentar

Postingan populer dari blog ini

Tugas 4 C++

Gambar
  Program Bilangan Positif atau Negatif Program ini digunakan untuk menentukan apakah sebuah bilangan yang diinputkan pengguna termasuk positif, negatif, atau nol. Cara kerja singkat: Program meminta pengguna memasukkan sebuah bilangan. Jika bilangan lebih dari 0, program menampilkan “Positif”. Jika bilangan kurang dari 0, program menampilkan “Negatif”. Jika bilangan sama dengan 0, program menampilkan “Nol”. Percabangan menggunakan if, else if, dan else. Program Menghitung Diskon Total Belanja Program ini digunakan untuk menghitung total pembayaran setelah diskon berdasarkan total belanja. Cara kerja singkat: Program meminta pengguna memasukkan total belanja. Jika total belanja lebih dari 200.000, maka: iberikan diskon 10%. Program menampilkan pesan bahwa pengguna mendapat diskon. Jika total belanja kurang dari 200.000, maka: Tidak ada diskon. Program menampilkan total bayar setelah potongan. Menggunakan percabangan if–else. Deskripsi Program Penentuan Nilai H...
Baca selengkapnya

Tugas 1 C++

Gambar
 Nama : Widya Shafitri Prodi : Teknik Informatika Fakultas : Ilmu komputer dan Sistem Informasi Volume Tabung Program ini menerima input jari-jari dan tinggi dari pengguna, lalu menghitung volume tabung menggunakan rumus matematika, dan menampilkan hasilnya di layar. Luas Lingkaran Program ini dibuat untuk menghitung luas lingkaran. Pengguna cukup memasukkan nilai jari-jari lingkaran, kemudian program akan memprosesnya dengan menggunakan rumus luas lingkaran ( L = π × r² ). Setelah itu, hasil perhitungan akan ditampilkan di layar sebagai output. Keliling Persegi Panjang Program ini meminta input panjang dan lebar dari pengguna, lalu menghitung keliling persegi panjang dengan rumus: K = 2 × ( p a n j a n g + l e b a r ) K = 2 × ( p anjan g + l e ba r ) Volume Kerucut Program ini menerima input jari-jari alas dan tinggi dari pengguna, lalu menghitung volume kerucut dengan rumus: V = 1 3 × π × r 2 × t V = 3 1 ​ × π × r 2 × t dengan keterangan: r  = jari-jari alas t  = tinggi...
Baca selengkapnya

Materi Fungsi dan Prosedur

 Fungsi dan Prosedur Dalam C++ Fungsi Fungsi merupakan sekelommpok statement yang digabung untuk melakukan suatu pekerjaan. Setiap program c++ pasti minimal memiliki satu fungsi “main()”, Deklarasi fungsi Deklarasi fungsi membutuhkan nama fungsi, tipe kembalian, dan parameter. Definisi fungsi tipe_balikan nama_fungsi(daftar_parameter) {             //kode fungsi return nilai_balikan; } Bagian dari fungsi Tipe balikan: Sebuah fungsi boleh mempunyai nilai balikan. Tipe_balikan merupakan tipe data dari nilai tersebut. Nama fungsi: Nama yang digunakan untuk pemanggilan fungsi Bagian dari fungsi-2 Daftar parameter: daftar variabel masukan yang dibutuhkan oleh sebuah fungsi. Kode fungsi: kode yang akan dieksekusi saat fungsi dipanggil. Contoh fungsi Int penambahan(int a, int b) { } Contoh pemanggilan fungsi Int x = 10; Int y = 20; Int hasil = penambahan (x,y); Prosedur Prosedur merupakan fungsi yang tidak mempunynai nilai balikan. Nilai balikannnya didefinis...
Baca selengkapnya