TUGAS SORTING

1. Buatlah 1 contoh program insertion sort.
2. Tuliskan pengertian sorting menurut pendapat anda masing – masing.
3. Buatlah contoh prgram buble sort dalam bahasa pascal
4. Tuliskan algoritma quick recursif.
5. Sebutkan dan jelaskan metode – metode sorting.

Contoh program insertion sort

#include <stdio.h>

int main()

{

  int n, array[1000], c, d, t;

  printf("Enter number of elements\n");

  scanf("%d", &n);

  printf("Enter %d integers\n", n);

  for (c = 0; c < n; c++) {

    scanf("%d", &array[c]);

  }

for (c = 1 ; c <= n - 1; c++) {

    d = c;

    while ( d > 0 && array[d] < array[d-1]) {

      t          = array[d];

      array[d]   = array[d-1];

      array[d-1] = t;

      d--;

    }

  }

  printf("Sorted list in ascending order:\n");

  for (c = 0; c <= n - 1; c++) {

    printf("%d\n", array[c]);

  }

  return 0;

}

PENGERTIAN SORTING

 sorting  adalah sebuah metode untuk pengurutan data, misalnya dari data yang terbesar ke data yang terkecil. Dengan cara program yang dibuat harus dapat membandingkan antar data yang di inputkan.
Artinya jika ada deretan data, maka data yang pertama akan membandingkan dengan data yang kedua. Jika data yang pertama lebih besar dari pada data yang kedua maka data yang pertama akan bertukar posisi dengan data yang kedua, begitu seterusnya sampai benar-benar data terurut dari yang terbesar hingga yang terkecil.

Contoh Prgram Buble Sort Dalam Bahasa Pascal

program bubble_sort_polma;

uses crt;

var

 i,n,j : integer;

 a : array [1..10] of integer;

procedure urutkan;

 var

  z : integer;

  begin

   for i:=1 to n-1 do

    begin

         for j:=n downto i+1 do

          begin

           if a[j] > a[j-1] then

            begin

z:=a[j];

                 a[j]:=a[j-1];

                 a[j-1]:=z;

                end;

          end;

    end;

  end;

begin

 clrscr;

 writeln('Program : Mengurutkan Nilai menggunakan Bubble Sort');

  writeln;

 write ('Masukkan banyak data yang ingin di urut : '); readln(n);

 for i:=1 to n do

  begin

   write ('Data ',i,' : '); readln(a[i]);

  end;

 urutkan;

 write('Data setelah diurutkan : ');

 for j:=1 to n do

  write (a[j],' ');

readln;

end.

Algoritma Quick Recursif

Algoritma quick Rekursif dapat dituliskan sebagai berikut :

Algoritma Quick Sort terdiri dari dua prosedur, yaitu prosedur PARTISI dan prosedur QUICKSORT. Berikut pseudocode dari algoritma quick sort :

Procedure quick_sort (I/O A : TabelInt, input i,j : integer )

{ Mengurutkan table A [i..j] dengan algoritma Quick Sort, dengan pemilihan pivot menggunakan elemen median table.

    Masukan : Tabel [i..j] yang sudah terdefinisi elemen-elemennya.

    Keluaran : Tabel [i..j] yang terurut secara asc }

Kamus

     p,q,temp, pivot : integer

Algoritma

   p         i

   q          j

   pivot       A[(p+q) div 2]

repeat

while A[p] < pivot do

           p         p + 1

endwhile

while A[q] > pivot do

          q         q - 1

endwhile

if p £ q then

temp         A[p]

              A[p]          A[q]

              A[q]          temp

              p         p +1

              q         q - 1

endif

until p > q    

if i < q then

quick_sort (A, i, q)

endif

if j > p then

quick_sort (A, p, j)

endif

Algoritma diatas termasuk dalam algoritma mempartisi dan algoritma mengurutkan dimana algoritma partisi untuk dapat menuju keadaan terurut tidaklah sukar lagi, setelah membagi tabel maka diterpkan lagi procedure yang sama pada keadaan bagian, procedure diatas mengktifkan dirinya sendiri secara rekursif.

Metode – metode Sorting

BUBBLE SORT

Bubble sort adalah proses pengurutan sederhana yang bekerja dengan cara berulang kali membandingkan dua elemen data pada suatu saat dan menukar elemen data yang urutannya salah. Ide dari Bubble sort adalah gelembung air yang akan “mengapung” untuk table yang terurut menaik (ascending). Elemen bernilai kecil akan “diapungkan” (ke indeks terkecil), artinya diangkat ke “atas” (indeks terkecil) melalui pertukaran. Karena

algoritma ini melakukan pengurutan dengan cara membandingkan elemen-elemen data satu sama lain, maka bubble sort termasuk ke dalam jenis algoritma comparison-based sorting.

Proses dalam Bubble sort dilakukan sebanyak N-1 langkah (pass) dengan N adalah ukuran array. Pada akhir setiap langkah ke – I , array L[0..N] akan terdiri atas dua bagian, yaitu bagian yang sudah terurut L[0..I] dan bagian yang belum terurut L[I+1..N-1]. Setelah langkah terakhir, diperoleh array L[0..N-1] yang terurut menaik.

Untuk mendapatkan urutan yang menaik, algoritmanya dapat ditulis secara global sebagai berikut :

Untuk setiap pass ke – I = 0,1,………., N-2 , lakukan :

Mulai dari elemen J = N-1, N-2,….., I + 1, lakukan :

Bandingkan L[J-1] dengan L[J]

Pertukarkan L[J-1] dengan L[J] jika L[J-1] > L[J]

Rincian setiap pass adalah sebagai berikut :

Pass 1:      I = 0. Mulai dari elemen J = N-1,N–2,…,1, bandingkan L[J-1] dengan L[J]. Jika L[J-1] > L[J], pertukarkan L[J-1] dengan L[J]. Pada akhir langkah 1, elemen L[0] berisi harga minimum pertama.

Pass 2:      I = 1. Mulai dari elemen J = N-1,N–2,…,2, bandingkan L[J-1] dengan L[J]. Jika L[J-1] > L[J], pertukarkan L[J-1] dengan L[J]. Pada akhir langkah 2, elemen L[1] berisi harga minimum kedua dan array L[0..1] terurut, sedangkan L[2..(N-1)] belum terurut.

Pass 3:      I = 2. Mulai dari elemen J = N-1,N–2,…,3, bandingkan L[J-1] dengan L[J]. Jika L[J-1] > L[J], pertukarkan L[J-1] dengan L[J]. Pada akhir langkah 3, elemen L[2] berisi harga minimum ketiga dan array L[0..2] terurut, sedangkan L[3..(N-1)] belum terurut.

Pass N-1:  Mulai dari elemen J = N-1, bandingkan L[J-1] dengan L[J]. Jika L[J-1] > L[J], pertukarkan L[J-1] dengan L[J].

Pada akhir langkah N-2, elemen L[N-2] berisi nilai minimun ke [N-2] dan array L[0..N-2] terurut menaik (elemen yang tersisa adalah L[N-1], tidak perlu diurut karena hanya satu-satunya).

Misal array L dengan N = 5 buah elemen yang belum terurut. Array akan diurutkan secara ascending (menaik).

0      1     2     3      4

Pass 1 :

I = 0 ;J= N-1= 4                      8          9          7          1          6

J = 3                            8          9          1          7          6

J = 2                            8          1          9          7          6

J = 1                            1          8          9          7          6

Hasil akhir langkah 1 :

0      1       2      3      4

 

Pass 2 :

I = 1 ;J= N-1= 4                      1          8          9          6          7

J = 3                            1          8          6          9          7

J = 2                            1          6          8          9          7

Hasil akhir langkah 2 :

0       1      2      3      4

Pass 3 :

I = 2 ;J= N-1= 4                      1          6          8          7          9

J = 3                            1          6          7          8          9

Hasil akhir langkah 3 :

Metode Selection Sort
Selection Sort berbeda dengan Bubble sort. Selection Sort pada dasarnya memilih data yang akan diurutkan menjadi dua bagian, yaitu bagaian yang sudah diurutkan dan bagian yang belum di urutkan.
Langkah pertama dicari data terkecil dari data pertama sampai data terakhir. Kemudian data terkecil ditukar dengan data pertama. Dengan demikian, data pertama sekarang mempunyai nilai paling kecil dibanding data yang lain. Langkah kedua, data terkecil kita cari mulai dari data kedua sampai terakhir. Data terkecil yang kita peroleh ditukar dengan data kedua dan demikian seterusnya sampai semua elemen dalam keadaan terurutkan. Metode ini lebih efektif dari pada metode bubble karena tidak memerlukan banyak pertukaran dan pengalokasian memori.