presentasi kelompok 3

SORTING DATAKELOMPOK 3

KELOMPOK 3• MIRANTI DWI HENDRIYAH (39025)

• HERMAWAN RAHMAT HIDAYAT (39033)

• RICKY JULIANJATSONO (39036)

• ATHYA RAMADHANI (39044)

• M. HARITS FAISHAL ( :3 )

• DIAN ARYANTI HAPSARI (39074)

Sorting (Pengurutan)

Sorting adalah proses mengatur sekumpulan objek menurut aturan atau susunan tertentu. Urutan objek tersebut dapat menaik (ascending = dari data kecil ke data lebih besar) atau menurun (descending = dari data besar ke data lebih kecil).

OUTLINE SORTING

Bubble Sort(Metode Gelembung)

Metode pengurutan gelembung (bubble sort) diinspirasi oleh gelembung sabun yang ada di permukaan air. Prinsip pengapungan ini juga dipakai pada pengurutan gelembung.

Cara ini adalah pengurutan elemen yang paling sederhana. Inti dari metode ini menggunakan perbandingan dan pertukaran.

Bubble Sort: PseudocodeBUBBLESORT(A)

1for i←1 to length[A]

2 for j←length[A] downto i+1

3 if A[j] < A[j-1]

4 then exchange A[j] ↔ A[j-1]

Bubble Sort : Algoritma(Descending)banyaknya data: n

Contoh: Data diurutkan/disorting dari yang bernilai besar ke kecil

Proses

step 1 : Periksalah nilai dua elemen mulai dari urutan ke-n sampai urutan ke-1. Jika nilai kiri<kanan, tukarkan kedua data itu.

step 2 : Periksalah nilai dua elemen mulai dari urutan ke-n sampai urutan ke-2. Jika nilai kiri<kanan, tukarkan kedua data itu.

step n-1 : Periksalah nilai dua elemen mulai dari urutan ke-n sampai urutan ke-n-1. Jika nilai kiri<kanan, tukarkan kedua data itu.

Bubble Sort : Algoritma(Ascending)banyaknya data: n

Contoh: Data diurutkan/disorting dari yang bernilai kecil ke besar

Proses

step 1 : Periksalah nilai dua elemen mulai dari urutan ke-n sampai urutan ke-1. Jika nilai kiri>kanan, tukarkan kedua data itu.

step 2 : Periksalah nilai dua elemen mulai dari urutan ke-n sampai urutan ke-2. Jika nilai kiri>kanan, tukarkan kedua data itu.

step n-1 : Periksalah nilai dua elemen mulai dari urutan ke-n sampai urutan ke-n-1. Jika nilai kiri>kanan, tukarkan kedua data itu.

Bubble Sort AscendingAwal : 5 4 3 2 1

Step 1 : 5 4 3 2 1


Step 1 : 5 4 3 1 2


Step 1 : 5 4 1 3 2


Step 1 : 5 1 4 3 2


Step 1 : 1 5 4 3 2


Step 1 : 1 5 4 3 2

Step 2 : 1 5 4 3 2


Step 1 : 1 5 4 3 2

Step 2 : 1 5 4 2 3


Step 1 : 1 5 4 3 2

Step 2 : 1 5 2 4 3


Step 1 : 1 5 4 3 2

Step 2 : 1 2 5 4 3


Step 1 : 1 5 4 3 2

Step 2 : 1 2 5 4 3

Step 3 : 1 2 5 4 3


Step 1 : 1 5 4 3 2

Step 2 : 1 2 5 4 3

Step 3 : 1 2 5 3 4


Step 1 : 1 5 4 3 2

Step 2 : 1 2 5 4 3

Step 3 : 1 2 3 5 4

Bubble Sort AscendingStep 1 : 1 5 4 3 2

Step 2 : 1 2 5 4 3

Step 3 : 1 2 3 5 4

Step 4 : 1 2 3 5 4

Bubble Sort AscendingStep 1 : 1 5 4 3 2

Step 2 : 1 2 5 4 3

Step 3 : 1 2 3 5 4

Step 4 : 1 2 3 4 5 (Selesai)

Bubble Sort

Jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan

Selection SortMetode pengurutan ini disebut pengurutan

maksimum / minimum karena didasarkan pada pemilihan elemen maksimum atau minimum kemudian mempertukarkan elemen maksimum/minimum tersebut dengan elemen terujung larik (elemen ujung kiri atau elemen ujung kanan).

Selanjutnya elemen terujung itu kita “isolasi” dan tidak diikut sertakan pada proses selanjutnya. Karena proses utama dalam pengurutan adalah pemilihan elemen maksimum / minimum, maka metode ini disebut metode seleksi (selection sort).

Selection Sort : Algorthm• Langkah 1: Tentukan Harga Maksimum didalam L1[1..N]

Pertukarkan harga maksimum dng L[N]

• Langkah 2: Tentukan Harga Maksimum didalam L1[1..N-1]

Pertukarkan harga maksimum dng L[N-1]

• Langkah 3: Tentukan Harga Maksimum didalam L1[1..N-2

Pertukarkan harga maksimum dng L[N-2]

• ……..

• Langkah N-1: Tentukan Harga Maksimum didalam L1[1..2]

Pertukarkan harga maksimum dng L[2].

Selection Sort : AlgorthmSELECTIONSORT(A)1 for i← 1 to length[A]-1 2 min = i;3 do for j ← i+1 to length[A]4 do if A[j] < A[min]5 min = j;6 exchange A[min] ↔ A[i]

Prinsip kerja:Dari elemen sebanyak n, 1. Carilah elemen terkecil dari array A, dan swap-lah

elemen terkecil tersebut dengan elemen pertama (A[1] ). 2. Carilah elemen terkecil kedua dari array A, dan swap-

lah elemen tersebut dengan elemen kedua (A[2])3. Ulangi sampai n-1 elemen pertama dari array A

Selection Sorting

1 2 3 4 5

27 7 19 9 4

The minimal

1

The minimal

2

The minimal

5

Selection Sorting

1 2 3 4 5

2 7 19 9 27

Selection Sorting

1 2 3 4 5

2 7 9 19 27

Metode Sisipan (Insertion Sort)• Dari namanya, pengurutan sisip (insertion

sort) adalah metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat.

• Pencarian posisi yang tepat dilakukan dengan pencarian beruntun. Selama pencarian posisi yang tepat dilakukan pergeseran elemen larik.

30

Metode Sisipan: PseudocodeINSERTION-SORT(A)1 for j←2 to length[A]2 do key←A[j]3 Insert A[j] ke sekuens yang

sudah disorting A[1…j-1] 4 i← j-15 while i>0 and A[i] > key6 do A[i+1] ←A[i]7 i ← i -18 A[i+1] ←key

31

Metode Sisipan: Algoritma(Ascending)• Andaikan: L[1] dianggap sudah tempatnya.

• Langkah 2: L[2] harus dicari tempatnya yang tepat pada L[1..2]

dengan cara menggeser elemen L[1] ke

kanan bila L[1] lebih besar dari L[2]. Misalkan

posisi elemen yang tepat adalah K sisipkan L[2]

pada K.

• Langkah 3: L[3] harus dicari tempatnya yang tepat pada L[1..3]

dengan cara menggeser elemen L[1..2] ke

kanan bila L[1..2] lebih besar dari L[3]. Misalkan

posisi elemen yang tepat adalah K sisipkan

L[3] pada K.

32

Metode Sisipan: Algoritma(Ascending)

• Langkah 4: L[4] harus dicari tempatnya yang tepat

pada L[1..4] dengan cara menggeser elemen

L[1..4] ke kanan bila L[1..4] lebih besar dari L[4].

Misalkan posisi elemen yang tepat adalah K sisipkan

L[4] pada K.

• Langkah N: L[N] harus dicari tempatnya yang tepat

pada L[1..N] dengan cara menggeser elemen L[1..N ke

kanan bila L[1..N] lebih besar dari L[N]. Misalkan posisi

elemen yang tepat adalah K sisipkan L[N] pada K.

33

Metode Sisipan: Contoh (Ascending)

34

22 5 18 10 20 11 Elemen L1 dianggap sudah terurut

1 2 3 4 5 6


35

22 5 18 10 20 11

2 22 5 18 10 20 11 2 3 4 5 6

Elemen L1 dianggap sudah terurut

1 2 3 4 5 6

Cari posisi yang tepat untuk L[2] pada L[1..2]


36

22 5 18 10 20 11

2 5 22 18 10 20 11 2 3 4 5 6


1 2 3 4 5 6



22 5 18 10 20 11

2

3

5 22 18 10 20 1

5 22 18 10 20 1

1 2 3 4 5 6

1 2 3 4 5 6


1 2 3 4 5 6




22 5 18 10 20 11

2

3

5 22 18 10 20 1

5 18 22 10 20 1

1 2 3 4 5 6

1 2 3 4 5 6


1 2 3 4 5 6




22 5 18 10 20 11

2

3

4

5 22 18 10 20 1

5 18 22 10 20 1

5 18 22 10 20 1

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6


1 2 3 4 5 6





40

22 5 18 10 20 11

2

3

4

5 22 18 10 20 1

5 18 22 10 20 1

5 10 18 22 20 1

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6


1 2 3 4 5 6





22 5 18 10 20 1

5 22 18 10 20 1

5 18 22 10 20 1

5 10 18 22 20 1

5 10 18 22 20 1

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6


1 2 3 4 5 6





1

2

3

4

5


22 5 18 10 20 11

2

3

4

5

5 22 18 10 20 1

5 18 22 10 20 1

5 10 18 22 20 1

5 10 18 20 22 1

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6


1 2 3 4 5 6






43

22 5 18 10 20 1

5 10 18 20 22 1

1

2

3

4

5

6

5 22 18 10 20 1

5 18 22 10 20 1

5 10 18 22 20 1

5 10 18 20 22 1

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6


1 2 3 4 5 6







44

22 5 18 10 20 1

1 5 10 18 20 22

1

2

3

4

5

6

5 22 18 10 20 1

5 18 22 10 20 1

5 10 18 22 20 1

5 10 18 20 22 1

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6


1 2 3 4 5 6





Cari posisi yang tepat untuk L[6] pada L[1..6]SELESAI

Metode Shell• Penemu : Donald Shell pada tahun 1959

• Metode perbandingan dan pertukaran

• Perbandingan dimulai dari separuh list yang akan disortir dengan separuh bagian yang lain.

• Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu – sehingga membentuk sebuah sub-list, kemudikan dilakukan penukaran bila diperlukan

45

Metode Shell• Contoh :

– Jika terdapat 100 elemen, diperbandingkan elemen 1 dan elemen 51, elemen 2 dan elemen 52 dst. Selanjutnya algoritma akan membandingkan elemen 1 dan elemen 26, elemen 2 dan elemen 27 dst.

46

Langkah 1: GAP = 10/2 = 5

22 73 26 55 18 81 94 76 47 98

81 94 76 55 98 22 73 26 47 18

81

22

9473

76

26

5547

9818

Metode Shell: Contoh (Descending)

Langkah 2: GAP = 5

81 94 76 55 98 22 73 26 47 18

81 94 76 55 98 22 73 26 47 18

81

22

9473

76

26

5547

9818

Metode Shell: Contoh

Langkah 3: GAP = 5/2=2

81 94 76 55 98 22 73 26 47 18

81 94 98 55 76 26 73 22 47 18

817394

2298 4755

22

76 18

7655

7622

2673


Langkah 4: GAP = 2

81 94 98 55 76 26 73 22 47 18

98 94 81 55 76 26 73 22 47 18

987394

2281 4755

22

76 18

8155

7626

2673


Langkah 5: GAP = 2

98 94 81 55 88 26 73 22 47 18

98 94 81 55 88 26 73 2247 18

987394

2281 4755

22

88 18

8155

8826

2673


Langkah 6: GAP = 2/2=1

98 94 81 55 76 26 73 22 47 18

98 94 81 76 55 73 26 47 22 18

982694

26812276

47

55 22

9481

55 55

7326

22

18


Langkah 7: GAP = 1

98 94 81 76 55 82 26 47 22 18

98 94 81 76 82 55 47 26 22 18

985594

26812676

26

82 22

9481

76 55

5547

22

18


Langkah 8: GAP = 1

98 94 81 76 73 55 47 26 22 18

98 94 81 76 73 55 47 26 22 18

985594

47812676

26

73 22

9481

76 73

5547

22

18


Metode Merge• Metode penggabungan biasanya digunakan

pada pengurutan berkas.

• Kunci dari Merge Sort adalah menggabung dua berkas terurut menjadi sebuah kesatuan

Asumsi: ada 2 berkas X (x1x2…xm) dan Y(y1y2…

yn) maka hasilnya adalah Z(z1z2…zm+n)

• Contoh:

L1 = { 3 8 9 } L2 = { 1 5 7 }

merge(L1, L2) = { 1 3 5 7 8 9 }

55

Merge Sort: AlgoritmaDiberikan berkas L dengan panjang k:

• If k == 1 berkas sudah terurut

• Else:– Merge Sort sisi kiri (0 thru k/2)

– Merge Sort sisi kanan (k/2+1 sampai k)

– Merge sisi kanan dengan sisi kiri

Contoh

presentasi kelompok 3

Documents