Sorting

 

Sorting

 

 

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.

1. 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

2. Pengurutan eksternal (external sort), yaitu pengurutan datayang disimpan dalam memori sekunder, biasanya databervolume besar sehingga tidak mampu untuk dimuat semuanya dalam memori.

2 Metode sorting diantaranya adalah :
1. Selection Sort
2. 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. 

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.

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)