SORTING

SORTING

Sorting 

            merupakan tindakan mengurutkan yang dibutuhkan untuk mempercepat operasi pencarian di sebuah list yang memiliki dua tipe sorting ascending(atas ke bawah atau awal ke akhir) dan descending(bawah ke atas atau akhir ke awal).

Sorting dibagi menjadi dua macam:

A. Simple sorting

• Bubble sort
• Selection sort
• Insertion sort

B. Intermediate sorting

• Quick sort
• Merge sort

SIMPLE SORTING

1. Bubble sort
Membandingkan antara dua nilai, membandingkan dan menukar (bila perlu) dikenal juga sebagai exchange sort.

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]);

}

2. Selection sort

Membandingkan angka pertama dengan setelahnya, jika angka pertama lebih kecil maka akan ditukar angka tersebut dan menjadi pembanding, apabila data telah habis dan pembanding merupakan angka terkecil maka diletakan paling depan atau paling besar maka diletakan  paling belakang

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 ]

}

3. Insertion sort

Membandingkan dengan memilih satu angka dan jika angka tersebut lebih kecil maka diselipkan di angka setelahnya dan apabila angka yang dipilih telah memiliki tempat maka akan memilih angka baru yang lain untuk dibandingkan sampai terurut

Contoh:

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

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

}

INTERMEDIATE SORTING

1. Quick sort

Mengambil sebuah nilai sebut sebagai pivot lalu membagi yang lebih kecil kekiri(bagian angka kecil) dan lebih besar kekanan(bagian angka besar) lalu mengecek bagian yang lebih besar dari pivot di ambil satu nilai sebagi pivot kedua lalu bandingkan lagi dibagian angka besar.

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);

       }

}

2.Merge sort

Membagi list yang tidak teratur menjadi n bagian kecil list lalu ulangi buat bagian kecil list hingga tersisa satu nilai.

Contoh:

1 2 2 3 4 5 6 6

2 4 5 6                  1 2 3 6

2 5            4 6              1 3           2 6

5         2           4          6         1        3           2        6