Sorting (Pengurutan)
- Usaha : mengurutkan dari data tak terurut menjadi data terurut à perlu waktu
- Masalah : efisiensi (peningkatan kecepatan pencarian)
- Metode : bubble (gelembung), insertion (penyisipan), selection (pemilihan), merge (penggabungan), quick, shell, radix, dll.
Untuk simulasi macam-macam sorting bisa liat disini.
Berikut beberapa metode sorting:
A. Bubble Sort
- Prinsip : seperti gelembung, yang besar akan “naik”, yang kecil akan “tetap” di bawah
- Setiap data (misalnya data pertama) akan dibandingkan dengan data yang ada di sebelahnya (dari data kedua sampai selesai) .
- Bila data pertama tersebut lebih besar dari data yang ada pada data sesudahnya, dilakukan penukaran tempat atau posisi data.
- Demikian, untuk data kedua sampai dengan data terakhir dilakukan dengan cara serupa.
Ilustrasi
Data awal :
|
[8, 4, 7, 3, 1, 2, 6, 5]
|
8ßà4, 4ßà3, 3ßà1
|
fase 1
|
[1, 8, 7, 4, 3, 2, 6, 5]
|
8ßà7, 7ßà4, 4ßà3, 3ßà2
|
fase 2
|
[1, 2, 8, 7, 4, 3, 6, 5]
|
8ßà7, 7ßà4, 4ßà3
|
fase 3
|
[1, 2, 3, 8, 7, 4, 6, 5]
|
8ßà7, 7ßà4
|
fase 4
|
[1, 2, 3, 4, 8, 7, 6, 5]
|
8ßà7, 7ßà6, 6ßà5
|
fase 5
|
[1, 2, 3, 4, 5, 8, 7, 6]
|
8ßà7, 7ßà6
|
fase 6
|
[1, 2, 3, 4, 5, 6, 8, 7]
|
8ßà7
|
fase 7
|
[1, 2, 3, 4, 5, 6, 7, 8]
| |
fase 8
|
[1, 2, 3, 4, 5, 6, 7, 8]
|
void tukar (int &a, int &b)
{ int temp;
temp = a;
a = b;
b = temp;
}
void buble_sort (int x[], int n)
{ int i, j;
for (i = 0; i<n-1; i++)
for (j = i+1; j<n; j++)
if (x[i] > x[j]) tukar(x[i], x[j]);
}
|
B. Insertion Sort
- Addalah metode pengurutan data dengan menempatkan setiap elemen data pada posisinya dengan cara melakukan perbandingan dengan data-data yang ada. Dalam pengurutan data ke dua, kemudian data yang diambil akan dibandingan dengan data-data yang ada disebuah kiri/ data sebelumnya (data-data sebelumnya data yang diambil/ jika selesai akan dilanjutkan dengan data selanjutnya).
Ilustrasi
Data awal :
|
[8, 4, 7, 3, 1, 2, 6, 5]
|
fase 1, 4 masuk
|
[4, 8, 7, 3, 1, 2, 6, 5]
|
fase 2, 7 masuk
|
[4, 7, 8, 3, 1, 2, 6, 5]
|
fase 3, 3 masuk
|
[3, 4, 7, 8, 1, 2, 6, 5]
|
fase 4, 1 masuk
|
[1, 3, 4, 7, 8, 2, 6, 5]
|
fase 5, 2 masuk
|
[1, 2, 3, 4, 7, 8, 6, 5]
|
fase 6, 6 masuk
|
[1, 2, 3, 4, 6, 7, 8, 5]
|
fase 7, 5 masuk
|
[1, 2, 3, 4, 5, 6, 7, 8]
|
fase 8
|
[1, 2, 3, 4, 5, 6, 7, 8]
|
procedure insertion_sort(input/output data:larik;
input n:integer)
|
Deklarasi
i, j, ditangan : integer
|
Deskripsi
for j ß 2 to n do
ditangan ß data[j]
for i ß j-1 asalkan {(i >= 0) dan (data[i] > ditangan)} do
data[i+1] ß data[i]
i--
endfor
data[i+1] ß ditangan
|
C. Selection Sort
Ide :
- Diberikan sederetan kartu :[8, 4, 7, 3, 1, 2, 6, 5]
- Langkah 1 : dicari terkecil pertama ditaruh paling kiri (pertama)
- Langkah 2 : dicari terkecil kedua ditaruh paling kiri kedua, dst.
Data awal :
|
[8, 4, 7, 3, 1, 2, 6, 5]
|
1 terkecil, 8ßà1
|
fase 1
|
[1, 4, 7, 3, 8, 2, 6, 5]
|
2 terkecil, 4ßà2
|
fase 2
|
[1, 2, 7, 3, 8, 4, 6, 5]
|
3 terkecil, 7ßà3
|
fase 3
|
[1, 2, 3, 7, 8, 4, 6, 5]
|
4 terkecil, 7ßà4
|
fase 4
|
[1, 2, 3, 4, 8, 7, 6, 5]
|
5 terkecil, 8ßà5
|
fase 5
|
[1, 2, 3, 4, 5, 7, 6, 8]
|
6 terkecil, 7ßà6
|
fase 6
|
[1, 2, 3, 4, 5, 6, 7, 8]
|
7 terkecil, tetap
|
fase 7
|
[1, 2, 3, 4, 5, 6, 7, 8]
| |
fase 8
|
[1, 2, 3, 4, 5, 6, 7, 8]
|
Procedure minimum(input A : larik; dari, n : integer; output tempat : integer)
{ mencari tempat di mana elemen terkecil ditemukan}
|
Deklarasi
i, min : integer
|
Deskripsi
min ß A[dari];
tempat ß dari;
for i ß dari+1 to n do
if A[i] < min then
min ß A[i];
tempat ß i;
endif
endfor
|
0 komentar:
Posting Komentar