Sorting & Searching

Sorting & Searching:

–       Bubble Sort

–       Selection Sort

–       Insertion Sort

–       Quick Sort

–       Merge Sort

–        Linear Search

–        Binary Search

–        Interpolation Search

SORTING 

sorting di gunakan untuk mempercepat pencarian di dalam list.

TYPE SORTING

- ASCENDING

- DESCENDNG

ALGORITHEM FOR SORTING

1. INTERNAL SORTING

data yang di sort mengunakan RAM

2. EXTERNAL SORTING

menyorting dengan mengunakan data cadangan

SORTING

SIMPLE SORTING

1. Bubble sort 

2. Selection sort

3. Insertion sort

INTERMEDIATE SORTING

1. Quick sort

2. Merge sort

BUBBLE SORT

Membandingkan dua value di tukar apa bila di perlukan yang juga dikenal sebagai pertukaran secara sorting Syntax:

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

 

Algorithm:

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 ]}

 

 UNSERTION SORT

 

Algorithm:

for(i=1; i<n; i++) {

     x = A[i], insert x to its suitable place between A[0] and A[i-1].

}

 QUICK SORT

Algorithm:

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

MERGE SORT adalah sorting algoritma berdasarkan pembagian dan pengumpulan algoritm

–Divide: divide the input data in two disjoint subsets

–Recur: solve the sub problems associated with subsets

–Conquer: combine the solutions for each subset into a solution

 

SEARCHING

                   Kami akan sering bekerja dengan sejumlah besar data yang disimpan dalam array Mungkin perlu untuk menentukan apakah suatu array berisi nilai yang cocok dengan nilai kunci tertentu Proses pencarian elemen tertentu dari suatu array disebut pencarian

 

        Several types of searching algorithm:

–Linear Search

Pencarian linear membandingkan setiap elemen dari array dengan kunci pencarian. Karena larik tidak dalam urutan tertentu, kemungkinan besar nilainya akan ditemukan di elemen pertama seperti yang terakhir Oleh karena itu, rata-rata, program harus membandingkan kunci pencarian dengan setengah elemen dari array 

–Binary Search

Metode pencarian linier berfungsi baik untuk array kecil atau tidak disortir. Namun, untuk pencarian linear array besar tidak efisien Jika susunan diurutkan, teknik pencarian binari berkecepatan tinggi dapat digunakan

–Interpolation Search 

Teknik pencarian interpolasi dilakukan pada data yang diurutkan
Proses pencarian ini hampir mirip dengan teknik pencarian biner
Teknik pencarian dilakukan dengan perkiraan lokasi data

 Philip kwandynata 2201736366 BINUS