SORTING

A.  Pengertian Sorting

Algoritma pengurutan (sorting algorithm) adalah algoritma yang mengurutkan data menggunakan aturan tertentu. Ada 2 macam, yaitu urut naik (ascending) dan urut turun descending)

a)  urut naik (ascending) yaitu dari data yang mempunyai nilai paling kecil sampai paling besar

b)    urut turun (descending) yaitu data yang mempunyai nilai paling besar sampai paling kecil.
 

    B.   Jenis-Jenis Sorting

1.      Bubble Sort

Bubble Sort (metode gelembung) adalah metode pengurutan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.

Kelebihan bubble sort :

·         Metode Bubble  Sort merupakan yang paling simple

·         Metode Bubble Sort muda di pahami algoritmanya

Kelemahan bubble sort

Saat mengurutkan data yang sangat besar akan mengalami kelambatan luar biasa, atau dengan kata lain kinerja memburuk cukup signifikan ketika data yang diolah jika  data cukup banyak. Kelemahan lain adalah jumlah pengulangan akan tetap sama jumlahnya walaupun data sesungguhnya sudah cukup terurut. Hal ini disebabkan setiap data dibandingkan dengan setiap data yang lain untuk menentukan posisinya.

2.      Merge Sort

Algoritma pengurutan data merge sort dilakukan dengan menggunakan cara divide and conquer yaitu dengan memecah kemudian menyelesaikan setiap bagian kemudian menggabungkannya kembali. Pertama data dipecah menjadi 2 bagian dimana bagian pertama merupakan setengah (jika data genap) atau setengah minus satu (jika data ganjil) dari seluruh data, kemudian dilakukan pemecahan kembali untuk masing-masing blok sampai hanya terdiri dari satu data tiap blok.
Setelah itu digabungkan kembali dengan membandingkan pada blok yang sama apakah data pertama lebih besar daripada data ke-tengah+1, jika ya maka data ke-tengah+1 dipindah sebagai data pertama, kemudian data ke-pertama sampai ke-tengah digeser menjadi data ke-dua sampai ke-tengah+1, demikian seterusnya sampai menjadi satu blok utuh seperti awalnya. Sehingga metode merge sort merupakan metode yang membutuhkan fungsi rekursi untuk penyelesaiannya.

3.      Quick Sort

Quick Sort adalah algoritma pengurutan yang sangat cepat dengan tipe penyelesaian divide and conquer. sehingga cocok untuk mengurutkan data dalam jumlah besar.

    C.    Contoh Program Sorting

1.      Bubble Sort

#include #include #define N 20 using namespace std; int bubble(int n); int i,j,A[N]; int jml; main() {             cout << "\t METODE BUBBLE SORT " <             cout <             cout << " Masukkan jumlah bilangan: "; cin >> jml;             cout <             for (i=0;i             {             cout << " Bilangan ke " << i+1 << " = ";             cin >> A[i];             }             cout <             bubble(jml);             cout << " Data yang sudah terurut : ";                         for (i=0;i             {                 cout <                 cout << "\t\t" << A[i];             } }     int bubble(int n)     {         int temp;         for (i=1;i<=n-1;i++)         {    for (j=i;j                {          if (A[i-1]>A[j])          {               temp = A[i-1];               A[i-1] = A[j];               A[j] = temp;           }    }          } }

                  Hasil Running 

2.      Merge Sort

#include #include using namespace std; int a[50]; void merge(int,int,int); void merge_sort(int low,int high) {     int mid;     if(low     {       mid=(low+high)/2;       merge_sort(low,mid);       merge_sort(mid+1,high);       merge(low,mid,high);      } } void merge(int low,int mid,int high) {      int h,i,j,b[50],k;      h=low;      i=low;      j=mid+1;      while((h<=mid)&&(j<=high))      {         if(a[h]<=a[j])         {             b[i]=a[h]; h++;         }         else         {            b[i]=a[j]; j++;         } i++;      }      if(h>mid)      {         for(k=j;k<=high;k++)         {             b[i]=a[k]; i++;         }      }      else      {         for(k=h;k<=mid;k++)         {             b[i]=a[k]; i++;         }      }      for(k=low;k<=high;k++)       a[k]=b[k]; } main() {  int num,i;      cout <<"     MERGE SORT " <      cout <      cout <<" Masukkan Banyak Bilangan: "; cin >> num;      cout <      for(i=1;i<=num;i++)      {       cout << " Bilangan ke "<> a[i] ;      }      merge_sort(1,num);      cout <      cout << " Hasil akhir pengurutan :";      for(i=1;i<=num;i++)          cout << " " << a[i]<< " ";  }

Hasil Running

3.      Quick Sort

#include #include using namespace std; void quick_sort(int arr[], int left, int right) {       int i = left, j = right;int tmp;       int pivot = arr[(left+right)/2];             while (i             {                         while (arr[i] < pivot)                         i++;                         while (arr[j] > pivot)                         j--;                         if (i<=j)             {                                     tmp = arr[i];                                     arr[i] = arr[j];                         arr[j] = tmp;                                     i++;j--;             }      }       if (left < j)             quick_sort(arr, left, j);       if (i < right)             quick_sort(arr, i, right); } int main() {     int i,n,data[50];     cout << " \t QUICK SORT " <     cout <     cout << " Masukan banyak bilangan : "; cin >> n;     cout <     for(i=0;i     {         cout << " Bilangan Ke " << i+1 << " = ";         cin >> data[i];     }     cout <     cout << " Bilangan sebelum diurutkan : ";     for(i=0;i     {         cout<     }     cout <     quick_sort(data,0,n-1);     cout << " Bilangan setelah pengurutan: ";     {         int i;         for (i=0;i         cout << data[i] << " ";         cout <     }     getch(); }

Hasil Running