Sorting and Searching di Bahasa C

Sorting dan Searching di Bahasa C

Sorting
Sorting merupakan proses mengurutkan angka atau nilai secara ascending maupun descending.
Secara dalam algoritma di bagi menjadi 2 yaitu :
1. Internal Sorting
Sorting dimana semua data di load ke dalam RAM.
2. Eksternal Sorting
Proses sorting dengan menggunakan penyimpanan ke dua.

Ada banyak jenis sorting, tapi yang akan di bahasa di sini adalah :
1. Simple sort

  • Bubble sort
  • Selection sort 
  • Insertion sort
2. Intermediate sort
  • Quick sort 
  • Merge sort
Bubble Sort 
Metode sorting dengan bubble sort adalah membandingkan dua buah nilai yang bersebelahan 
contoh:
void Bubble(int *DataArr, int n)
{
    int i, j;
    for(i=1; i<n; i++)
    for(j=n-1; j>=i; j--)
    if(DataArr[j-1] > DataArr[j])
               Swap(&DataArr[j-1],&DataArr[j]);
}


Selection Sort 
Mengambil Bilangan dan membandingkan nilainya dengan angka yang lain 
contoh:
for(i=0; i<N-1; i++){      /* N=number of data */

  Set idx_smallest equal to i
  for(j=i+1; j<N; j++){
  If array[ j ] < array [ idx_smallest ] then idx_smallest = j
    }
  Swap array[ i ] with array[ idx_smallest ]
}

Insertion Sort
mengambil 1 bilangan dan mengecek angka di sebelah nya dan jika kondisi dipenuhi misal lebih kecil dari bilangan yang diambil, bilangan tersebut akan di masukan ke dalam temp dan dilakukan swap dengan bilangan yang lebih besar 
contoh:





Quick Sort
Membagi array menjadi 2 dan kemudian menetukan pivot, biasa nya pivot yang diambil adalah array terakhir dan array pertama. jika diambil array terakhir dan pertama maka pivot akan bergerak ke kiri , dan array pertama akan bergerak ke kanan, kemudian dilakukan pengecekan apakah bilangan yang bergerak kanan lebih besar daripada pivot pertama, dan apakah bilangan ke kiri lebih kecil dibanding pivot terakhir jika kondisi terpenuhi maka akan dilakukan pengecekan berdasarkan kondisi misal lebih keci maka akan di cek apakah bilangan di sebelah kiri tadi lebih kecil dari bilangan di sebelah kanan , jika kondisi terpenuhi maka akan dilakukan swap antar bilangan tersebut.
contoh:
void QuickSort(int left, int right)
{
      if(left < right){
            //arrange elements  R[left],...,R[right] that
            //producing new sequence:
            R[left],...,R[J-1] < R[J] and R[J+1],...,R[right] > R[J].
            QuickSort(left, J-1);
            QuickSort(J+1, right);
       }
}

Merge Sort
Membagi 2 array sampai menjadi 1 kemudian membandingkan array yang berdekatan dan digabungkan kembali kedalam 1 array
contoh:

Searching
Merupakan proses menemukan angka atau value kunci atau nilai yang diinginkan dari sebuah array.
Beberapa jenis searching didalam algoritma:

  • Linear Searching
  • Binary Searching
  • Interpolitan Searching

Linear Searching
Metode ini membandingkan setiap element didalam array dengan nilai kunci atau nilai yang diinginkan
secara algoritma:
1. n : total record of array x.
2. For each x[i], 0 £  i £ n-1, check whether x[i] = key.
3. If x[i] = key, then the searched data is found in index=i. Finished.
4. If x[i] ¹ key, then continue searching until the last data which is i = n-1.
5. If i= n-1 and x[i] ¹ key, it means the data is not exist in the list, and set index = -1.
    Finished. 
Binary Searh
Untuk menggunakan binary search, array harus di urutkan terlebih dahulu untuk mempermudah
pencarian. Jika sudah dilakukan pengurutan array maka akan dicek apakah bilangan lebih besar atau 
lebih besar atau lebih kecil dari pada bilangan yang ingin dicari .
contoh :
secara algoritma
1. n : total record of array x.
2. left=0,  right= n-1.
3. mid =(int) (left + right)/2.
4. If x[mid]=key then index = mid. Finished.
5. If x[mid]<key then left = mid+1.
6. If x[mid]>key then right = mid-1.
7. If left £ right and x[mid] ¹ key, then repeat point 3.
8. If x[mid] ¹ key then index = -1. Finished.
Interpolitan Search
Dalam interpolitan search value kunci dapat di cari dengan langsung menunjuk urutan array dengan rumus:
secara algoritma :
1.In the interpolation search, we'll split the data according to the following formula
2.If data[mid] = sought data, data has been found, searching is stopped and return
mid.
3.If data[mid]!= sought data, repeat point **
4.**Searching is continued while sought data > data[min] and sought data <
data[max].
5.Looking for a mid value by entering into the interpolation formula
6.If data[mid] > sought data, high = mid – 1
7.If data[mid] < sought data, low = mid + 1
8.It will be looped until the requirements point ** are not met then return (-1), data not
found



Komentar

Posting Komentar

Postingan populer dari blog ini

Function dan Recursion di Bahasa C

Function dan Recursion di Bahasa Pemogramman C a. Function Function merupakan kumpulan statement yang mengambil input, melakukan perhitungan yang diperlukan dan menghasilkan output. Fungsi dapat membantu dalam menghemat penulisan kode yang sering di tulis berulang ulang, karena kumpulan statement dan perhitungan yang sering di lakukan dapat di masukan ke dalam suatu fungsi yang dapat di panggil secara berulang. Fungsi juga dapat membuat program lebih terstruktur dan efesien sehingga program tersebut lebih mudah di pahami dan dibaca. Fungsi sendiri terbagi menjadi 2 jenis yaitu function yang di buat sendiri dan function yang sudah ada di dalam library c seperti di dalam fungsi string.h (strlen,strcpy,strstr,dll). Contoh pembuatan fungsi yang sederhana #include<stdio.h> int jumlah(int a, int b){ int sum=a+b; return sum; int main (){ int angka1,angka2; scanf("%d %d", &angka1,&angka2); printf("%d", jumlah(angka1,angka2); testcase input ...
Baca selengkapnya

Pointer dan Array Dalam Bahasa Pemogramaman C

A. Pointer      Pointer merupakan suatu jenis variabel yang dapat menunjuk alamat memori dari variabel yang lain. Variabel biasanya memiliki sebuah alamat karen dalam deklarasi ,programa akan mengalokasikan alamat untuk variabel tersebut. Dapat dianalogikan variabel seperti rumah dan isi dari rumah tersebut adalah 5, setiap rumah pasti memiliki sebuah alamat, untuk mendeklarasikan alamat tersebut maka di gunakan pointer dengan simbol bintang (*). Simbol bintang tersebut di tambahkan di depan variabel yang akan di deklarasikan. bentuk dasar dari pointer adalah : #include<stdio.h> int main(){ int a=15; int *p; p=&a; printf("%d",*p); return 0; } B. Array      Array merupakan kumpulan dari nilai yang bertipe data yang sama dengan urutan tertentu. Array dapat memungkinkan kita untuk menyimpan data dalam jumlah yang banyak dan terindeks. Array dapat di ibaratkan seperti loker besar yang menyimpan buku (tipe data 1) dan tidak mungkin kita d...
Baca selengkapnya