Ada 4 fondasi berpikir komputasional yang dikenal dalam ilmu Informatika, yaitu Abstraksi, Algoritma, Dekomposisi dan Pola (AADP), yang secara garis besar dijelaskan sebagai berikut.

1. Dekomposisi dan formulasi persoalan sedemikian rupa sehingga dapat diselesaikan dengan cepat dan efisien serta optimal dengan menggunakan komputer sebagai alat bantu. Persoalan yang sulit apalagi besarakan menjadi mudah jika diselesaikan sebagian-sebagian secara sistematis.

2. Abstraksi, yaitu menyarikan bagian penting dari suatu permasalahan dan mengabaikan yang tidak penting sehingga memudahkan fokus kepada solusi.

3. Algoritma, yaitu menuliskan otomasi solusi melalui berpikir algoritmik (langkah-langkah yang terurut) untuk mencapai suatu tujuan (solusi). Jika langkah yang runtut ini diberikan ke komputer dalam bahasa yang dipahami oleh komputer, kalian akan dapat “memerintah” komputer mengerjakan langkah tersebut.

4. Pengenalan pola persoalan, generalisasi serta mentransfer proses penyelesaian persoalan ke persoalan lain yang sejenis.

Perlu dicatat bahwa AADP bukan tahapan, dan bahkan dapat dilakukan secara bersamaan. Proses berpikir manusia sangat canggih, tidak hanya sekuensial seperti komputer. BK perlu diasah mulai dari persoalan sederhana dan kecil. Kemudian, secara bertahap, persoalannya ditingkatkan menjadi makin besar dan kompleks. Makin besar dan kompleks suatu persoalan, solusinya makin membutuhkan komputer agar dapat diselesaikan secara efisien. Pada tingkat SD dan SMP, strategi penyelesaian persoalan belum secara khusus dirumuskan dalam bentuk algoritma. Pada tingkat SMA, siswa akan belajar bagaimana caranya agar solusi masalahnya bisa dituliskan dalam bentuk algoritma yang efisien dan siap dibuat menjadi program komputer.

Topik yang dipilih dalam BK untuk SMA merupakan persoalanpersoalan mendasar terkait kehidupan sehari-hari yang perlu dikuasai dan mengandung konsep informatika. Dengan mempelajari dan membahas topik ini, diharapkan siswa akan mendapatkan dasar pengetahuan yang diperlukan untuk menemukan solusi-solusi yang membutuhkan program komputer.

Melalui kasus yang dibahas, siswa diharapkan dapat membentuk katalog solusi, yang saat dibutuhkan, akan tinggal dipakai. Melalui kegiatan BK ini, siswa menabung potongan solusi yang kelak dapat dirangkai menjadi pola solusi yang dibutuhkan untuk persoalan nyata yang dihadapi.

Berpikir Komputasional sebetulnya idealnya dijalankan secara paralel dengan aktivitas pemrograman, dan merupakan satu alur proses belajar. BK lebih berfokus kepada analisis permasalahan dan strategi yang tepat untuk mendapatkan solusi. Sementara, pemrograman berfokus pada strategi mengimplementasikan solusi menjadi program komputer. Keduanya saling melengkapi sehingga siswa perlu diajak untuk secara mandiri dan aktif serta kreatif belajar merangkai keduanya.

Implementasi menjadi program memang tidak ditekankan menjadi aktivitas wajib dan tidak secara eksplisit dituliskan sebagai kegiatan dalam unit BK ini, tetapi diharapkan guru dapat menyemangati siswa agar dapat melakukannya. Hal ini juga untuk mengakomodir siswa yang kurang tertarik dan kurang berbakat hal teknis, tetapi lebih memiliki hasrat dan bakat dalam problem solving. BK lebih berfokus ke aspek abstraksi dan membangun algoritma dari solusi dari persoalan.

Aspek otomasi dan analisis hasil eksekusi program (yang dalam gambar di sebelah disebut sebagai “visualisasi”) dicakup pada pemrograman. Di tahap awal, untuk anak usia dini, BK bahkan bukan dimulai dari persoalan, melainkan dari benda nyata dan tugas yang jelas untuk mahir menerapkan AADP dalam berbagai situasi. Untuk siswa tingkat SMA, diharapkan guru memahami bahwa CT pada tingkatan SMA tidak hanya berlatih dekomposisi, pengenalan pola, abstraksi, dan algoritma yang sudah banyak diasah pada tingkatan SMP, tetapi sudah mengemas semuanya dalam problem solving. Dari banyak konsep informatika, ada 6 konsep yang penting, yang akan dipilih untuk dilaksanakan sesuai urutan yang ditentukan guru, yaitu: pencarian (searching), pengurutan (sorting), stack, dan queue. Keenam konsep tersebut merupakan abstraksi dan generalisasi dari persoalan sehari-hari yang akan melatarbelakangi banyak persoalan komputasi.

INSERTION SORT

Insertion Sort merupakan sebuah teknik pengurutan dengan cara membandingkan dan mengurutkan dua data pertama pada array, kemudian membandingkan data para array berikutnya apakah sudah berada di tempat semestinya. Algorithma insertion sort seperti proses pengurutan kartu yang berada di tangan kita. Algorithma ini dapat mengurutkan data dari besar ke kecil (Ascending) dan kecil ke besar (Descending). Algoritma ini tidak cocok untuk set data dengan jumlah besar karena kompleksitas dari algorithma ini adalah Ο() di mana n adalah jumlah item.

Berikut gambaran dari implementasi Insertion Sort:

1st Cycle:
(70, 60, 30, 50, 40, 20) -> (60, 70, 30, 50, 40, 20)
(60, 70, 30, 50, 40, 20)

2nd Cycle:
(60, 70, 30, 50, 40, 20) -> (60, 30, 70, 50, 40, 20)
(60, 30, 70, 50, 40, 20) -> (30, 60, 70, 50, 40, 20)
(30, 60, 70, 50, 40, 20)

3rd Cycle:
(30, 60, 70, 50, 40, 20) -> (30, 60, 50, 70, 40, 20)
(30, 60, 50, 70, 40, 20) -> (30, 50, 60, 70, 40, 20)
(30, 50, 60, 70, 40, 20) -> (30, 50, 60, 70, 40, 20)
(30, 50, 60, 70, 40, 20)

4th Cycle:
(30, 50, 60, 70, 40, 20) -> (30, 50, 60, 40, 70, 20)
(30, 50, 60, 40, 70, 20) -> (30, 50, 40, 60, 70, 20)
(30, 50, 40, 60, 70, 20) -> (30, 40, 50, 60, 70, 20)
(30, 40, 50, 60, 70, 20) -> (30, 40, 50, 60, 70, 20)
(30, 40, 50, 60, 70, 20)

5th Cycle:
(30, 40, 50, 60, 70, 20) -> (30, 40, 50, 60, 20, 70)
(30, 40, 50, 60, 20, 70) -> (30, 40, 50, 20, 60, 70)
(30, 40, 50, 20, 60, 70) -> (30, 40,20, 50, 60, 70)
(30, 40, 20, 50, 60, 70) -> (30, 20, 40, 50, 60, 70)
(30, 20, 40, 50, 60, 70) -> (20, 30, 40, 50, 60, 70)
(20, 30, 40, 50, 60, 70)

Cara Kerja Insertion Sort

Berikut adalah beberapa langkah yang menggambarkan cara kerja insertion sort:

1. Mulai proses pengurutan dari elemen kedua dengan asumsi bagian pertama sudah berada di sub-array terurut.

2. Ambil elemen berikutnya dari bagian yang belum diurut dan simpan sebagai key (bagian yang ditempatkan pada posisi tepat di sub-array terurut).

3. Bandingkan key dengan elemen-elemen di sub-array yang telah terurut dari belakang ke depan.

4. Ulangi langkah sebelumnya hingga menemukan posisi di mana key lebih besar atau sama dengan elemen di sub array atau hingga mencapai awal array.

5. Ulangi proses tersebut hingga seluruh array diurutkan.

Kelebihan dan Kekurangan Insertion Sort

Insertion sort adalah algoritma pengurutan yang cukup sederhana dan intuitif. Meski begitu, insertion sort memiliki kelebihan dan kekurangan yang harus dipertimbangkan. Berikut adalah beberapa kelebihan dan kekurangannya:

Kelebihan Insertion Sort

Berikut adalah beberapa kelebihan insertion sort yang merupakan keunggulannya:

• Sederhana dan Mudah Dipahami: Algoritma insertion sort sangat sederhana untuk dipahami dan diimplementasikan. Ini menjadikannya pilihan yang baik untuk pendidikan dan penggunaan dalam skenario sederhana.

• Efektif untuk Data Set Kecil: Insertion sort sangat efisien untuk data set yang kecil, terutama jika data set tersebut sudah hampir terurut.

• Stable: Insertion sort adalah stable sort. Artinya, dua elemen dengan nilai kunci yang sama akan mempertahankan urutan relatif mereka setelah pengurutan.

• In-Place: Insertion sort tidak memerlukan alokasi memori tambahan yang signifikan.

• Online: Insertion sort dapat bekerja sebagai algoritma pengurutan online.

Kekurangan Insertion Sort

Berikut adalah beberapa kekurangan insertion sort yang harus dipertimbangkan:

• Tidak Efisien untuk Data Set Besar: Kompleksitas waktu algoritma ini membuatnya tidak efisien untuk mengurutkan data set besar.

• Banyak Operasi Swap dan Perbandingan: Untuk elemen yang harus dipindahkan ke dekat awal array, insertion sort memerlukan banyak operasi swap dan perbandingan. Hal ini dapat mengurangi efisiensinya.

• Sensitif terhadap Urutan Input: Meskipun efektif untuk data yang hampir terurut, ini membuatnya tidak efisien jika elemen-elemen pada awalnya terurut dalam urutan terbalik. Ini memerlukan jumlah perbandingan dan perpindahan maksimum.

Implementasi Insertion Sort

Untuk memahami insertion sort secara lebih dalam, MinDi siapkan contoh implementasi kodenya. Implementasi insertion sort ini digunakan untuk mengurutkan array [5, 6, 11, 12, 13] menjadi [12, 11, 13, 5, 6]. 

Selection sort adalah teknik pengurutan yang beroperasi dengan memisahkan array menjadi dua bagian. Pemisahan tersebut membagi subarray menjadi yang telah diurutkan dan tidak diurutkan.

Lebih detailnya, algoritma pengurutan ini bekerja dengan memilih elemen terkecil atau terbesar dari subarray yang belum diurutkan. Lalu, elemen terpilih ini dipindahkan ke akhir subarray yang sudah diurutkan.

Pendekatan tersebut bisa secara bertahap membangun bagian akhir array yang diurutkan hingga semua elemen terurut.

Selection sort adalah teknik pengurutan yang beroperasi dengan memisahkan array menjadi dua bagian. Pemisahan tersebut membagi subarray menjadi yang telah diurutkan dan tidak diurutkan.

Lebih detailnya, algoritma pengurutan ini bekerja dengan memilih elemen terkecil atau terbesar dari subarray yang belum diurutkan. Lalu, elemen terpilih ini dipindahkan ke akhir subarray yang sudah diurutkan.

Pendekatan tersebut bisa secara bertahap membangun bagian akhir array yang diurutkan hingga semua elemen terurut.

Cara Kerja Selection Sort

Cara kerja selection sort melibatkan beberapa langkah iteratif yang sistematis. Proses ini dimulai dengan asumsi bahwa array yang akan diurutkan terbagi menjadi dua bagian terurut dan tidak terurut. Beberapa langkah-langkah detail dari cara kerja selection sort adalah:

1. Inisialisasi

Tahap pertama dalam selection sort adalah inisialisasi. Ini dimulai dengan menganggap seluruh array sebagai subarray yang belum diurutkan. Subarray terurut masih kosong karena belum ada elemen yang diproses.

2. Pencarian Elemen Minimum

Tahap kedua dalam selection sort adalah pencarian elemen minimum. Ini bisa dimulai dengan memilih elemen minimum dari subarray yang belum diurutkan. 

Prosesnya dilakukan dengan membandingkan setiap elemen dalam subarray tersebut untuk menemukan nilai terkecil. Pada variasi terurut secara menurun, kamu bisa menemukan elemen maksimum.

3. Pertukaran

Tahapan berikutnya dalam selection sort adalah pertukaran. Apabila elemen minimum atau maksimum ditemukan, penukaran bisa dilakukan.

Hal tersebut dilakukan dengan menukar elemen minimum/maksimum dengan komponen pertama dari subarray yang belum diurutkan. Akan tetapi, pertukaran ini tidak perlu dilakukan jika elemen minimum/maksimum sudah ada di posisi pertama.

4. Perubahan Subarray

Tahapan selanjutnya dalam selection sort adalah perubahan subarray. Hal ini bisa dilakukan setelah pertukaran. Elemen yang telah ditemukan posisinya dalam urutan sesuai dipindahkan ke subarray terurut.

Artinya, tiap iterasi memiliki batas antara subarray yang sudah dan belum diurutkan bergeser satu elemen ke kanan.

5. Iterasi

Terakhir adalah iterasi. Proses ini merupakan pengulangan tahapan 2 hingga 4 untuk setiap elemen subarray yang belum diurutkan.

Tiap iterasi, elemen pertama dari subarray yang belum diurutkan dianggap sudah berada di posisi sesuai dalam subarray terurut.

Kekurangan dan Kelebihan Selection Sort

Selection sort adalah algoritma pengurutan yang sederhana dan mudah dipahami. Meski begitu, selection sort juga memiliki kelebihan dan kekurangan. Berikut adalah beberapa kelebihan dan kekurangan dari algoritma selection sort:

Kelebihan Selection Sort

Berikut adalah beberapa kelebihan selection sort yang menjadikannya unggul:

• Sederhana dan Mudah Dipahami: Hal ini membuat selection sort mudah dipahami dan digunakan oleh semua orang, termasuk pemula.

• Penggunaan Memori yang Efisien: Selection sort adalah algoritma pengurutan in-place. Artinya, ini tidak memerlukan ruang tambahan signifikan. Sebab, algoritma ini hanya memerlukan ruang untuk penyimpanan sementara.

• Tidak Sensitif Terhadap Urutan Awal: Performa algoritma tidak dipengaruhi oleh urutan awal elemen dalam array. Mulai dari array yang sudah diurutkan, terurut terbalik, atau acak. Waktu eksekusinya akan tetap konsisten.

• Performa yang Dapat Diprediksi: Setiap elemen memerlukan pencarian melalui seluruh bagian yang belum diurutkan untuk menemukan elemen minimum/maksimum. Jumlah perbandingan yang dibutuhkan selalu tetap, menjadikan performanya dapat diprediksi.

Kekurangan Selection Sort

Beberapa kekurangan selection sort yang perlu dipertimbangkan adalah:

• Efisiensi Waktu yang Rendah: Kompleksitas waktunya menjadikan ini kurang efisien untuk mengurutkan data set yang besar.

• Tidak Stabil: Algoritma ini dapat mengubah urutan elemen yang nilainya sama. Artinya, jika ada dua elemen dengan nilai yang sama, posisi relatif mereka dalam array mungkin berubah setelah pengurutan.

• Tidak Adapatif: Selection sort melakukan jumlah operasi yang sama terlepas dari seberapa terurutnya array awal. Artinya, tidak ada peningkatan efisiensi waktu untuk array yang sudah sebagian atau sepenuhnya diurutkan.

• Tidak Skalabel untuk Data Set Besar: Performanya yang menurun secara signifikan dengan peningkatan ukuran data set, selection sort tidak disarankan untuk aplikasi pengurutan data skala besar.