SORTING - Konsep Dasar, Selection Sort, Insertion Sort

Pengurutan (Sorting)

Seringkali perancang program perlu mengurutkan sekumpulan data yang dimiliki untuk memudahkan pemrosesan selanjutnya terhadap data tersebut. 

Pengurutan adalah sebuah algoritma dasar yang sering diperlukan dalam pembuatan program.

Berbagai algoritma pengurutan telah diciptakan dan dapat digunakan. Pemahaman tentang beberapa algoritma pengurutan dasar perlu diketahui, termasuk cara

penggunaannya dalam program.

Pengertian Sort

Sorting atau pengurutan data adalah proses yang sering harus dilakukan dalam pengolahan data. Sort dalam hal ini diartikan mengurutkan data yang berada dalam suatu tempat penyimpanan, dengan urutan tertentu baik urut menaik (ascending) dari nilai terkecil sampai dengan nilai terbesar, atau

urut menurun (descending) dari nilai terbesar sampai dengan nilai terkecil. Sorting adalah proses pengurutan.

Pengurutan internal (internal sort), yaitu   pengurutan terhadap sekumpulan data yang disimpan dalam media internal komputer yang dapat diakses setiap elemennya secara langsung. Dapat dikatakan sebagai pengurutan tabel

Pengurutan eksternal (external sort), yaitu pengurutan data yang disimpan dalam memori sekunder, biasanya data bervolume besar sehingga tidak mampu untuk dimuat semuanya dalam memori.

Didalam Sorting terdapat 8 Metode Sort, akan tetapi disini kita akan membahas 2 diantaranya saja yaitu :

• Selection Sort
• Insertion Sort

1. Selection Sort

Inti dari algoritme selection sort adalah menemukan elemen tertinggi dan terendah di array acak lalu menempatkannya di posisi yang semestinya.

Diketahui array A=[7,5,4,2]A=[7,5,4,2] akan disortir dengan urutan ascending (urutan naik).

Elemen terendah pada array, 22, akan dicari dan ditukar posisinya dengan elemen di posisi teratas, yaitu 77. Sekarang pencarian dilakukan untuk menemukan elemen terendah yang ada di array awal yang belum beraturan dan menempatkannya di posisi kedua, dan seterusnya.

mari kita lihat implementasinya

 

pada iterasi ith, elemen dari posisi 0 hingga i -1 akan diurutkan

 

Komplesitas Waktu:
Untuk menemukan elemen terendah dari array berukuran NN elemen, pembanding N−1N−1diperlukan. Setelah menempatkan elemen terendah di posisi semestinya, ukuran array acak berkurang ke N−1N−1 lalu pembanding N−2N−2 diperlukan untuk menemukan nilai terendah di array acak.
Maka dari itu

(N−1)(N−1) + (N−2)(N−2) + …….……. + 11 = (N⋅(N−1))/2(N⋅(N−1))/2 pembanding dan NN bertukar hasil di kompleksitas keseluruhan O(N2)O(N2).

 

2. Insertion Sort

Konsep insertion sort berdasarkan pada gagasan bahwa satu-persatu elemen dari elemen input hanya akan digunakan sekali pada setiap iterasi untuk menemukan posisi yang semestinya. 

Teknik ini melakukan iterasi pada elemen input dan menjadikan array yang disortir lebih besar pada tiap iterasi. Insertion sort membandingkan suatu elemen dengan elemen yang memiliki nilai tertinggi dalam array yang disortir.

 

Jika elemen pembanding bernilai lebih besar, maka elemen tersebut akan menggantikan tempat elemen yang lebih kecil dan elemen yang lebih kecil akan menjadi elemen pembanding sampai posisi yang tepat ditemukan. Cara ini dilakukan dengan memindahkan semua elemen yang lebih besar terhadap elemen sebanyak satu posisi. 

 

implementasinya

Karena 7 adalah elemen pertama dan tidak ada elemen lain sebagai pembanding, 7 tetap berada di posisinya. Sekarang saat beralih ke 4, 7 merupakan elemen tertinggi di daftar tersortir dan bilangan tersebut lebih besar dibandingkan 4. Jadi, 4 ditempatkan ke posisi yang tepat yaitu sebelum 7. Sama halnya dengan 5, karena 7 (elemen terbesar di daftar tersortir) lebih besar dibandingkan 5, kita akan menempatkan 5 ke posisi semestinya. Terakhir, untuk 2, semua elemen ada di sisi kiri dari 2 (daftar tersortir) berpindah satu posisi karena semua bilangan lebih besar daripada 2, lalu 2 ditempatkan di posisi pertama. Array tersebut akan menjadi array tersortir.

Komplesitas Waktu:
Pada skenario terburuk, semua elemen dibandingkan dengan semua elemen lain pada array tersortir. Untuk elemen NN akan ada N2N2 pembanding. Oleh karena itu, kompleksitas waktu adalah O(N2)

=====

disalin dari slide materi kuliah SOD bu Habibah Nurfauziah, S.Kom, M.Si