Bubble & Selection Sort
Sorting/Mengurutkan Array of Integer :¶
Diberikan sebuah random Array of Integer, diinginkan bahwa urutan elemen Array of Integer tersebut berubah menjadi dari elemen terkecil ke terbesar.
Terdapat banyak metode untuk mengururtkan array, dinataranya :
- Bubble Sort
- Selection Sort
- Insertion Sort
Pada tulisan ini akan dibahas terkait dengan Bubble Sort dan Selection Sort
Bubble Sort
Ide dari Selection Sort adalah menaruh bilangan paling kecil ke array paling kanan.
- Caranya adalah bandingkan satu persatu elemen array ke i dengan elemen array ke i+1, yang lebih besar taruh di elemen ke i+1.
- Lakukan hal tersebut sejak indeks i=1 sampai n-1
- Hal tersebut membuat elemen terbesar dari array berada di elemen ke n
- Pada proses berikutnya, lakukan hal yang sama, dari indeks ke i=1 sampai n-2
- Pada proses berikutnya, lakukan hal yang sama, dari indeks ke i=1 sampai n-3. Dan seterusnya
Masukkan : random Array of Integer dengan $n$ elemen
Keluaran : Array of Integer yang sudah terurut
Langkah-langkah :
- Masukkan A=random Array Of Integer berukuran $n$
- Untuk setiap j pada {n-1,n-2,n-3,...,1}
- Untuk setiap i pada {1,2,3,...,j}
- jika A[i]>A[i+1]
- tukar elemen A[i] dengan A[i+1]
- #proses ini akan menaruh elemen paling besar di paling kanan dari array
- jika A[i]>A[i+1]
- Untuk setiap i pada {1,2,3,...,j}
Saat masuk ke program (python), indeks harus disesuaikan, karena pada python indeks mulai dari 0
In [1]:
#Bubble Sort
import random ; random.seed(3)
A = [random.randrange(1, 32, 1) for i in range(7)]
#A=list(map(int,str(1234560))) #contoh kasus terburuk untuk Bubble Sort
print("Random Array of Integer, A=",A)
iter=0
for j in range(len(A)-1):
for i in range(0,len(A)-1-j):
iter=iter+1
if A[i]>A[i+1]:
temp=A[i]
A[i]=A[i+1]
A[i+1]=temp
print('Tukar A[',i,'] dan A[',i+1,'] menjadi =',A)
print("Banyaknya iterasi pengulangan =",iter)
Random Array of Integer, A= [8, 19, 18, 5, 12, 30, 20] Tukar A[ 1 ] dan A[ 2 ] menjadi = [8, 18, 19, 5, 12, 30, 20] Tukar A[ 2 ] dan A[ 3 ] menjadi = [8, 18, 5, 19, 12, 30, 20] Tukar A[ 3 ] dan A[ 4 ] menjadi = [8, 18, 5, 12, 19, 30, 20] Tukar A[ 5 ] dan A[ 6 ] menjadi = [8, 18, 5, 12, 19, 20, 30] Tukar A[ 1 ] dan A[ 2 ] menjadi = [8, 5, 18, 12, 19, 20, 30] Tukar A[ 2 ] dan A[ 3 ] menjadi = [8, 5, 12, 18, 19, 20, 30] Tukar A[ 0 ] dan A[ 1 ] menjadi = [5, 8, 12, 18, 19, 20, 30] Banyaknya iterasi pengulangan = 21
Pengulangan yang dilakukan oleh kode di atas adalah sebanyak 21 kali tetapi yang dicetak hanya saat terjadi penukaran saja. (proses membandingkan (if) dan menukar variabel diabaikan)
Berikut kode yang memperlihatkan semua proses pengulangan.
In [2]:
#Bubble Sort
import random ; random.seed(3)
A = [random.randrange(1, 32, 1) for i in range(7)]
#A=list(map(int,str(1234560))) #contoh kasus terburuk untuk Bubble Sort
print("Random Array of Integer, A=",A)
iter=0
for j in range(len(A)-1):
for i in range(0,len(A)-1-j):
if A[i]>A[i+1]:
temp=A[i]
A[i]=A[i+1]
A[i+1]=temp
iter=iter+1
print(iter,". Cek A[",i,"] dan A[",i+1,"], Hasil pada iterasi ke-",iter,"adalah A=",A)
Random Array of Integer, A= [8, 19, 18, 5, 12, 30, 20] 1 . Cek A[ 0 ] dan A[ 1 ], Hasil pada iterasi ke- 1 adalah A= [8, 19, 18, 5, 12, 30, 20] 2 . Cek A[ 1 ] dan A[ 2 ], Hasil pada iterasi ke- 2 adalah A= [8, 18, 19, 5, 12, 30, 20] 3 . Cek A[ 2 ] dan A[ 3 ], Hasil pada iterasi ke- 3 adalah A= [8, 18, 5, 19, 12, 30, 20] 4 . Cek A[ 3 ] dan A[ 4 ], Hasil pada iterasi ke- 4 adalah A= [8, 18, 5, 12, 19, 30, 20] 5 . Cek A[ 4 ] dan A[ 5 ], Hasil pada iterasi ke- 5 adalah A= [8, 18, 5, 12, 19, 30, 20] 6 . Cek A[ 5 ] dan A[ 6 ], Hasil pada iterasi ke- 6 adalah A= [8, 18, 5, 12, 19, 20, 30] 7 . Cek A[ 0 ] dan A[ 1 ], Hasil pada iterasi ke- 7 adalah A= [8, 18, 5, 12, 19, 20, 30] 8 . Cek A[ 1 ] dan A[ 2 ], Hasil pada iterasi ke- 8 adalah A= [8, 5, 18, 12, 19, 20, 30] 9 . Cek A[ 2 ] dan A[ 3 ], Hasil pada iterasi ke- 9 adalah A= [8, 5, 12, 18, 19, 20, 30] 10 . Cek A[ 3 ] dan A[ 4 ], Hasil pada iterasi ke- 10 adalah A= [8, 5, 12, 18, 19, 20, 30] 11 . Cek A[ 4 ] dan A[ 5 ], Hasil pada iterasi ke- 11 adalah A= [8, 5, 12, 18, 19, 20, 30] 12 . Cek A[ 0 ] dan A[ 1 ], Hasil pada iterasi ke- 12 adalah A= [5, 8, 12, 18, 19, 20, 30] 13 . Cek A[ 1 ] dan A[ 2 ], Hasil pada iterasi ke- 13 adalah A= [5, 8, 12, 18, 19, 20, 30] 14 . Cek A[ 2 ] dan A[ 3 ], Hasil pada iterasi ke- 14 adalah A= [5, 8, 12, 18, 19, 20, 30] 15 . Cek A[ 3 ] dan A[ 4 ], Hasil pada iterasi ke- 15 adalah A= [5, 8, 12, 18, 19, 20, 30] 16 . Cek A[ 0 ] dan A[ 1 ], Hasil pada iterasi ke- 16 adalah A= [5, 8, 12, 18, 19, 20, 30] 17 . Cek A[ 1 ] dan A[ 2 ], Hasil pada iterasi ke- 17 adalah A= [5, 8, 12, 18, 19, 20, 30] 18 . Cek A[ 2 ] dan A[ 3 ], Hasil pada iterasi ke- 18 adalah A= [5, 8, 12, 18, 19, 20, 30] 19 . Cek A[ 0 ] dan A[ 1 ], Hasil pada iterasi ke- 19 adalah A= [5, 8, 12, 18, 19, 20, 30] 20 . Cek A[ 1 ] dan A[ 2 ], Hasil pada iterasi ke- 20 adalah A= [5, 8, 12, 18, 19, 20, 30] 21 . Cek A[ 0 ] dan A[ 1 ], Hasil pada iterasi ke- 21 adalah A= [5, 8, 12, 18, 19, 20, 30]
Selection Sort
Ide dari Selection Sort adalah menaruh bilangan paling kecil ke array paling kiri.
- Cari indeks elemen terkecil dari array, misalkan imin
- Kemudian tukar isi array elemen pertama dengan elemen ke-imin
- Dilakukan proses berikutnya, ditukar dengan elemen kedua, dst sampai ditukar dengan elemen ke n-1.
Berikut adalah algoritmanya.
Masukkan : random AoI dengan $n$ elemen
Keluaran : AoI yang sudah terurut
Langkah-langkah :
- Masukkan A=random AoI berukuran $n$
- Untuk setiap j pada {1,2,3,...,n-1}
- Misalkan indeks elemen AoI terkecil saat ini adalah j
- Untuk setiap i pada {j+1,j+2,j+3,...,n}
- jika A[imin]>A[i]
- simpan indeks imin yang baru = i
- #proses ini akan menaruh elemen paling kecil di paling kiri dari array
- jika A[imin]>A[i]
- Tukar A[imin] dengan A[j]
Saat masuk ke program (python), indeks harus disesuaikan, karena pada python indeks mulai dari 0
In [3]:
#Selection Sort
import random ; random.seed(3)
A = [random.randrange(1, 32, 1) for i in range(7)]
#A=list(map(int,str(1234560))) #contoh kasus lain, tetapi banyak iterasi tetap sama
print("Random Array of Integer, A=",A)
iter=0
for j in range(len(A)-1):
imin=j #simpan indeks minimum sementara
for i in range(j+1,(len(A))):
iter=iter+1
if A[imin]>A[i]:
imin=i
temp=A[j]
A[j]=A[imin]
A[imin]=temp
print('Tukar A[',j,'] dan A[',imin,'] menjadi =',A)
print("Banyaknya iterasi pengulangan =",iter)
Random Array of Integer, A= [8, 19, 18, 5, 12, 30, 20] Tukar A[ 0 ] dan A[ 3 ] menjadi = [5, 19, 18, 8, 12, 30, 20] Tukar A[ 1 ] dan A[ 3 ] menjadi = [5, 8, 18, 19, 12, 30, 20] Tukar A[ 2 ] dan A[ 4 ] menjadi = [5, 8, 12, 19, 18, 30, 20] Tukar A[ 3 ] dan A[ 4 ] menjadi = [5, 8, 12, 18, 19, 30, 20] Tukar A[ 4 ] dan A[ 4 ] menjadi = [5, 8, 12, 18, 19, 30, 20] Tukar A[ 5 ] dan A[ 6 ] menjadi = [5, 8, 12, 18, 19, 20, 30] Banyaknya iterasi pengulangan = 21
In [4]:
#Modifikasi Selection Sort (Langsung Ditukar)
import random ; random.seed(3)
A = [random.randrange(1, 32, 1) for i in range(7)]
#A=list(map(int,str(1234560))) #contoh kasus lain, tetapi banyak iterasi tetap sama
print("Random Array of Integer, A=",A)
iter=0
for j in range(len(A)-1):
for i in range(j+1,(len(A))):
iter=iter+1
if A[i]<A[j]:
temp=A[j]
A[j]=A[i]
A[i]=temp
print('Tukar A[',j,'] dan A[',i,'] menjadi =',A)
print("Banyaknya iterasi pengulangan =",iter)
Random Array of Integer, A= [8, 19, 18, 5, 12, 30, 20] Tukar A[ 0 ] dan A[ 3 ] menjadi = [5, 19, 18, 8, 12, 30, 20] Tukar A[ 1 ] dan A[ 2 ] menjadi = [5, 18, 19, 8, 12, 30, 20] Tukar A[ 1 ] dan A[ 3 ] menjadi = [5, 8, 19, 18, 12, 30, 20] Tukar A[ 2 ] dan A[ 3 ] menjadi = [5, 8, 18, 19, 12, 30, 20] Tukar A[ 2 ] dan A[ 4 ] menjadi = [5, 8, 12, 19, 18, 30, 20] Tukar A[ 3 ] dan A[ 4 ] menjadi = [5, 8, 12, 18, 19, 30, 20] Tukar A[ 5 ] dan A[ 6 ] menjadi = [5, 8, 12, 18, 19, 20, 30] Banyaknya iterasi pengulangan = 21
Comments
Post a Comment