Python/Java(sertakan listing program dan hasil eksekusinya) Persoalan: Mengurutkan list/array yang

Berikut ini adalah pertanyaan dari qed pada mata pelajaran TI untuk jenjang Sekolah Dasar

Python/Java(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]

Jawaban dan Penjelasan

Berikut ini adalah pilihan jawaban terbaik dari pertanyaan diatas.

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 \tt list, sudah ada method \tt sort(). 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 \tt sort(). 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 \tt low, \tt mid, dan \tt high (atau menggunakan nama lain juga boleh).

Pertama, inisialisasi \tt lowdan\tt mid dengan 0 (list/array pada Python adalah 0-based). Dan inisialisasi \tt high dengan indeks elemen terakhir, yaitu \tt n-1, atau \tt len(array)-1.

Lalu, iterasikan \tt mid.

Selama \tt mid \le high, lakukan:

  • Pada setiap iterasi, jika menemukan elemen terkecil (2), yang berarti \tt arr[mid] == 2, maka lakukan pertukaran elemen antara \tt arr[low]dengan\tt arr[mid], dan inkrementasi \tt lowdan\tt mid.
  • Ketika menemukan elemen terbesar (4), yang berarti \tt arr[mid] == 4, maka lakukan pertukaran elemen antara \tt arr[mid]dengan\tt arr[high], dan dekrementasi \tt high.
  • Kondisi terakhir, menemukan elemen tengah (3), yang berarti \tt arr[mid] == 3, maka lakukan inkrementasi \tt mid (tidak ada pertukaran elemen pada kondisi ini).

Secara sekilas, algoritma tersebut mirip dengan bubble atau insertion sort. Namun silahkan amati lagi perbedaannya.

Kode Program (Python)# sory234.py# oleh: hydef swap(a, b):    tmp = a; a = b; b = tmp;    return a, bdef 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 += 1import randomdef 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'[{

Semoga dengan pertanyaan yang sudah terjawab oleh henriyulianto dapat membantu memudahkan mengerjakan soal, tugas dan PR sekolah kalian.

Apabila terdapat kesalahan dalam mengerjakan soal, silahkan koreksi jawaban dengan mengirimkan email ke yomemimo.com melalui halaman Contact

Last Update: Fri, 18 Nov 22