2.2. Selection SortSelection Sort adalah sort yang melakukan beberapa kali pass untuk melakukan penyeleksian elemen struktur data. Untuk sorting ascending (menaik), elemen yang paling kecil di antara elemen-elemen yang belum urut, disimpan indeksnya, kemudian dilakukan pertukaran nilai elemen dengan indeks yang disimpan tersebut dengan elemen yang paling depan yang belum urut. Sebaliknya, untuk sorting descending (menurun), elemen yang paling besar yang disimpan indeksnya kemudian ditukar.

Algoritma selection sort dapat dirangkum sebagai berikut:1.Temukan nilai yang paling minimum (atau sesuai keinginan) di dalam struktur data. Jika ascending, maka yang harus ditemukan adalah nilai yang paling minimum. Jika descending, maka temukan nilai yang paling maksimum.2.Tukar nilai tersebut dengan nilai pada posisipertama di bagian struktur data yang belum diurutkan.3.Ulangi langkah di atas untuk bagian struktur datayang tersisa.

PseudocodedariselectionSortadalahsebagaiberikut; For I = 0 to N-1 do: Smallsub = I For J = I + 1 to N-1 do: If A(J) < A(Smallsub) Smallsub = J End-If End-For Temp = A(I) A(I) = A(Smallsub) A(Smallsub) = Temp End-For

2.3. Insertion SortMetodepengurutanpadainsertionsortadalahmetodedengancaramenyisipkanelemenlarikpada posisiyangtepat.Cara kerja insertion sort, Pertama-tama, dilakukan iterasi, dimana di setiap iterasi insertion sort memindahkan nilai elemen,kemudian menyisipkannya berulang-ulang sampai ketempat yang tepat. Begitu seterusnya dilakukan. Dari proses iterasi, seperti biasa, terbentuklah bagian yang telah di-sorting dan bagian yang belum di-sorting.

Algoritma Insertion Sort dapat dirangkum sebagai berikut:1.Simpan nilai Ti kedalam variabel sementara, dengan i = 1.2.Bandingkan nilainya dengan elemen sebelumnya.3.Jika elemen sebelumnya (Ti-1) lebih besar nilainya daripada Ti, maka tindih nilai Ti dengan nilai Ti-1 tersebut. Decrement i (kurangi nilainya dengan 1).4.Lakukan terus poin ke-tiga, sampai Ti-1 Ti.5.Jika Ti-1 Ti terpenuhi, tindih nilai di Ti dengan variabel sementara yang disimpan sebelumnya.6.Ulangi langkah dari poin 1 di atas dengan i di-increment (ditambah satu).PseudocodedariInsertionSortadalahsebagaiberikut;procedureinsertion;vari,j,v:integer;beginfori:=2toNdobeginv:=a[i];j:=1;whilea[j1]>vdobegina[j]:=a[j1];j:=j1end;a[j]:=v;endend;

2.4. Merge SortAlgoritmaMerge Sortditemukan oleh John vonNeumann di tahun 1945. Merge Sort termasuk paradigma algoritma divide and conquer (kurang lebih berarti: bagi dan atasi). Hal ini dikarenakan algoritma ini melakukan pembagian struktur data sebelum kemudian dioperasi satu per satu. Intinya, algoritma ini menggunakan dua ide utama sebagai berikut,1.Sebuah list yang kecil membutuhkan langkah yang lebih sedikit untuk pengurutan daripada sebuah list yang besar.2.Untuk membentuk sebuah list terurut dari duabuah list terurut membutuhkan langkah yangl ebih sedikit daripada membentuk sebuah list terurut dari dua buah list tak terurut. Contoh:hanya diperlukan satu kali traversal untuk masing-masing list jika keduanya sudahterurut.Algoritma Merge Sort sederhananya, dapat ditulis berikut:1.Bagi list yang tak terurut menjadi dua sama panjang atau salah satunya lebih panjang satu elemen.2.Bagi masing-masing dari 2 sub-list secara rekursif sampai didapatkan list dengan ukuran 1.3.Gabung 2 sublist kembali menjadi satu list terurut.Berikut iniadalahtigaprosesdidalammenggunakanalgoritmaMergeSort:Divide : BagiarrayA[l..r]denganjumlahelemennmenjadiduasubarray denganjumlahelemen masingmasingsubarraysebanyakn/2.Conqueror: Urutkanmasing-masing subarray secara rekursif menggunakan prosedur merge sortCombine : SatukansubarrayuntukmenghasilkanelemenarrayA[l..r]yang terurut.BerikutiniadalahalgoritmauntukMergeSortarrayA[l..r]:Merge-Sort (A,l,r)1. ifl < r2. then q := [(l+r) /2]3. Merge-Sort(A,l,q)4. Merge-Sort(A,q+1,r)5. Merge(A,p,q,r)

SedangkanalgoritmauntukprosedureMergeadalahsebagaiberikut:MERGE ( A, l, q, r)1. n1 q l + 12. n2 r q3. create arrays L[1. . n 1+ 1] and R[1. . n 2+ 1]4. fori 1to n 15. doL[i] A[ l + i 1]6. forj 1to n 27. doR[ j ] A[q + j ]8. L[n 1+ 1] 9. R[n 2+ 1] 10. i 111. j 112. fork l to r13. doifL[i] R[ j ]14. then A[k] L[i]15. i i +116. elseA[k] R[ j ]17. j j +1

2.5. Quick SortQuick Sortadalah algoritma sorting yang terkenal yang dirancang oleh C.A.R. Hoare pada tahun 1960 ketika bekerja untuk perusahaan manufaktur komputer saintifik kecil, Elliott Brothers. Algoritma ini rekursif, dan termasuk paradigma algoritmadivide and conquer.Algoritma ini terdiri dari 4 langkah utama:1.Jika struktur data terdiri dari 1 atau 0 elemen yang harus diurutkan, kembalikan struktur data itu apa adanya.2.Ambil sebuah elemen yang akan digunakan sebagai pivot point (poin poros). (Biasanya elemen yang paling kiri.)3.Bagi struktur data menjadi dua bagian satu dengan elemen-elemen yang lebih besar daripada pivot point, dan yang lainnya dengan elemen-elemen yang lebih kecil dari pada pivot point.4.Ulangi algoritma secara rekursif terhadap kedua paruh struktur data.Berikutadalahtigaprosesdidalammetodedividedanconqueror untuk algoritmaQuickSort:Divide : Bagi arrayA[l..r] menjadi dua subarrayA[l..pivot-1] dan A[pivot+1..r] sehinggasetiapelemen di dalam sub array A[l..pivot1] bernilai lebih kecil atau samadenganA[pivot]. Untuk menghitung nilaipivot merupakan bagiandari prosedurpartition.Conqueror:UrutkansubarrayA[l..pivot1]dan A[pivot+1..r] secara rekursif ke prosedur quicksortCombine:Karenasubarraysudahterurut,makaarrayA[l..r]sudahterurut.Pseudocodedarialgoritmaquicksortadalahsebagaiberikut:procedurequicksort(l,r:integer);varpivot:integer;beginforr>lthenbeginpivot:=partition(l,r);quicksort(l,pivot1);quicksort(pivot+1,r);endend;AlgoritmadaripartisiarrayA[l..r]adalah:

x := A[r]i := l-1forj := l to r-1doifA[j]