Sorting

Hay guys, mungkin di antara kalian pada gak tau kan apa itu Sorting? apa itu Bubble Sort (bukan Bubble yang di jual pop ice yyaa). yukk kita liat apa aja sihh pengertian Sorting

Sorting / bisa di bilang pengurutan adalah suatu proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu ( untuk data yang bertipe numerik atau karakter).

mungkin gak semua kita tau kalau sorting / pengurutan ada 2 macam yaitu :

1. Ascending (urut naik) merupakan pengurutan dari angka yang nilainya lebih kecil kemudian menuju ke nilainya yang lebih besar.
2.   Descending (urut turun) adalah sebaliknya, yaitu pengurutan dari nilainya yang lebih besar kemudian menuju ke nilainya yang lebih kecil.

 hhhmmmm mungkin belom begitu mengerti yaa.. apa yang di maksud, biar anda mengerti saya kasih contoh

Hasil yang di Sorting

•    Ascending adalah 0   2   3   5   8   9 

•   Descending adalah  9   8   5   3   2   0

nahh.. Sorting ada banyak macam-macam nya nihh, tentu nya ada 7 macam nihhh yaitu :

1. Bubble Sort  
2. Exchange Sort 
3. Selection Sort
4. Insertion Sort
5. Shell Sort
6. Merge Sort   
7. Quick Sort  

1. Bubble Sort  

Memindahkan element sekarang dengan elemen berikutnya , jika elemen sekarang itu lebih besar / lebih kecil dari elemen berikutnya maka berpindah (bisa di bilang di tukar posisi).

Proses Bubble Sort

• 1.       Ascending

• Data yang paling awal dibandingkan dengan data berikutnya jika ternyata lebih besar maka di tukar.
• Data yang paling akhir dibandingkan dengan data sebelumya jika ternyata lebih kecil maka di tukar.

• 2.       Descending

• Data yang paling awal dibandingkan dengan data berikutnya jika ternyata lebih kecil maka di tukar.
• Data yang paling akhir dibandingkan dengan data sebelumya jika ternyata lebih besar maka di tukar.

 Contoh Bubble Sort
Ascending (Urutan Naik) 

 

Sudah mangerti kahh anda dengan type Bubble Sort? yukk kita liat Pseudocode dari Bubble Sort :

# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]

# Start with the largest gap and work down to a gap of 1
[[foreach]] (gap in gaps)
{
    # Do a gapped insertion sort for this gap size.
    # The first gap elements a[0..gap-1] are already in gapped order
    # keep adding one more element until the entire array is gap sorted
    for (i = gap; i < n; i += 1)
    {
        # add a[i] to the elements that have been gap sorted
        # save a[i] in temp and make a hole at position i
        temp = a[i]
        # shift earlier gap-sorted elements up until the correct location for a[i] is found
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        # put temp (the original a[i]) in its correct location
        a[j] = temp
    }
}

2. Exchange Sort

Exchange sort itu sangat mirip dengan buble sort. Bahkan banyak yang mengatakan bahwa exchange sort sama dengan buble sort. Bedanya hanya jika bubble sort proses pertukarannya harus sistematis (dari awal atau dari belakang) Sedangkan exchange sort proses pertukaran hanya akan dilakukan jika diperlukan saja.

Proses Exchange Sort

1.       Ascending

• Jika terdapat elemen sebelumnya lebih besar dari elemen berikutnya maka tukar.
• Jika terdapat elemen sesudahnya lebih kecil dari elemen sebelumnya maka tukar.

2.       Descending

•   Jika terdapat elemen sebelumnya lebih kecil dari elemen berikutnya maka tukar.
•   Jika terdapat elemen sesudahnya lebih besar dari elemen sebelumnya maka tukar.

Contoh Exchange Sort

Ascending (Urutan Naik)

 

 

 

Saya rasa anda pahan maksud dari Exchange sort? yukk kita liat Pseudocode dari Exchange sort :

void ExchangeSort(apvector <int> &num)
{
     int i, j;
     int temp;   // holding variable
     int numLength = num.length( ); 
     for (i=0; i< (numLength -1); i++)    // element to be compared
    {
          for(j = (i+1); j < numLength; j++)   // rest of the elements
         {
                if (num[i] < num[j])          // descending order
               {
                        temp= num[i];          // swap
                        num[i] = num[j];
                        num[j] = temp;
               }
          }
     }
     return;
}

 

3. Selection Sort

Memindahkan elemen dengan cara membandingkan elemen sekarang dengan elemen yang berikutnya sampai dengan elemen terakhir . Jika ditemukan elemen lain yang lebih kecil / lebih besar dari elemen sekarang maka dicatat posisinya dan kemudian ditukar dan begitu seterusnya.                 

Proses Selection Sort

1.       Ascending

•   Elemen yang paling besar diletakkan di akhir.
•   Elemen yang paling kecil diletakkan di awal.

2.       Descending

•   Elemen yang paling kecil diletakkan di akhir.
•   Elemen yang paling besar diletakkan di awal.

Contoh Selection Sort

Ascending (Urutan Naik)

   Insertion Sort

Yukkk kita liat  Pseudocode dari Selection Sort :

procedure selection sort 
   list  : array of items
   n     : size of list

   for i = 1 to n - 1
   /* set current element as minimum*/
      min = i    
  
      /* check the element to be minimum */

      for j = i+1 to n 
         if list[j] < list[min] then
            min = j;
         end if
      end for

      /* swap the minimum element with the current element*/
      if indexMin != i  then
         swap list[min] and list[i]
      end if

   end for
 
end procedure

4.  Insertion Sort

Pengurutan yang dilakukan dengan cara membandingkan dengan data ke-2 sampai data terakhir. Jika ditemukan data yang lebih kecil atau lebih besar maka data tersebut disisipkan kedepan sesuai posisi yang seharusnya.

Contoh Insertion Sort

Ascending (Urutan Naik)

 Nihh saya kasih tau Pseudocode dari type Insertion Sort :

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert
 
   for i = 1 to length(A) inclusive do:
 
      /* select value to be inserted */
      valueToInsert = A[i]
      holePosition = i
      
      /*locate hole position for the element to be inserted */
  
      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while
  
      /* insert the number at hole position */
      A[holePosition] = valueToInsert
      
   end for
 
end procedure

5. Shell Sort

Merupakan proses pengurutan data yang sebelumnya acak menjadi data yang terurut dengan cara menentukan jarak antar elemen yang akan dibandingkan.

Contoh  Shell  Sort

Ascending (Urutan Naik)

 

Boleh di coba guys Pseudocode dari type Shell Sort

procedure shellSort()
    A : array of items 
 
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1     
   end while
   
   while interval > 0 do:

      for outer = interval; outer < A.length; outer ++ do:

      /* select value to be inserted */
      valueToInsert = A[outer]
      inner = outer;

         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

      /* insert the number at hole position */
      A[inner] = valueToInsert

      end for

   /* calculate interval*/
   interval = (interval -1) /3;   

   end while
   
end procedure

6. Merge Sort

Merupakan proses pengurutan data yang menggunakan merging dua buah vector. Pada proses merge sort, data dibuat sepasang-sepasang, yang terdiri dari dua elemen. Jika N ganjil, maka ada satu vector yang terdiri dari 1 elemen. Lalu kemudian data tersebut di merging sampai terurut.

Contoh Merge Sort

Ascending (Urutan Naik)

Pseudocode dari type Merge Sort :

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array

   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
   
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
   
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
   
   return c
 
end procedure

7. Quick Sort

Merupakan proses penyusunan elemen yang membandingkan suatu elemen (pivot) denan elemen yang lain, dan menyusunnya sedemikian rupa sehingga elemen –elemen lain yang lebih kecil dari pivot terletak disebelah kiri pivot. Dan elemen yang lebih besar dari pivot terletak disebelah kanan pivot.

Dengan demikian akan terbentuk dua sublist, yang terletak disebelah kanan dan kiri pivot. Lalu pada sublist kiri dan kanan itu kita anggap sebuah list baru, dan kita kerjakan proses yang sama seperti yang sebelumnya. Demikian seterusnya sampai tidak terdapat sublist lagi.

Contoh Quick Sort

Ascending (Urutan Naik)

 

 

 

Pada belom tau kan Pseudocode dari type Quick Sort?? boleh di coba guys Pseudocode nya :

function partitionFunc(left, right, pivot)
   leftPointer = left -1
   rightPointer = right

   while True do
      while A[++leftPointer] < pivot do
         //do-nothing            
      end while
  
      while rightPointer > 0 && A[--rightPointer] > pivot do
         //do-nothing         
      end while
  
      if leftPointer >= rightPointer
         break
      else                
         swap leftPointer,rightPointer
      end if
  
   end while 
 
   swap leftPointer,right
   return leftPointer
 
end function

 sumber :Disini