(sertakan listing program dan hasil eksekusinya)
Persoalan: Mengurutkan list/array yang memiliki elemen bernilai 2, 3, dan 4 saja.
Contoh:
Array = [3, 2, 2, 3, 4, 3]
Hasil pengurutan = [2, 2, 3, 3, 3, 4]
Kode Program (Python)
# sory234.py
# oleh: hy
def swap(a, b):
tmp = a; a = b; b = tmp;
return a, b
def sort234(arr):
low, mid = 0, 0
high = len(arr)-1
while mid <= high:
if arr[mid] == 2:
# tukar posisi low dan mid
arr[low], arr[mid] = swap(arr[low], arr[mid])
low += 1; mid += 1
elif arr[mid] == 4:
# tukar posisi mid dan high
arr[mid], arr[high] = swap(arr[mid], arr[high])
high -= 1
else: # arr[mid] = 3
mid += 1
import random
def main():
# Buat list sebagai contoh kasus
for i in range(2, 8):
l = []; random.seed()
print(f'\nCONTOH KASUS {i-1}')
for i in range(2**i):
l.append(random.randint(2, 4))
print(f'[{", ".join([str(x) for x in l])}]')
sort234(l)
print('Diurutkan menjadi...')
print(f'[{", ".join([str(x) for x in l])}]')
if __name__ == '__main__':
main()
_____________
Contoh Hasil Eksekusi
(array/list diisi secara random dengan nilai 2, 3, dan 4)
CONTOH KASUS 1
[4, 4, 4, 2]
Diurutkan menjadi...
[2, 4, 4, 4]
CONTOH KASUS 2
[2, 2, 2, 3, 3, 2, 2, 4]
Diurutkan menjadi...
[2, 2, 2, 2, 2, 3, 3, 4]
CONTOH KASUS 3
[4, 3, 3, 2, 3, 4, 3, 4, 3, 3, 4, 3, 4, 4, 4, 3]
Diurutkan menjadi...
[2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4]
CONTOH KASUS 4
[3, 2, 4, 2, 2, 3, 3, 4, 3, 2, 2, 4, 3, 2, 3, 2, 2, 2, 2, 4, 2, 3, 2, 3, 4, 3, 2, 2, 3, 4, 3, 4]
Diurutkan menjadi...
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4]
CONTOH KASUS 5
[4, 2, 3, 4, 2, 3, 4, 4, 4, 3, 2, 4, 4, 3, 4, 3, 2, 2, 2, 2, 4, 3, 2, 2, 2, 4, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 4, 3, 2, 4, 2, 2, 3, 4, 4, 3, 4, 3, 4, 3, 3, 4, 2, 2, 2, 3, 2, 2, 4, 2, 3, 3, 4]
Diurutkan menjadi...
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
CONTOH KASUS 6
[3, 3, 2, 2, 3, 4, 3, 3, 4, 2, 3, 4, 2, 2, 3, 4, 2, 4, 3, 2, 4, 3, 3, 3, 2, 2, 3, 4, 3, 2, 3, 3, 2, 4, 4, 4, 3, 4, 3, 2, 2, 4, 4, 2, 4, 3, 3, 4, 4, 3, 2, 3, 2, 4, 2, 2, 2, 2, 4, 2, 2, 2, 2, 3, 2, 2, 2, 4, 2, 3, 2, 2, 2, 3, 3, 4, 4, 4, 4, 2, 2, 4, 3, 4, 4, 4, 3, 4, 4, 3, 3, 3, 2, 4, 4, 4, 2, 2, 3, 4, 3, 2, 4, 2, 2, 3, 3, 4, 3, 2, 2, 2, 4, 4, 4, 3, 2, 3, 4, 3, 3, 4, 4, 2, 4, 4, 4, 4]
Diurutkan menjadi...
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
_____________
Pembahasan
Pada Python, untuk class [tex]\tt list[/tex], sudah ada method [tex]\tt sort()[/tex]. Mengapa tidak menggunakan method ini untuk mengurutkan isi array dengan spesifikasi seperti pada persoalan?
Saya tidak tahu apakah yang dimaksud dalam pertanyaan adalah benar penggunaan method [tex]\tt sort()[/tex]. Atau menggunakan algoritma pengurutan yang lain (bubble, insertion, quick, merge, heap, dsb.).
Namun, menurut saya, kuncinya adalah hanya ada 3 nilai yang mungkin pada array, yaitu 2, 3, dan 4. Penggunaan metode pengurutan seperti yang kita kenal di atas akan menghasilkan kompleksitas waktu yang lebih tinggi, alias kurang efisien.
Karena hanya 3 nilai yang mungkin, maka kompleksitas waktu algoritma pengurutan akan lebih baik apabila kita melakukan prinsip "urutkan sambil jalan". Ada 3 variabel yang berperan di sini, yaitu [tex]\tt low[/tex], [tex]\tt mid[/tex], dan [tex]\tt high[/tex] (atau menggunakan nama lain juga boleh).
Pertama, inisialisasi [tex]\tt low[/tex] dan [tex]\tt mid[/tex] dengan 0 (list/array pada Python adalah 0-based). Dan inisialisasi [tex]\tt high[/tex] dengan indeks elemen terakhir, yaitu [tex]\tt n-1[/tex], atau [tex]\tt len(array)-1[/tex].
Lalu, iterasikan [tex]\tt mid[/tex].
Selama [tex]\tt mid \le high[/tex], lakukan:
- Pada setiap iterasi, jika menemukan elemen terkecil (2), yang berarti [tex]\tt arr[mid] == 2[/tex], maka lakukan pertukaran elemen antara [tex]\tt arr[low][/tex] dengan [tex]\tt arr[mid][/tex], dan inkrementasi [tex]\tt low[/tex] dan [tex]\tt mid[/tex].
- Ketika menemukan elemen terbesar (4), yang berarti [tex]\tt arr[mid] == 4[/tex], maka lakukan pertukaran elemen antara [tex]\tt arr[mid][/tex] dengan [tex]\tt arr[high][/tex], dan dekrementasi [tex]\tt high[/tex].
- Kondisi terakhir, menemukan elemen tengah (3), yang berarti [tex]\tt arr[mid] == 3[/tex], maka lakukan inkrementasi [tex]\tt mid[/tex] (tidak ada pertukaran elemen pada kondisi ini).
Secara sekilas, algoritma tersebut mirip dengan bubble atau insertion sort. Namun silahkan amati lagi perbedaannya.
[answer.2.content]