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 , sudah ada method . 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 . 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 , , dan (atau menggunakan nama lain juga boleh).

Pertama, inisialisasi dan dengan 0 (list/array pada Python adalah 0-based). Dan inisialisasi dengan indeks elemen terakhir, yaitu , atau .

Lalu, iterasikan .

Selama , lakukan:

• Pada setiap iterasi, jika menemukan elemen terkecil (2), yang berarti , maka lakukan pertukaran elemen antara dengan, dan inkrementasi dan.
• Ketika menemukan elemen terbesar (4), yang berarti , maka lakukan pertukaran elemen antara dengan, dan dekrementasi .
• Kondisi terakhir, menemukan elemen tengah (3), yang berarti , maka lakukan inkrementasi (tidak ada pertukaran elemen pada kondisi ini).

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