Sorting

Seputar Sorting
Sort adalah proses pengurutan data yang sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut suatu aturan tertentu. 

Beberapa Jenis Sorting
Empat teknik pengurutan yaitu: 
  1. Bubble Sort: mengurutkan elemen dengan memindahkan elemen yang sekarang dengan elemen yang berikutnya, jika elemen sekarang nilainya lebih besar (>) dari elemen berikutnya, maka tukar posisi.
  2. Selection Sort: teknik yang membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang maka dicatat posisinya dan kemudian ditukar. Dan begitu seterusnya.
  3. Insertion Sort: pengurutan dilakukan dengan cara membandingkan data ke-I (dimana I dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai posisi yang seharusnya.
  4. Quick Sort: Quick Sort akan membandingkan suatu elemen (pivot) dengan elemen yang lain sehingga elemen-elemen lain yang lebih kecil dari pivot tersebut terletak di sebelah kirinya dan elemen-elemen lain yang lebih besar dari pivot tersebut terletak di sebelah kanannya.
Syarat Sorting
Bubble Sort
  1. Jumlah iterasi sama dengan banyaknya bilangan dikurang 1. 
  2. Di setiap iterasi, jumlah pertukaran bilangannya sama dengan jumlah banyaknya bilangan. 
  3. Dalam algoritma Bubble Sort, meskipun deretan bilangan tersebut sudah terurut, proses sorting akan tetap dilakukan. 
  4. Tidak ada perbedaan cara yang berarti untuk teknik algoritma Bubble Sort Ascending dan Descending.

Selection Sort
Menggunakan  metode  pengurutan dengan mencari nilai data terkecil dimulai dari data diposisi 0 hingga diposisi N-1. Jika terdapat N data dan data terkoleksi dari urutan 0 sampai dengan N-1 maka algoritma pengurutan dengan metode selection sort adalah sebagai berikut:
  1. Cari data terkecil dalam interval  j= 0 sampai dengan j= N-1 
  2. Jika pada posisi  pos ditemukan data yang terkecil, tukarkan data diposisi  pos dengan data di posisi  i jika k. 
  3. Ulangi langkah 1 dan 2 dengan j= j+i sampai dengan j= N-1, dan seterusnya sampai  j = N

Insertion Sort
  1. Insertion sort seperti proses pengurutan kartu yang berada di tangan kita. 
  2. Algorithma ini dapat mengurutkan data dari besar ke kecil (Ascending) dan kecil ke besar (Descending). 
  3. Algoritma ini tidak cocok untuk set data dengan jumlah besar karena kompleksitas dari algorithma ini adalah Ο() di mana n adalah jumlah item.

Quick Sort
  1. Memilih satu elemen secara acak sebagai pivot 
  2. Memindahkan semua elemen yang lebih kecil ke sebelah kiri pivot dan semua elemen yang lebih besar ke sebelah kanan pivot. Elemen yang nilainya sama bisa disimpan di salah satunya. 
  3. Melakukan sort secara rekursif terhadap sub-array sebelah kiri dan kanan pivot

Contoh Sorting
1. Bubble Sort
Code C++:
//JUDUL: Mengurutkan bilangan dengan bubble sort
#include <iostream>
using namespace std;
//KAMUS GLOBAL
int arr[] = {34, 98, 17, 70, 6, 29};
int total_array;
//DESKRIPSI

//JUDUL: Prosedur berparameter untuk menampung dan menukar nilai
//procedure nampung(*a, *b : integer)
void nampung(int *a, int *b)
{
    //KAMUS LOKAL: Tidak ada
    int temp;
    //DESKRIPSI
    temp = *a;
    *a = *b;
    *b = temp;
}

//JUDUL: Prosedur berparameter array untuk bubble sort
//procedure bubble_sort(arr: array of integer, n : integer)
void bubble_sort(int arr[], int n)
{
    //KAMUS LOKAL: Tidak ada
    //DESKRIPSI
    for (int i = 0; i < n-1; i++){
        for (int j = 0; j < n-i-1; j++){
            if (arr[j] > arr[j+1]){
                nampung(&arr[j], &arr[j+1]);
            }
        }
    }


}

//JUDUL: Prosedur berparameter untuk mengoutputkan array
//procedure hasil(arr: array of integer, jumlah : integer)
void hasil(int arr[], int jumlah)
{
    //KAMUS LOKAL: Tidak ada
    //DESKRIPSI
    for (int i = 0; i < jumlah; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main()
{
    cout << "Mengurutkan bilangan dengan bubble sort" << endl;
    total_array = sizeof(arr)/sizeof(arr[0]);
    cout<<"Sebelum diurutkan: \n";
    hasil(arr, total_array);

    bubble_sort(arr, total_array);
    cout<<"Setelah diurutkan: \n";
    hasil(arr, total_array);
    return 0;
}

Hasil Code:
Mengurutkan bilangan dengan bubble sort
Sebelum diurutkan:
34 98 17 70 6 29
Setelah diurutkan:
6 17 29 34 70 98

2. Selection Sort
Code C++:
#include<iostream>
using namespace std;

void outputArray(int *arr, int jumlah) {
   for(int i = 0; i<jumlah; i++){
      cout << arr[i] << " ";
   }
   cout << endl;
}
void selectionSort(int *arr, int jumlah) {
   int i, j, tukar;
	i = 0;
	while(i < jumlah - 1){
        tukar = i;
        j = i + 1;
        while(j < jumlah){
            if(arr[j] < arr[tukar]){
                tukar = j;
            }
            j = j+1;
        }
        swap(arr[tukar], arr[i]);
        i = i + 1;
	}
}

void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

int main() {
   int n;
   cout << "Masukkan jumlah: "; cin >> n;
   int arr[n];
   for(int i = 0; i<n; i++) {
      cin >> arr[i];
   }
   cout << "Sebelum di sorting ";
   outputArray(arr, n);
   selectionSort(arr, n);
   cout << "Sesudah di sorting: ";
   outputArray(arr, n);

}

Hasil Code:
Masukkan jumlah: 6
34 98 17 70 6 29
Sebelum di sorting 34 98 17 70 6 29 
Sesudah di sorting: 6 17 29 34 70 98

3. Insertion Sort
Code C++:
#include<iostream>
using namespace std;

void outputArray(int *arr, int jumlah) {
   for(int i = 0; i<jumlah; i++){
      cout << arr[i] << " ";
   }
   cout << endl;
}
void insertionSort(int *arr, int jumlah) {
   int key, j;
   for(int i = 1; i<jumlah; i++) {
      key = arr[i];
      j = i;
      while(j > 0 && arr[j-1]>key) {
         arr[j] = arr[j-1];
         j--;
      }
      arr[j] = key;
   }
}
int main() {
   int n;
   cout << "Masukkan jumlah: "; cin >> n;
   int arr[n];
   for(int i = 0; i<n; i++) {
      cin >> arr[i];
   }
   cout << "Sebelum di sorting ";
   outputArray(arr, n);
   insertionSort(arr, n);
   cout << "Sesudah di sorting: ";
   outputArray(arr, n);
}

Hasil Code:
Masukkan jumlah: 6
34 98 17 70 6 29
Sebelum di sorting 34 98 17 70 6 29 
Sesudah di sorting: 6 17 29 34 70 98

4. Quick Sort
Code C++:
//JUDUL: Mengurutkan bilangan dengan quick sort
#include <iostream>
using namespace std;
//KAMUS GLOBAL
int arr[] = {34, 98, 17, 70, 6, 29};
int total_array;
//DESKRIPSI

//JUDUL: Prosedur berparameter untuk menampung dan menukar nilai
//procedure nampung(*a, *b : integer)
void nampung(int *a, int *b)
{
    //KAMUS LOKAL: Tidak ada
    int temp;
    //DESKRIPSI
    temp = *a;
    *a = *b;
    *b = temp;
}

//JUDUL: Fungsi berparameter array untuk mengatur kembali array
//function partisi(arr : array of integer, terendah : integer, tertinggi : integer) --> integer
int partisi(int arr[], int terendah, int tertinggi) {
    //KAMUS LOKAL:
    int titik_utama;
    int i;
    //DESKRIPSI
    titik_utama = arr[tertinggi];
    i = (terendah - 1);
    for (int j = terendah; j < tertinggi; j++) {
        if (arr[j] <= titik_utama) {
            i++;
            nampung(&arr[i], &arr[j]);
        }
    }
    nampung(&arr[i + 1], &arr[tertinggi]);
    return (i + 1);
}

//JUDUL: Prosedur berparameter array untuk quick sort
//procedure quick_sort(arr : array of integer, terendah : integer, tertinggi : integer)
void quick_sort(int arr[], int terendah, int tertinggi) {
    //KAMUS LOKAL:
    int hasil_akhir;
    //DESKRIPSI
    if (terendah < tertinggi) {
        hasil_akhir = partisi(arr, terendah, tertinggi);
        quick_sort(arr, terendah, hasil_akhir - 1);
        quick_sort(arr, hasil_akhir + 1, tertinggi);
  }
}
//JUDUL: Prosedur berparameter untuk mengoutputkan array
//procedure hasil(arr: array of integer, jumlah : integer)
void hasil(int arr[], int jumlah)
{
    //KAMUS LOKAL: Tidak ada
    //DESKRIPSI
    for (int i = 0; i < jumlah; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main()
{
    cout << "Mengurutkan bilangan dengan quick sort" << endl;
    total_array = sizeof(arr)/sizeof(arr[0]);
    cout<<"Sebelum diurutkan: \n";
    hasil(arr, total_array);

    quick_sort(arr, 0, total_array - 1);
    cout<<"Setelah diurutkan: \n";
    hasil(arr, total_array);
    return 0;
}

Hasil Code:
Mengurutkan bilangan dengan quick sort
Sebelum diurutkan:
34 98 17 70 6 29
Setelah diurutkan:
6 17 29 34 70 98

Komentar

Posting Komentar

Postingan populer dari blog ini

Microsoft PowerPoint

Gambar
Apa itu Microsoft PowerPoint ? Microsoft Office Power Point Microsoft PowerPoint adalah sebuah program aplikasi Microsoft Office yang berguna sebagai media presentasi dengan menggunakan beberapa slide. Aplikasi ini sangat digemari dan banyak digunakan dari berbagai kalangan, baik itu pelajar, perkantoran dan bisnis, pendidik, dan trainer. Kehadiran powerpoint membuat sebuah presentasi berjalan lebih mudah dengan dukungan fitur yang sangat menarik dan canggih. Fitur template atau desain juga akan mempercantik sebuah presentasi PowerPoint. Sejarah Microsoft PowerPoint   Microsoft Powerpoint dikembangkan pertama kali oleh Bob Gaskins dan Dennis Austin. Waktu itu, Microsoft PowerPoint digunakan sebagai presenter untuk perusahaan Forethought, Inc yang kemudian namanya diubah menjadi PowerPoint. PowerPoint versi 1 dirilis pada tahun 1987 dan komputer yang didukungnya adalah Apple Macintosh. Kala itu powerpoint masih menggunakan warna hitam putih saja dan mam...
Baca selengkapnya