sorting adalah sebuah proses merangkai benda dalam urutan tertentu dan/ atau himpunan
yang berbeda,oleh karena itu sorting mempunyai dua kategori yang berbeda
- Pengurutan : merangkai benda sejenis, sekelas dll. dalam urutan tertentu
- kategorisasi : Pengelompokan dan pemberian label kepada benda dengan sifat yang serupa
Pada dasarnya sorting dapat di bagi menjadi lima seperti gambar di atas
Teknik sorting dapat di bagi menurut tingkat kesulitan yaitu:
Sorting sederhana:
-Bubble sort
-Selection sort
-Insertion sort
Sorting lanjutan:
- Merge sort
-Quick sort
Sorting menurut jenis pengurutan:
- Ascending
pengurutan di mulai dari nilai terkecil menuju nilai terbesar
-Descending
penguruan di mulai dari nilai terbesar menuju nilai terkecil
fungsi untuk menukar dua buah data
void tukar(int *a,int *b){
int t=*a;
*a=*b;
*b=t;
}
Metode pengurutan Data:
- Pengurutan berdasarkan perbandingan(comparison-based sorting)
contoh: bubble sort,exchange sort
- Pengurutan berdasarkan prioritas(priority queue soritng method)
contoh: Selection sort, heap sort
- Pengurutan berdasarkan penyisipan dan penjagaan terurut(insert and keep sorted method)
contoh:insertion sort, tree sort
- pengurutan berdasarkan pembagian dan penguasaan(devine and conquer method)
contoh: quick sort, merge sort
- pengurutan berkurang menurun
contoh: shell sort
- Diberi nama “Bubble” karena proses pengurutan secara berangsurangsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda
- Metode temudah namun merupakan metode yang paling lambat
- Membandingkan dua data yang bersebelahan, yaitu elemen sekarang dengan elemen berikutnya
- Membandingkan dan menukar jika sesuai dengan persyaratan
contoh algoritma:
catatan:
- lettakkan fungsi tukar di atas fungsi bubble,atau letakkan prototipe di atas fungsi bubble
- Jika ingin mengubah menjadi descending tinggal mengubah tanda menjadi "<" di sintax "if"
proses bubble sort:
catatan: banyaknya putaran=banyaknya angka di kurang satu(n-1)
putaran pertama
putaran ke dua
Putaran ke tiga
putaran ke empat
putaran ke lima
Putaran ke enam
putaran ke tujuh
pengurutan dengan cara di atas merupakan bentuk sorting ascending
Kelemahan :
- walaupun data sudah terurut namun perbandingan tetap di lakukan
- -Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu di ambil dan di sisipkan(insert) ke tempat yang seharusnya
-Pengurutan di mulai dari data yang ke 2 sampai dengan data terakhir,
jika di temukan data yang lebih kecil, maka akan di tempatkan(di insert) di posisi
yang seharusnya
-Pada penyisipan elemen,maka elemen-elemen lain bergeser ke belakang.
contoh algoritma:
for(i=1; i
x = A[i], sisipkan x pada tempatnya yang
sesuai antara A[0] s/d A[i-1].
}
Proses insertion:
putaran pertama
Putaran ke dua
Putaran ke tiga
Putaran ke empat
Putaran ke lima
Putaran ke enam
Putaran ke tujuh
Merupakan kombinasi antara sorting dan searching
Proses pengurutannya dengan mencari elemen-elemen yang memiliki nilai terkecil dan di tukar dengan nilai terbesar
selama proses perbandingan dan perubahan hanya di lakukan pada index pembanding saja
contoh proses:
Data yang di urutkan di bagi menjadi 2 bagian dan ditempatkan di 2 array yang berbeda
merge sort membutuhkan 3 array, 1 array untuk menempatkan hasilnya dan sisanya merupakan data yang akan diurutkan
ke 2 array tersebut di urutkan masing-masing kemudian di simpan pada masing-masing array dan di gabungkan pada array yang pertama
contoh proses:
Merupakan metode yang sangat cepat dengan teori algoritma yang mudah, namun dalam penulisan programnya sangat sulit
merupakan kombinasi antara metode exchange sort dan metode merge sort
ada 4 langkah dalam melakukan metode ini yaitu:
- if(n<=1),maka kembali ke awal atau menghentikan proses
- Ambil satu elemen dari array sebagai pusat(pivot)
- Array di pecah menjadi 2 bagian, pecahan array pertama terdiri dari elemen yang lebih besar pivot, sedangkan pecahan array ke 2 memiliki elemen yang lebih kecil dari pivot
- Kemudian ke dua pecahan proses tersebut melakukan proses pengurutan
contoh proses:
Pola pergerakan elemen
referensi :
