SORTING

SORTING

Dalam sebuah data, terkadang data tersebut berada dalam bentuk yang tidak terpola atau dengan pola tertentu yang tidak kita inginkan. Dengan sorting kita dapat menyusun kembali data yang sebelumnya tidak terpola atau dengan pola tertentu yang tidak kita inginkan, menjadi tersususn secara teratur sesuai dengan yang kita inginkan.

Sorting adalah proses pengurutan data yang sebelumnya tidak terpola atau dengan pola tertentu, sehingga menjadi tersusun teratur menurut aturan tertentu

Macam – macam sorting

- Bubble sort

- Exchange sort

- Selection sort

- Insertion sort

- Quick sort

BUBBLE SORT

Proses membandingkan elemen yang sekarang dengan elemen yang berikutnya.Jika elemen sekarang lebih besar dari elemen berikutnya maka posisinya ditukar ini disebut pengurutan dengan cara Descending, sedangkan jika data sekarang lebih kecil dari elemen berikutnya maka posisinya ditukar ini disebut pengurutan dengan cara Ascending

Procedure ascending_bubble (var data : array; jmldata:integer);

Var i,j : integer;

Begin

for i : = 2 to jmldata do

for j : = jmldata downto i do

if data [j] <>

tukardata (data[j] ,data[j-1])

End;

Ilustrasi

Misalkan kita mempunyai data sebagai berikut :

9 27 11 3 18 5 .Kita ingin mengurut data menggunakan bubble sort secara ascending (urutan dari kecil ke besar)

Langkah 1

Kita akan bandingkan data yang berada di sebelah kanan dengan data sebelumnya, begitu seterusnya sampai data terakhir

9 27 11 3 18 > 5 → tukar posisi karena data sekarang lebih kecil

9 27 11 3 < 5 18 → tidak ada pertukaran karena data sekarang lebih besar

9 27 11 > 3 5 18 → tukar posisi karena data sekarang lebih kecil

9 27 > 3 11 5 18 → tukar posisi karena data sekarang lebih kecil

9 > 3 27 11 5 18 → tukar posisi karena data sekarang lebih kecil

3 9 27 11 5 18

Langkah 2

3 9 27 11 5 < 18 → tidak ada pertukaran karena data sekarang lebih besar

3 9 27 11 > 5 18 → tukar posisi karena data sekarang lebih kecil

3 9 27 > 5 11 18 → tukar posisi karena data sekarang lebih kecil

3 9 > 5 27 11 18 → tukar posisi karena data sekarang lebih kecil

3 < 5 9 27 11 18 → tidak ada pertukaran karena data sekarang lebih besar

3 5 9 27 11 18

Langkah 3

3 5 9 27 11 < 18 → tidak ada pertukaran karena data sekarang lebih besar

3 5 9 27 > 11 18 → tukar posisi karena data sekarang lebih kecil

3 5 9 < 11 27 18 → tidak ada pertukaran karena data sekarang lebih besar

3 5 < 9 11 27 18 → tidak ada pertukaran karena data sekarang lebih besar

3 < 5 9 11 27 18 → tidak ada pertukaran karena data sekarang lebih besar

3 5 9 11 27 18

Langkah 4

3 5 9 11 27 > 18 → tukar posisi karena data sekarang lebih kecil

3 5 9 11 < 18 27 → tidak ada pertukaran karena data sekarang lebih besar

3 5 9 < 11 18 27 → tidak ada pertukaran karena data sekarang lebih besar

3 5 < 9 11 18 27 → tidak ada pertukaran karena data sekarang lebih besar

3 < 5 9 11 18 27 → tidak ada pertukaran karena data sekarang lebih besar

3 5 9 11 18 27

Data sudah terurut secara Ascending

3 5 9 11 18 27

Tadi kita sudah mengurut data menggunakan bubble sort secara Ascending. Sekarang kita akan mengurut data menggunakan bubble sort secara Descending (urutan dari besar ce kecil)

.Kita ambil data yang sama seperti diatas

Procedure descending_bubble (var data : array; jmldata:integer);

Var i,j : integer;

Begin

for i : = 2 to jmldata do

for j : = jmldata downto i do

if data [j] > data [j-1] then

tukardata (data[j] ,data[j-1])

End;

Langkah 1

9 27 11 3 18 > 5 → tidak ada pertukaran karena data sekarang lebih kecil

9 27 11 3 < 18 5 → tukar posisi karena data sekarang lebih besar

9 27 11 < 18 3 5 → tukar posisi karena data sekarang lebih besar

9 27 > 18 11 3 5 → tidak ada pertukaran karena data sekarang lebih kecil

9 < 27 18 11 3 5 → tukar posisi karena data sekarang lebih besar

27 9 18 11 3 5

Langkah 2

27 9 18 11 3 < 5 → tukar posisi karena data sekarang lebih besar

27 9 18 11 > 5 3 → tidak ada pertukaran karena data sekarang lebih kecil

27 9 18 > 11 5 3 → tidak ada pertukaran karena data sekarang lebih kecil

27 9 < 18 11 5 3 → tukar posisi karena data sekarang lebih besar

27 > 18 9 11 5 3 → tidak ada pertukaran karena data sekarang lebih kecil

27 18 9 11 5 3

Langkah 3

27 18 9 11 5 > 3 → tidak ada pertukaran karena data sekarang lebih kecil

27 18 9 11 > 5 3 → tidak ada pertukaran karena data sekarang lebih kecil

27 18 9 < 11 5 3 → tukar posisi karena data sekarang lebih besar

27 18 > 11 9 5 3 → tidak ada pertukaran karena data sekarang lebih kecil

27 > 18 11 9 5 3 → tidak ada pertukaran karena data sekarang lebih kecil

27 18 11 9 5 3

Data sudah terurut secara Descending

27 18 11 9 5 3

EXCHANGE SORT

Proses membandingkan suatu elemen dengan elemen – elemen yang lainnya dalam sebuah array dan melakukan pertukaran elemen jika perlu, jadi ada elemen yang selalu mejadi pusat (pivot)

Procedure descending_exchange ;

void exchange _sort (int data [ ] )

{

for (int i = 0; i <>

{

for (int j = i+1; j <>

{

if (data [i] > data [j])

tukar (&data [i], &data[j]);

}

}

}

Ilistrasi

Misalkan kita mempunyai data sebagai berikut :

74

59

66

76

84

81

Kita ingin mengurut data menggunakan Exchange sort secara Descending (urutan dari besar ke kecil)

Langkah 1

74	59	66	76	84	81
74	59	66	76	84	81
74	59	66	76	84	81
76	59	66	74	84	81
84	59	66	74	76	81
84	59	66	74	76	81

Penjelasan

Dalam Exchange sort pivot (pusat) data kita bandingkan dengan data yang berada di kanan pivot sampai data terakhir. Jika pivot lebih kecil dengan data yang kita bandingkan maka posisinya ditukar dan jika pivot lebih besar dengan data yang kita bandingkan maka posisi pivot tetap

Pada tabel diatas, angka yang berwarna biru adalah pivot. Kita akan bandingkan pivot dengan data yang berada disebelah kanan sampai data terakhir.Jika pivot lebih besar dari data yang kita bandingkan maka posisi pivot dengan data yang kita bandingkan tetap,Jika pivot lebih kecil dari data yang kita bandingkan maka maka posisis pivot ditukar dengan posisi data yang lebih besar

Pada tabel diatas angka yang berwarna merah menunjukkan nilai pivot yang lebih kecil dari data yang dibandingkan,maka posisinya ditukar

Langkah 2

84	59	66	74	76	81
84	66	59	74	76	81
84	74	59	66	76	81
84	76	59	66	74	81
84	81	59	66	74	76

Penjelasan

Pada langkah ke 2 pivot berada pada kolom ke 2 yang angkanya berwarna biru.Sama seperti tadi kita bandingkan pivot dengan data yang berada di sebelah kanannya sampai data terakhir. Jika pivot lebih besar dari data yang kita bandingkan maka posisi pivot dengan data yang kita bandingkan tetap,Jika pivot lebih kecil dari data yang kita bandingkan maka maka posisis pivot ditukar dengan posisi data yang lebih besar

Pada tabel diatas angka yang berwarna merah menunjukkan nilai pivot yang lebih kecil dari data yang dibandingkan,maka posisinya ditukar

Langkah 3

84	81	59	66	74	76
84	81	66	59	74	76
84	81	74	59	66	76
84	81	76	59	66	74

Penjelasan

Pada langkah ke 3 pivot berada pada kolom ke 3 yang angkanya berwarna biru.Sama seperti tadi kita bandingkan pivot dengan data yang berada di sebelah kanannya sampai data terakhir. Jika pivot lebih besar dari data yang kita bandingkan maka posisi pivot dengan data yang kita bandingkan tetap,Jika pivot lebih kecil dari data yang kita bandingkan maka maka posisis pivot ditukar dengan posisi data yang lebih besar

Pada tabel diatas angka yang berwarna merah menunjukkan nilai pivot yang lebih kecil dari data yang dibandingkan,maka posisinya ditukar

Langkah 4

84	81	76	59	66	74
84	81	76	66	59	74
84	81	76	74	59	66

Penjelasan

Pada langkah ke 4 pivot berada pada kolom ke 4 yang angkanya berwarna biru.Sama seperti tadi kita bandingkan pivot dengan data yang berada di sebelah kanannya sampai data terakhir. Jika pivot lebih besar dari data yang kita bandingkan maka posisi pivot dengan data yang kita bandingkan tetap,Jika pivot lebih kecil dari data yang kita bandingkan maka maka posisis pivot ditukar dengan posisi data yang lebih besar

Pada tabel diatas angka yang berwarna merah menunjukkan nilai pivot yang lebih kecil dari data yang dibandingkan,maka posisinya ditukar

Langkah 5

84	81	76	74	59	66
84	81	76	74	66	59

Penjelasan

Pada langkah ke 5 pivot berada pada kolom ke 5 yang angkanya berwarna biru.Sama seperti tadi kita bandingkan pivot dengan data yang berada di sebelah kanannya sampai data terakhir. Jika pivot lebih besar dari data yang kita bandingkan maka posisi pivot dengan data yang kita bandingkan tetap,Jika pivot lebih kecil dari data yang kita bandingkan maka maka posisis pivot ditukar dengan posisi data yang lebih besar

Pada tabel diatas angka yang berwarna merah menunjukkan nilai pivot yang lebih kecil dari data yang dibandingkan,maka posisinya ditukar

Data sudah terurut secara Descending 84 81 76 74 66 59

Tadi kita sudah mengurutkan data menggunakan exchange sort secara Descending. Sekarang kita akan mengurut data secara Ascending. Kita ambil data yang sama seperti diatas

Procedure ascending_exchange ;

void exchange _sort (int data [ ] )

{

for (int i = 0; i <>

{

for (int j = i+1; j <>

{

if (data [i] <>

tukar (&data [i], &data[j]);

}

}

}

Langkah 1

74	59	66	76	84	81
59	74	66	76	84	81
59	74	66	76	84	81
59	74	66	76	84	81
59	74	66	76	84	81
59	74	66	76	84	81

Penjelasan

Dalam Exchange sort pivot (pusat) data kita bandingkan dengan data yang berada di kanan pivot sampai data terakhir. Jika pivot lebih besar dengan data yang kita bandingkan maka posisinya ditukar dan jika pivot lebih kecil dengan data yang kita bandingkan maka posisi pivot tetap

Pada tabel diatas, angka yang berwarna biru adalah pivot. Kita akan bandingkan pivot dengan data yang berada disebelah kanan sampai data terakhir.Jika pivot lebih besar dari data yang kita bandingkan maka posisi pivot ditukar dengan data yang kita bandingkan,Jika pivot lebih kecil dari data yang kita bandingkan maka posisi pivot tetap

Pada tabel diatas angka yang berwarna merah menunjukkan nilai pivot yang lebih besar dari data yang kita bandingkan, maka posisinya ditukar

Langkah 2

59	74	66	76	84	81
59	66	74	76	84	81
59	66	74	76	84	81
59	66	74	76	84	81
59	66	74	76	84	81

Penjelasan

Pada langkah ke 2 pivot berada pada kolom ke 2 yang angkanya berwarna biru Sama seperti tadi kita akan bandingkan pivot dengan data yang berada disebelah kanan sampai data terakhir.Jika pivot lebih besar dari data yang kita bandingkan maka posisi pivot ditukar dengan data yang kita bandingkan,Jika pivot lebih kecil dari data yang kita bandingkan maka posisi pivot tetap

Pada tabel diatas angka yang berwarna merah menunjukkan nilai pivot yang lebih besar dari data yang kita bandingkan, maka posisinya ditukar

Langkah 3

59	66	74	76	84	81
59	66	74	76	84	81
59	66	74	76	84	81
59	66	74	76	84	81

Penjelasan

Pada langkah ke 3 pivot berada pada kolom ke 3 yang angkanya berwarna biru Sama seperti tadi kita akan bandingkan pivot dengan data yang berada disebelah kanan sampai data terakhir.Jika pivot lebih besar dari data yang kita bandingkan maka posisi pivot ditukar dengan data yang kita bandingkan,Jika pivot lebih kecil dari data yang kita bandingkan maka posisi pivot tetap

Pada langkah 3 tidak terjadi pertukaran posisi, karena nilai pivot lebih kecil dari data yang kita bandingkan

Langkah 4

59	66	74	76	84	81
59	66	74	76	84	81
59	66	74	76	84	81

Penjelasan

Pada langkah ke 4 pivot berada pada kolom ke 4 yang angkanya berwarna biru Sama seperti tadi kita akan bandingkan pivot dengan data yang berada disebelah kanan sampai data terakhir.Jika pivot lebih besar dari data yang kita bandingkan maka posisi pivot ditukar dengan data yang kita bandingkan,Jika pivot lebih kecil dari data yang kita bandingkan maka posisi pivot tetap

Pada langkah 4 tidak terjadi pertukaran posisi, karena nilai pivot lebih kecil dari data yang kita bandingkan

Langkah 5

59	66	74	76	84	81
59	66	74	76	81	84

Penjelasan

Pada langkah ke 5 pivot berada pada kolom ke 5 yang angkanya berwarna biru Sama seperti tadi kita akan bandingkan pivot dengan data yang berada disebelah kanan sampai data terakhir.Jika pivot lebih besar dari data yang kita bandingkan maka posisi pivot ditukar dengan data yang kita bandingkan,Jika pivot lebih kecil dari data yang kita bandingkan maka posisi pivot tetap

Pada tabel diatas angka yang berwarna merah menunjukkan nilai pivot yang lebih besar dari data yang kita bandingkan, maka posisinya ditukar

SELECTION SORT

Proses membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain lebih kecil dari elemen sekarang maka dicatat posisinya dan kemudikan ditukar dan begitu seterusnya.

Ilustrasi

Procedur ascending_selection;

var i, j, pos : byte;

Begin

for i ; = 1 to max – 1 do

begin

pos : = i;

for j : = i + 1 to max do

if data [j] < data [pos] then pos : = j ;

if i <> pos then

tukar data (data [i] , data [pos])

end;

End;

Misalkan kita mempunyai data sebagai berikut

3 6 5 4 2 7

Kita ingin mengurut data menggunakan selection sort secara Ascending

Langkah 1

0 1 2 3 4 5 → index

3 6 5 4 2 7 → value

Pembanding Posisi

3 < 6 0

3 < 5 0

3 < 4 0

3 > 2 (tukar) 4

2 < 7 4

Tukar data ke – 0 (3) dengan data ke – 4 (2)

0 1 2 3 4 5 → index

2 6 5 4 3 7 → value

Penjelasan

Data pada index ke – 0 kita membandingkan dengan data yang berada disebelah kanan sampai data terakhir.Jika data pada index ke – 0 lebih kecil dari data yang berada disebelah kanannya maka data pada index ke -0 posisinya tetap,sedangkan jika data pada index ke – 0 lebih besar dari data yang berada disebelah kanannya, maka data pada index ke – 0 posisinya ditukar

Langkah 2

0 1 2 3 4 5 → index

2 6 5 4 3 7 → value

Pembanding Posisi

6 > 5 (tukar) 2

5 > 4 (tukar) 3

4 > 3 (tukar) 4

3 > 7 4

Tukar data ke – 1 (6) dengan data ke – 4 (3)

0 1 2 3 4 5 → index

2 3 5 4 6 7 → value

Penjelasan

Data pada index ke – 1 kita membandingkan dengan data yang berada disebelah kanan sampai data terakhir.Jika data pada index ke – 1 lebih kecil dari data yang berada disebelah kanannya maka data pada index ke -1 posisinya tetap,sedangkan jika data pada index ke – 1 lebih besar dari data yang berada disebelah kanannya, maka data pada index ke – 1 posisinya ditukar

Langkah 3

0 1 2 3 4 5 → index

2 3 5 4 6 7 → value

Pembanding Posisi

5 > 4 (tukar) 3

4 < 6 3

4 < 7 3

Tukar data ke – 2 (5) dengan data ke – 3 (4)

0 1 2 3 4 5 → index

2 3 4 5 6 7 → value

Penjelasan

Data pada index ke – 2 kita membandingkan dengan data yang berada disebelah kanan sampai data terakhir.Jika data pada index ke – 2 lebih kecil dari data yang berada disebelah kanannya maka data pada index ke -2 posisinya tetap,sedangkan jika data pada index ke – 2 lebih besar dari data yang berada disebelah kanannya, maka data pada index ke – 2 posisinya ditukar

Data sudah terurut secara Ascending

2 3 4 5 6 7

Tadi kita sudah mengurutkan data menggunakan selection sort secara Ascending. Sekarang kita akan mengurut data secara Descending.Kita ambil data yang sama.

Procedur descending_selection;

var i, j, pos : byte;

Begin

for i ; = 1 to max – 1 do

begin

pos : = i;

for j : = i + 1 to max do

if data [j] > data [pos] then pos : = j ;

if i <> pos then

tukar data (data [i] , data [pos])

end;

End;

Langkah 1

0 1 2 3 4 5 → index

3 6 5 4 2 7 → value

Pembanding Posisi

3 < 6 (tukar) 1

6 > 5 1

6 > 4 1

6 > 2 1

6 < 7(tukar) 5

Tukar data ke – 0 (3) dengan data ke – 5 (7)

0 1 2 3 4 5 → index

7 6 5 4 2 3 → value

Penjelasan

Data pada index ke – 0 kita membandingkan dengan data yang berada disebelah kanan sampai data terakhir.Jika data pada index ke – 0 lebih kecil dari data yang berada disebelah kanannya maka data pada index ke -0 posisinya ditukar ,sedangkan jika data pada index ke – 0 lebih besar dari data yang berada disebelah kanannya, maka data pada index ke – 0 posisinya tetap

Langkah 2

0 1 2 3 4 5 → index

7 6 5 4 2 3 → value

Pembanding Posisi

6 > 5 1

6 > 4 1

6 > 3 1

6 > 2 1

Tidak ada pertukaran

0 1 2 3 4 5 → index

7 6 5 4 2 3 → value

Penjelasan

Data pada index ke – 1 kita membandingkan dengan data yang berada disebelah kanan sampai data terakhir.Jika data pada index ke – 1 lebih kecil dari data yang berada disebelah kanannya maka data pada index ke -1 posisinya ditukar ,sedangkan jika data pada index ke – 1 lebih besar dari data yang berada disebelah kanannya, maka data pada index ke – 1 posisinya tetap

Pada langkah 2 tidak ada pertukaran, karena data pada indeks ke 1 lebih besar dari data yang berada disebelah kanannya, maka data pada indexs ke – 1 posisinya tetap

Langkah 3

0 1 2 3 4 5 → index

7 6 5 4 2 3 → value

Pembanding Posisi

5 > 4 2

5 > 2 2

5 > 3 2

Tidak ada pertukaran

0 1 2 3 4 5 → index

7 6 5 4 2 3 → value

Penjelasan

Data pada index ke – 2 kita membandingkan dengan data yang berada disebelah kanan sampai data terakhir.Jika data pada index ke – 2 lebih kecil dari data yang berada disebelah kanannya maka data pada index ke -2 posisinya ditukar ,sedangkan jika data pada index ke – 2 lebih besar dari data yang berada disebelah kanannya, maka data pada index ke – 2 posisinya tetap

Pada langkah 3 tidak ada pertukaran, karena data pada index ke 2 lebih besar dari data yang berada disebelah kanannya, maka data pada index ke – 2 posisinya tetap

Langkah 4

0 1 2 3 4 5 → index

7 6 5 4 2 3 → value

Pembanding Posisi

4 > 2 3

4 > 3 3

Tidak ada pertukaran

0 1 2 3 4 5 → index

7 6 5 4 2 3 → value

Penjelasan

Data pada index ke – 3 kita membandingkan dengan data yang berada disebelah kanan sampai data terakhir.Jika data pada index ke – 3 lebih kecil dari data yang berada disebelah kanannya maka data pada index ke -3 posisinya ditukar ,sedangkan jika data pada index ke – 3 lebih besar dari data yang berada disebelah kanannya, maka data pada index ke – 3 posisinya tetap

Pada langkah 4 tidak ada pertukaran, karena data pada index ke 3 lebih besar dari data yang berada disebelah kanannya, maka data pada index ke – 3 posisinya tetap

Langkah 5

0 1 2 3 4 5 → index

7 6 5 4 2 3 → value

Pembanding Posisi

2 < 3 (tukar) 5

Tukar data ke – 4 (2) dengan data ke – 5 (3)

0 1 2 3 4 5 → index

7 6 5 4 3 2 → value

Data sudah terurut secara Descending

7 6 5 4 3 2

Penjelasan

Data pada index ke – 4 kita membandingkan dengan data yang berada disebelah kanan sampai data terakhir.Jika data pada index ke – 4 lebih kecil dari data yang berada disebelah kanannya maka data pada index ke - 4 posisinya ditukar ,sedangkan jika data pada index ke – 4 lebih besar dari data yang berada disebelah kanannya, maka data pada index ke – 4 posisinya tetap

INSERTION SORT

Proses pengurutan data dengan cara membandingkan data I (dimana I dimulai dari data ke 2 sampai dengn data terakhir) dengan data berikutnya

Procedure ascending_insert ;

var i, j, temp : byte ;

Begin

for i : = 2 to max do

begin

temp : = data [i];

j : = i – 1;

while (data [j] > temp ) dan (j > 0) do

begin

data [j + 1]: = data [j]

dec (j);

end;

end;

End;

Ilustrasi

Misalkan kita mempunyai data sebagai berikut

9 7 8 3 5 1

Kita akan mengurut data menggunakan insertion sort secara Asending

Langkah 1

0 1 2 3 4 5 → index

9 7 8 3 5 1 → value

Temp	Cek	Geser
7	Temp < 9	Data ke - 0 ke posisi ke - 1

Temp menempati posisi ke – 0

0 1 2 3 4 5 → index

7 9 8 3 5 1 → value

Penjelasan

Data pada index ke – 1 kita disebut temp.Setelah kita tentukan temp,kita akan bandingkan temp tersebut dengan data yang berada di sebelah kirinya sampai data terakhir.Jika temp lebih kecil dari data yang kita bandingkan maka temp menempati posisi data tersebut. Jika temp lebih besar dari data yang kita bandingkan maka temp tetap pada posisinya

Langkah 2

0 1 2 3 4 5 → index

7 9 8 3 5 1 → value

Temp	Cek	Geser
8	Temp < 9	Data ke – 1 ke posisi ke - 2
8	Temp > 7	Tidak ada pergeseran karena temp lebih besar

Temp menempati posisi ke – 1

0 1 2 3 4 5 → index

7 8 9 3 5 1 → value

Penjelasan

Data pada index ke – 2 kita disebut temp.Setelah kita tentukan temp,kita akan bandingkan temp tersebut dengan data yang berada di sebelah kirinya sampai data terakhir.Jika temp lebih kecil dari data yang kita bandingkan maka temp menempati posisi data tersebut. Jika temp lebih besar dari data yang kita bandingkan maka temp tetap pada posisinya

Langkah 3

0 1 2 3 4 5 → index

7 8 9 3 5 1 → value

Temp	Cek	Geser
3	Temp < 9	Data ke – 2 ke posisi ke - 3
3	Temp < 8	Data ke – 1 ke posisi ke - 2
3	Temp < 7	Data ke – 0 ke posisi ke - 1

Temp menempati posisi ke – 0

0 1 2 3 4 5 → index

3 7 8 9 5 1 → value

Penjelasan

Data pada index ke – 3 kita disebut temp.Setelah kita tentukan temp,kita akan bandingkan temp tersebut dengan data yang berada di sebelah kirinya sampai data terakhir.Jika temp lebih kecil dari data yang kita bandingkan maka temp menempati posisi data tersebut. Jika temp lebih besar dari data yang kita bandingkan maka temp tetap pada posisinya

Langkah 4

0 1 2 3 4 5 → index

3 7 8 9 5 1 → value

Temp	Cek	Geser
5	Temp < 9	Data ke – 3 ke posisi ke - 4
5	Temp < 8	Data ke – 2 ke posisi ke - 3
5	Temp < 7	Data ke – 1 ke posisi ke - 2
5	Temp > 3	Tidak ada pergeseran karena temp lebih besar

Temp menempati posisi ke – 1

0 1 2 3 4 5 → index

3 5 7 8 9 1 → value

Penjelasan

Data pada index ke – 4 kita disebut temp.Setelah kita tentukan temp,kita akan bandingkan temp tersebut dengan data yang berada di sebelah kirinya sampai data terakhir.Jika temp lebih kecil dari data yang kita bandingkan maka temp menempati posisi data tersebut. Jika temp lebih besar dari data yang kita bandingkan maka temp tetap pada posisinya

Langkah 5

0 1 2 3 4 5 → index

3 5 7 8 9 1 → value

Temp	Cek	Geser
1	Temp < 9	Data ke – 4 ke posisi ke - 5
1	Temp < 8	Data ke – 3 ke posisi ke - 4
1	Temp < 7	Data ke – 2 ke posisi ke - 3
1	Temp < 5	Data ke – 1 ke posisi ke - 2
1	Temp < 3	Data ke – 0 ke posisi ke - 1

Temp menempati posisi ke – 0

0 1 2 3 4 5 → index

1 3 5 7 8 9 → value

Data sudah terurut secara Ascending

1 3 5 7 8 9

Penjelasan

Data pada index ke – 5 kita disebut temp.Setelah kita tentukan temp,kita akan bandingkan temp tersebut dengan data yang berada di sebelah kirinya sampai data terakhir.Jika temp lebih kecil dari data yang kita bandingkan maka temp menempati posisi data tersebut. Jika temp lebih besar dari data yang kita bandingkan maka temp tetap pada posisinya

Tadi kita sudah mengurutkan data menggunakan insertion sort secara Ascending. Sekarang kita akan mengurut data secara Descending.Kita ambil data yang sama.

Procedure ascending_insert ;

var i, j, temp : byte ;

Begin

for i : = 2 to max do

begin

temp : = data [i];

j : = i – 1;

while (data [j] <> 0) do

begin

data [j + 1]: = data [j]

dec (j);

end;

end;

End;

Langkah 1

0 1 2 3 4 5 → index

9 7 8 3 5 1 → value

Temp	Cek	Geser
7	Temp < 9	Tidak ada pergeseran karena temp lebih kecil

Temp tidak mengalami pergeseran

0 1 2 3 4 5 → index

9 7 8 3 5 1 → value

Penjelasan

Data pada index ke – 1 kita disebut temp.Setelah kita tentukan temp,kita akan bandingkan temp tersebut dengan data yang berada di sebelah kirinya sampai data terakhir.Jika temp lebih kecil dari data yang kita bandingkan maka temp tidak mengalami pergeseran. Jika temp lebih besar dari data yang kita bandingkan maka temp menempati posisi data tersebut

Langkah 2

0 1 2 3 4 5 → index

9 7 8 3 5 1 → value

Temp	Cek	Geser
8	Temp > 7	Data ke 1 ke posisi ke - 2
8	Temp < 9	Tidak ada pergeseran karena temp lebih kecil

Temp menempati posisi ke – 1

0 1 2 3 4 5 → index

9 8 7 3 5 1 → value

Penjelasan

Data pada index ke – 2 kita disebut temp.Setelah kita tentukan temp,kita akan bandingkan temp tersebut dengan data yang berada di sebelah kirinya sampai data terakhir.Jika temp lebih kecil dari data yang kita bandingkan maka temp tidak mengalami pergeseran. Jika temp lebih besar dari data yang kita bandingkan maka temp menempati posisi data tersebut

Langkah 3

0 1 2 3 4 5 → index

9 8 7 3 5 1 → value

Temp	Cek	Geser
3	Temp < 7	Tidak ada pergeseran karena temp lebih kecil

3

Temp < 8

Tidak ada pergeseran karena temp lebih kecil

3

Temp < 9

Tidak ada pergeseran karena temp lebih kecil

Temp tidak mengalami pergeseran

0 1 2 3 4 5 → index

9 8 7 3 5 1 → value

Penjelasan

Data pada index ke – 3 kita disebut temp.Setelah kita tentukan temp,kita akan bandingkan temp tersebut dengan data yang berada di sebelah kirinya sampai data terakhir.Jika temp lebih kecil dari data yang kita bandingkan maka temp tidak mengalami pergeseran. Jika temp lebih besar dari data yang kita bandingkan maka temp menempati posisi data tersebut

Langkah 4

0 1 2 3 4 5 → index

9 8 7 3 5 1 → value

Temp	Cek	Geser
5	Temp > 3	Data ke – 3 ke posisi ke - 4
5	Temp < 7	Tidak ada pergeseran karena temp lebih kecil
5	Temp < 8	Tidak ada pergeseran karena temp lebih kecil
5	Temp < 9	Tidak ada pergeseran karena temp lebih kecil

Temp menempati posisi ke – 3

0 1 2 3 4 5 → index

9 8 7 5 3 1 → value

Data sudah terurut secara Descending

9 8 7 5 3 1

Penjelasan

Data pada indeks ke – 4 kita disebut temp.Setelah kita tentukan temp,kita akan bandingkan temp tersebut dengan data yang berada di sebelah kirinya sampai data terakhir.Jika temp lebih kecil dari data yang kita bandingkan maka temp tidak mengalami pergeseran. Jika temp lebih besar dari data yang kita bandingkan maka temp menempati posisi data tersebut

QUICK SORT

Quick sort adalah proses membandingkan suatu elemen (disebut pivot) dengan elemen – elemen yang lain dan menyusun sedemikian rupa sehingga elemen – elemen tersebut tersusun menurut pola tertentu.

Ilustrasi

Misalkan kita mempunyai data sebagai berikut

2 3 7 5 9 18 11

Kita ingin mengurut data menggunakan quick sort secara Ascending

Langkah 1

Kita cari pivot.Pivot adalah data yang terletak ditengah

Kita kerjakan dulu data yang terletak disebelah kiri pivot

2 3 7 5 9 18 11

Angka yang berwarna merah adalah pivot. Sekarang kita bandingkan pivot dengan data yang terletak disebelah kiri pivot. Jika data lebih besar dari pivot maka data tersebut dipindahkan ke sebelah kanan pivot..Sehingga sekarang data menjadi

2 3 5

Langkah 2

Kita cari pivot.Pivot adalah data yang terletak ditengah dari data diatas

2 3 5

Angka yang berwarna merah adalah pivot. Sekarang kita bandingkan pivot dengan data yang terletak disebelah kiri pivot. Jika data lebih besar dari pivot maka data tersebut dipindahkan ke sebelah kanan pivot. Pada langkah ke 2 posisi data tetap karena data disebelah pivot lebih kecil

Langkah 3

Sekarang kita bandingkan data yang terletak disebalah kanan pivot

9 18 11

Kemudian kita cari pivot dari data diatas

Angka yang berwarna merah adalah pivot. Sekarang kita bandingkan pivot dengan data yang terletak disebelah kiri pivot. Jika data lebih besar dari pivot maka data tersebut dipindahkan ke sebelah kanan pivot. Pada langkah ke 3 posisi data tetap karena data disebelah pivot lebih kecil

Langkah 4

Sekarang kita bandingkan data yang terletak disebalah kanan pivot

Angka yang berwarna merah adalah pivot. Sekarang kita bandingkan pivot dengan data yang terletak disebelah kanan pivot. Jika data lebih kecil dari pivot maka data tersebut dipindahkan ke sebelah kiri pivot.

Data sudah terurut

2 3 5 7 9 18 11