sorting

1.     Buatlah 1 contoh program insertion sort.

   #include "stdio.h"

int main()
{
    int L[20],temp,i,j,n=6;
    printf("pengurutan berdasarkan Insertion sort \nmasukkan %d elements: \n",n);
    for(i=0;i<n;i++){
        scanf("%d",&L[i]);}

    printf("\nsebelum sorting: ");

    for(i=0;i<n;i++){printf("%d ",L[i]);}

    for(i=1;i<n;i++){
    /*5 7 3 1 ===> 5 7 3 1, (5 7 7 1, 5 5 7 1, 3 5 7 1), (3 5 7 7, 3 5 5 7, 3 3 5 7, 1 3 5 7)*/
        temp=L[i];
        j=i-1;
        while((temp<L[j])&&(j>=0)){
            L[j+1]=L[j];
            j=j-1;
        }
        L[j+1]=temp;
    }

    printf("\nsetelah sorting: ");
    for(i=0;i<n;i++){printf("%d ",L[i]);}
    printf("\n");

                                                                                 

2.     Tuliskan pengertian sorting menurut pendapat anda masing-masing

     Sorting merupakan suatu proses untuk menyusun kembali himpunan obyek menggunakan aturan tertentu. Sorting disebut juga sebagai suatu algoritma untuk meletakkan kumpulan elemen data kedalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen. Pada dasarnya ada dua macam urutan yang

 biasa digunakan dalam suatu proses sorting: 

1. Urut naik (ascending)
   Mengurutkan dari data yang mempunyai nilai paling kecil sampai paling besar

. Urut turun (descending)

   Mengurutkan dari data yang mempunyai nilai paling besar sampai paling kecil.

Mengapa harus melakukan sorting data? Ada banyak alasan dan keuntungan dengan mengurutkan data. Data yang terurut mudah untuk dicari, mudah untuk diperiksa, dan mudah untuk dibetulkan jika terdapat kesalahan. Data yang terurut dengan baik juga mudah untuk dihapus jika sewaktu-waktu data tersebut tidak diperlukan lagi. Selain itu, dengan mengurutkan data maka kita semakin mudah untuk menyisipkan data atapun melakukan penggabungan data.

Metode-metode sorting meliputi:

1. Insertion Sort (Metode Penyisipan)
2. Selection Sort (Metode Seleksi)
3. Bubble sort(Metode Gelembung)
4. Shell Sort (Metode Shell)
5. Quick Sort (Metode Quick)
6. Merge Sort (Metode Penggabungan)

3.Buatlah contoh program buble sort dalam bahasa pascal

{Program Buble Sort}

uses crt;
var i,j,k,temp,n :integer;
a,b,c :array[1..100] of integer;
begin
clrscr; textcolor(12);
write('Banyaknya elemen Array : ');readln(n);
{input data}
for i:=1 to n do a[i]:=random(1000);
    {cetak array sebelum urut}
    writeln;textcolor(15);write('Sebelum diurutkan: ');
    for i:=1 to n do write (a[i],' ');
        writeln;
        textcolor(15);writeln('process pengurutan bubble : ');
        for i:=1 to n-1 do begin
             for j:=n downto i+1 do begin
                  if a[j-1]>a[j] then begin
                        temp:=a[j-1]; a[j-1]:=a[j]; a[j]:=temp;
                  End;
             end;
             {cetak array tiap langkah pengurutan}
             writeln;write('hasil akhir langkah ke - ',i,' : ');
             for k:=1 to n do write(a[k],' ');
         end;
         {cetak array setelah pengurutan}
          writeln;writeln;
         textcolor(15);write('hasil pengurutan bubble : ');
         for i:=1 to n do write (a[i],' ');
         readln;
end.

4.Tuliskan algoritma quick rekursif.

#include <iostream>
using namespace std;
void cetak(int n)
{
if(n<=4)
cetak(n+1);
cout<<n<<endl;
}

int main(int argc, char *argv[])
{
cout<<“Hasil dengan cara menggunakan rekursif: “;
cetak(1);
system(“PAUSE”);
return EXIT_SUCCESS;
}

5.Sebutkan dan jelaskan metode-metode sorting

Macam-macam Sorting:

·         Buble Sort :

Merupakan algoritma pengurutan paling tua dengan metode pengurutan paling sederhana. Pengurutan yang dilakukan dengan membandingkan masing-masing item dalam suatu list secara berpasangan, menukar item jika diperlukan, dan mengulaginya sampai akhir list secara berurutan, sehingga tidak ada lagi item yang dapat ditukar.

·         Selection Sort :

Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.

·         Insertion Sort :

Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan dan yang sudah diurutkan. Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.

·         Shell Sort :

Merupakan algoritma yang stau jenis dengan insertion sort, dimana pada setiap nilai i dalam n/i item diurutkan. Pada setiap pergantian nilai, i dikurangi sampai 1 sebagai nilai terakhir

author: wikipedia

·         Merge Sort :

Algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort.

1. Divide                                        

Memilah elemen – elemen dari rangkaian data menjadi dua bagian.

2. Conquer

Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif

3. Kombinasi

Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan

Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.

author : Swfung8

·         Quick Sort :

Algoritma ini berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini hanya mengikuti langkah – langkah sebagai berikut :

1. Divide

Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.

2. Conquer

Mengurutkan elemen pada sub-rangkaian secara rekursif. Pada algoritma quicksort, langkah ”kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array

Author: Matt Chan

·         Heap Sort:

Heap sort adalah sorting yang menggunakan struktur data heap, dengan nilai parent selalu lebih besar dari pada nilai childnya.

Algoritma:

1.       Buat suatu heap.

2.       Ambil isi dari root masukkan kedalam sebuah array.

3.       Hapus element root dengan mempertahankan properti heap.

4.       Ulangi sampai tree menjadi kosong