Made By: Grayesi Silitonga

MINGGU V DAN VI

SORTING

SubCPMK042 - Memahami dan mampu mengimplementasikan Sorting

Algoritma sorting adalah suatu metode atau teknik untuk mengurutkan data atau elemen-elemen dalam suatu struktur data
secara teratur. Algoritma sorting merupakan salah satu konsep penting dalam pemrograman, tujuannya untuk mengubah data
yang tidak teratur menjadi urutan yang teratur, misalnya dari data yang tidak terurut menjadi data yang terurut menaik atau
menurun. Sorting Pada Struktur Data sangat penting dalam sebuah pemrograman komputer. Apa itu Sorting pada struktur
data? Sorting adalah proses pengurutan data yang sebelumnya disusun secara acak sehingga tersusun secara teratur menurut
aturan tertentu. Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun). “Sorting algorithms are
fundamental concepts in computer science and play a crucial role in organizing data efficiently. Whether you’re a beginner
programmer or preparing for technical interviews at top tech companies, understanding these algorithms is essential. In this
comprehensive guide, we’ll explore various sorting algorithms, from the simple but inefficient Bubble Sort to the more
advanced and widely-used Quick Sort” Yang artinya Algoritma pengurutan adalah konsep dasar dalam ilmu komputer dan
memainkan peran penting dalam mengatur data secara efisien. Baik Anda seorang pemula dalam pemrograman atau sedang
mempersiapkan wawancara teknis di perusahaan teknologi terkemuka, memahami algoritma ini sangat penting. Dalam
panduan komprehensif ini, kita akan mengeksplorasi berbagai algoritma pengurutan, mulai dari Bubble Sort yang sederhana
namun tidak efisien hingga Quick Sort yang lebih maju dan banyak digunakan. Sorting adalah proses mengurutkan data yang
belum terurut menjadi data terurut dalam urutan tertentu.

1. Bentuk-Bentuk Sorting

Sorting bisa dilakukan dalam dua bentuk, yaitu: ascending (menaik), yaitu data diurutkan dari nilai terkecil ke terbesar.
descending (menurun), yaitu data diurutkan dari nilai terbesar ke terkecil. Dalam pemrograman, sorting memiliki peran
penting dalam berbagai situasi, seperti mempercepat pencarian data, meningkatkan efisiensi pengelolaan data, dan
mempermudah analisis data. Oleh karena itu, pemilihan algoritma sorting yang tepat sangat berpengaruh terhadap
meningkatkan kinerja sistem yang digunakan.

1.1 Ascending

Pengurutan data secara ascending adalah pengurutan data dari nilai terendah hingga nilai tertinggi. Misalnya, jika kita ingin
mengurutkan data angka dari 1 hingga 10 secara ascending, maka urutannya akan menjadi 1, 2, 3, 4, 5, 6, 7, 8, 9, dan 10.
Pengurutan data secara ascending biasanya dilakukan untuk data yang memiliki skala atau rentang nilai yang jelas.

Contoh pengurutan data Ascending :

1.​ Urutan data umur dari yang termuda ke yang tertua

2.​ Urutan data harga dari yang termurah ke yang termahal
3.​ Urutan data tinggi badan dari yang terpendek ke yang tertinggi

Di bawah ini adalah contoh pseudocode untuk mengurutkan data secara ascending menggunakan metode bubble sort:

1.2 Descending

Pengurutan data secara descending adalah pengurutan data dari nilai tertinggi hingga nilai terendah. Misalnya, jika kita ingin
mengurutkan data angka dari 10 hingga 1 secara descending, maka urutannya akan menjadi 10, 9, 8, 7, 6, 5, 4, 3, 2, dan 1.
Pengurutan data secara descending biasanya dilakukan untuk data yang memiliki skala atau rentang nilai yang jelas, namun
urutannya dibalik.
Contoh pengurutan data Ascending :

1.​ Urutan data pendapatan dari yang tertinggi ke yang terendah

2.​ Urutan data berat badan dari yang terberat ke yang teringan
3.​ Urutan data kecepatan dari yang tercepat ke yang terendah

Tujuan utama dari proses pengurutan adalah untuk mempermudah pencarian data (searching) dan analisis data. Data yang
telah terurut memungkinkan penggunaan algoritma pencarian yang lebih efisien, seperti Binary Search, yang memiliki
kompleksitas waktu 𝑂( 𝑙𝑜𝑔 𝑛), dibandingkan Linear Search pada data acak yang memakan waktu 𝑂(𝑛). Selain itu, sorting
juga sering digunakan untuk mendeteksi duplikasi data dan membandingkan dua buah list.

2. Jenis-Jenis Sorting

Terdapat berbagai jenis algoritma pengurutan yang dikembangkan untuk menangani kebutuhan komputasi yang berbeda.
Algoritma-algoritma ini umumnya diklasifikasikan berdasarkan efisiensi waktu komputasinya (Time Complexity):

( 2)
1.​ Algoritma Sederhana (𝑂 𝑛 ): Biasanya digunakan untuk jumlah data yang kecil karena metodenya yang mudah
diimplementasikan namun kurang efisien untuk data besar. Contoh: Bubble Sort, Selection Sort, dan Insertion Sort.
2.​ Algoritma Efisien (𝑂(𝑛 log 𝑙𝑜𝑔 𝑛) ): Menggunakan pendekatan divide and conquer untuk memecah masalah
menjadi bagian kecil, sehingga jauh lebih cepat untuk menangani data dalam jumlah besar. Contoh: Merge Sort,
Quick Sort, dan Heap Sort.

2.1 Bubble Sort

Algortima ini merupakan salah satu algoritma pengurutan yang paling sederhana, baik dalam hal pengertian maupun
penerapannya. Ide dari algoritma bubble sort ialah mengulang proses pembandingan antara tiap-tiap elemen array dan
menukarnya apabila urutannya [Link] ini menyusun data yang diinginkan secara berurutan dengan membandingkan
elemen data yang ada dan terus diulang hingga tidak perlu dilakukan penukaran lagi.

2.1.1 Cara Kerja Algoritma Buble Sort.

Cara kerja algoritma Bubble Sort (Metode Pengurutan Gelembung) terinspirasi dari prinsip gelembung sabun yang selalu
terapung ke permukaan air karena berat jenisnya yang lebih ringan. Dalam proses pengurutan data secara menaik (ascending),
algoritma ini bekerja dengan membandingkan elemen data yang sekarang dengan elemen berikutnya secara berpasangan. Jika
ditemukan bahwa elemen saat ini memiliki nilai yang lebih besar daripada elemen berikutnya, maka posisi keduanya akan
ditukar. Mekanisme ini membuat elemen yang bernilai paling kecil seolah-olah "diapungkan" atau diangkat ke posisi paling
atas (ujung kiri array) melalui serangkaian pertukaran. Proses perbandingan dan penukaran ini dilakukan secara
berulang-ulang, dan algoritma baru akan berhenti total ketika seluruh array telah diperiksa tanpa terjadi pertukaran lagi, yang
menandakan bahwa semua data sudah terurut dengan benar.

2.1.2 Contoh Soal Iterasi Bubble Sort

Berikut ini adalah gambaran dari algoritma bubble sort:

Kita misalkan memiliki 5 angka yang akan kita simpan kedalam variabel Data (Array). Dengan masing-masing nilai sebagai
berikut:

Pass 1 (Iterasi Pertama):

Tujuan: Mendorong angka terbesar ke posisi paling kanan.

(23 vs 15) -> 23 lebih besar, TUKAR. -> [15, 23, 29, 5, 19]

(23 vs 29) -> Aman.

(29 vs 5) -> 29 lebih besar, TUKAR. -> [15, 23, 5, 29, 19]

(29 vs 19) -> 29 lebih besar, TUKAR. -> [15, 23, 5, 19, 29].

Hasil Pass 1: Angka 29 sudah aman di posisi terakhir.

Pass 2 (Iterasi Kedua): Abaikan posisi terakhir (29), kita urutkan sisanya.

(15 vs 23) -> Aman.

(23 vs 5) -> 23 lebih besar, TUKAR. -> [15, 5, 23, 19, 29]
(23 vs 19) -> 23 lebih besar, TUKAR. -> [15, 5, 19, 23, 29]

Hasil Pass 2: Angka 23 sudah aman di posisi kedua dari belakang.

Pass 3 (Iterasi Ketiga):

(15 vs 5) -> 15 lebih besar, TUKAR. -> [5, 15, 19, 23, 29]

​ ​ ​ ​

(15 vs 19) -> Aman.

Hasil Pass 3:

Data sudah terurut:

[ 5, 15, 19, 23, 29 ]:

2.1.3 Kelebihan Bubble Sort​

1. Sederhana dan Mudah Dipahami

Bubble Sort adalah salah satu algoritma pengurutan yang paling mudah dipahami dan diimplementasikan. Prosesnya yang int
uitif membuatnya ideal untuk tujuan pendidikan.

2. InPlace Sorting

Algoritma ini tidak memerlukan ruang memori tambahan yang signifikan, karena melakukan pengurutan langsung dalam arra
y yang sama. Ini menjadikannya efisien dalam penggunaan memori.
3. Stabil

Bubble Sort adalah algoritma yang stabil, artinya elemen dengan nilai yang sama akan mempertahankan urutan relatifnya sete
lah pengurutan. Ini penting dalam situasi di mana urutan awal elemen memiliki makna.

4. Mudah Mendeteksi Array yang Sudah Terurut

Jika tidak ada pertukaran yang terjadi selama satu iterasi, algoritma dapat menghentikan proses lebih awal, yang membuatnya
lebih efisien dalam kasus terbaik.

2.1.4 Kekurangan Bubble Sort

1. Kinerja Buruk untuk Dataset Besar

Kekurangan utama dari Bubble Sort adalah kompleksitas waktu yang tinggi, yaitu O(n²) dalam kasus terburuk dan rata-rata. I
ni membuatnya sangat lambat untuk dataset besar.

2. Inefisien untuk Data Hampir Terurut

Meskipun Bubble Sort dapat mendeteksi array yang sudah terurut, ia tetap melakukan perbandingan dan pertukaran yang tida
k perlu pada setiap iterasi, yang membuatnya tidak efisien dalam situasi ini.

3. Tidak Fleksibel

Algoritma ini kurang fleksibel dibandingkan dengan algoritma pengurutan lainnya dan sulit untuk dioptimalkan untuk jenis d
ata tertentu.

2.1.5 Manfaat Menggunakan Buble Sort

Salah satu manfaat menggunakan Bubble Sort (dan algoritma sorting klasik lainnya) adalah kemampuannya yang dirancang
khusus untuk bekerja secara efektif dengan struktur data array. Dalam penerapannya, algoritma ini sangat berguna untuk
membantu pembuatan aplikasi yang membutuhkan penyortiran data, seperti mengurutkan daftar harga produk dari termurah
ke termahal, menyusun ranking nilai siswa, atau mengurutkan nama secara alfabetis. Algoritma pengurutan semacam ini
merupakan bagian penting dalam pemrosesan data untuk mengelola informasi agar lebih terstruktur.

2.2 Selection Sort

Selection Sort adalah algoritma sorting sederhana yang bekerja dengan cara mencari elemen terkecil dalam array dan
menempatkannya di posisi yang sesuai. Sama seperti Bubble Sort, algoritma ini melakukan pengurutan langsung di dalam
array (in-place sorting). Namun, jika dibandingkan dengan Bubble Sort, penggunaan Selection Sort lebih efisien karena hanya
melakukan sedikit pertukaran elemen. Algoritma Selection Sort memiliki kompleksitas waktu O(n²) pada kasus terburuk
(worst case). Salah satu kelemahannya adalah algoritma ini tetap melakukan pencarian elemen terkecil meskipun sebagian
besar data sudah terurut. Sehingga, algoritma Selection Sort kurang efisien untuk mengurutkan data set besar dan lebih cocok
digunakan untuk mengurutkan data set kecil.

Algoritma Selection Sort pertama kali diperkenalkan pada tahun 1956 oleh ahli komputer J.W. Tukey. Meskipun bukan yang
paling efisien untuk dataset besar, algoritma ini dikenal karena kesederhanaannya dan mudah dipahami, sehingga sering
digunakan sebagai contoh pengantar dalam pengajaran algoritma dan struktur data.

Algoritma Selection Sort juga menggunakan nested loop for, yaitu:

1.​ loop for I , digunakan untuk membatasi jumlah iterasi yang dilakukan. variabel min_index = i untuk menyimpan
indeks elemen terkecil dalam setiap iterasi yang sedang dilakukan.
2.​ loop for j , digunakan untuk mencari elemen terkecil dari sisa daftar dan memperbarui min_index jika menemukan
elemen yang lebih kecil, sehingga elemen terkecil berada di posisi yang benar.
2.2.1 Cara Kerja Algoritma Selection Sort

Selection sort bekerja dengan prinsip dasar sebagai berikut:

1.​ Cari Elemen Terkecil: Algoritma ini pertama-tama mencari elemen terkecil dalam daftar yang belum terurut.
2.​ Tukar Elemen: Setelah menemukan elemen terkecil, algoritma menukarnya dengan elemen di posisi pertama dari
daftar yang belum terurut.
3.​ Perulangan: Langkah ini diulang untuk elemen kedua, ketiga, dan seterusnya, hingga seluruh daftar terurut.

2.2.2 Contoh Soal Selection Sort

Diketahui Array dengan [23,15,29,10,30]

Pass 1 (Mencari posisi ke-1): Kita cari angka paling kecil dari indeks 0 sampai akhir.

Pemain: 23, 15, 29, 10, 30.

Terkecil ditemukan: 10.

Aksi: Tukar 10 dengan posisi awal (23).

Hasil: [ 10, 15, 29, 23, 30 ](Angka 10 sudah dikunci/selesai).

Pass 2 (Mencari posisi ke-2): Cari terkecil dari sisa data (15, 29, 23, 30).

Terkecil ditemukan: 15.

Aksi: Karena 15 sudah berada di posisi paling depan dari sisa data, posisinya tetap (tukar dengan dirinya sendiri).​

Hasil: [ 10, 15, 29, 23, 30 ](Angka 10, 15 sudah dikunci).

Pass 3 (Mencari posisi ke-3): Cari terkecil dari sisa data (29, 23, 30).

Terkecil ditemukan: 23.

Aksi: Tukar 23 dengan posisi depan sisa data (29).

Hasil: [ 10, 15, 23, 29, 30 ](Angka 10, 15, 23 sudah dikunci).

Pass 4 (Mencari posisi ke-4): Cari terkecil dari sisa data (29, 30).

Terkecil ditemukan: 29.

Aksi: Posisi tetap.

Hasil Akhirnya Ialah : [ 10, 15, 23, 29, 30 ]

2.2.3 Kelebihan Selection Sort

1. Sederhana dan Mudah Dipahami: Algoritma selection sort sangat mudah dipahami dan diimplementasikan. Ini
membuatnya cocok untuk digunakan dalam konteks pendidikan dan sebagai dasar untuk memahami algoritma pengurutan
yang lebih kompleks.

2. Tidak Membutuhkan Memori Tambahan: Algoritma ini bekerja di tempat, artinya tidak memerlukan memori tambahan
selain daftar yang akan diurutkan. Ini menjadikannya algoritma dengan kompleksitas ruang O(1).

2.2.4 Kelemahan Selection Sort

1. Tidak Efisien untuk Daftar Besar: Dengan kompleksitas waktu O(n^2), selection sort menjadi tidak efisien untuk daftar
yang besar. Algoritma ini akan memerlukan waktu yang cukup lama untuk mengurutkan daftar dengan banyak elemen.

2. Tidak Stabil: Selection sort bukanlah algoritma yang stabil, yang berarti elemen dengan nilai yang sama bisa saja tidak
mempertahankan urutan relatif mereka setelah pengurutan.

2.2.5 Manfaat Selection Sort

Salah satu manfaat menggunakan Selection Sort terletak pada kesederhanaannya yang membuat algoritma ini mudah
dipahami serta mudah untuk diimplementasikan. Algoritma ini juga memiliki keunggulan dalam efisiensi sumber daya karena
tidak memerlukan memori tambahan yang besar saat dijalankan. Selain itu, Selection Sort memiliki kelebihan spesifik berupa
jumlah operasi pertukaran (swap) yang sangat minimal, yaitu maksimal sebanyak n-1 kali. Karakteristik ini menjadikannya
pilihan yang berguna terutama dalam skenario di mana operasi pertukaran data dianggap sangat "mahal" dalam hal waktu
komputasi.

2.3 Insertion Sort

Insertion Sort adalah algoritma sorting sederhana yang bekerja dengan cara menyusun elemen satu per satu ke dalam array
hingga semua elemen dalam array terurut. Walaupun elemen array ditambahkan satu persatu, pengurutannya tetap dilakukan
langsung di dalam array (in-place sorting). Dalam kasus terbaik (Best Case), Insertion Sort memiliki kompleksitas
waktu O(n), yaitu ketika algoritma ini mengurutkan data yang hampir terurut atau jumlah data yang diurutkan sedikit.
Namun, dalam beberapa kasus, Insertion Sort memiliki kompleksitas waktu O(n²), terutama jika banyak elemen yang berada
di posisi yang jauh dari urutan yang seharusnya, sehingga akan menyebabkan banyak pergeseran.

Algoritma Insertion Sort menggunakan nested loop berikut:

1.​ loop for digunakan untuk menentukan iterasi berjalan sebanyak n kali, dimana n adalah banyaknya elemen dalam
daftar. Loop ini bertugas untuk menyisipkan/memasukkan elemen ke dalam daftar yang sudah terurut.
2.​ loop while digunakan untuk menggeser elemen-elemen yang lebih besar ke bagian kanan daftar yang sudah terurut.
Proses ini terus dilakukan sampai ditemukan posisi yang sesuai untuk menyisipkan elemen key. Setelah ditemukan
posisi yang sesuai, nilai key akan dimasukkan ke dalam daftar pada posisi tersebut.

2.3.1 Cara Kerja Inserrtion Sort

1. Membuat Subarray Terurut: Algoritma dimulai dengan menganggap elemen pertama sebagai subarray terurut.

2. Menambahkan Elemen: Elemen berikutnya dalam array diambil dan dibandingkan dengan elemen-elemen di subarray
terurut.

3. Menyisipkan Elemen: Elemen diambil diposisikan pada tempat yang tepat di subarray terurut sehingga subarray tetap
terurut.

4. Mengulang Proses: Langkah 2 dan 3 diulang untuk semua elemen yang tersisa dalam array.

2.3.2 Contoh Soal Iterasi Insertion Sort

Diketahui Array dengan [5,2,4,6,1]

Pass 1 (Fokus ke angka 2):

Kita pegang angka 2 (key). mengapa? Karena sebelah kiri dari angka 5 tidak ada

Bandingkan dengan kirinya (5).

Apakah 5 > 2? Ya. GESER 5 ke kanan.

Ada lagi di kirinya? Tidak.

Sisipkan 2 di ruang kosong.

Hasil: [ 2, 5, 4, 6, 1 ]
Pass 2 (Fokus ke angka 4):

Kita pegang angka 4 (key).

Bandingkan dengan kirinya (5). 5 > 4? Ya. GESER 5.

Bandingkan lagi dengan kirinya (2). 2 > 4? Tidak. Berhenti.

Sisipkan 4 di depan angka 2.

Hasil: [ 2, 4, 5, 6, 1 ]

Pass 3 (Fokus ke angka 6):

Kita pegang angka 6 (key).

Bandingkan dengan kirinya (5). 5 > 6? Tidak.

Karena kirinya lebih kecil, berarti posisi 6 sudah pas. Tidak ada geser.

Hasil: [ 2, 4, 5, 6, 1 ]

Pass 4 (Fokus ke angka 1):

Kita pegang angka 1 (key).

Bandingkan dengan kirinya (6). 6 > 1? Ya. GESER 6.

Bandingkan dengan kirinya (5). 5 > 1? Ya. GESER 5.

Bandingkan dengan kirinya (4). 4 > 1? Ya. GESER 4.

Bandingkan dengan kirinya (2). 2 > 1? Ya. GESER 2.

Ruang kosong di paling depan. Sisipkan 1.

Hasil Akhirnya Ialah : [ 1, 2, 4, 5, 6 ]

Selesai. Data sudah terurut.

2.3.3 Kelebihan Insertion Sort

1. Sederhana dan Mudah Diterapkan: Insertion Sort merupakan algoritma yang mudah dipahami dan diterapkan, bahkan
untuk pemrogram pemula.

2. Efisien untuk Array Kecil: Algoritma ini sangat efisien untuk array kecil dan array yang hampir terurut.

3. Stabil: Insertion Sort merupakan algoritma yang stabil, yang berarti mempertahankan urutan relatif elemen-elemen yang
memiliki nilai yang sama.

4. Memori Rendah: Algoritma ini hanya membutuhkan ruang tambahan yang sangat kecil, membuatnya cocok untuk aplikasi
dengan memori terbatas.

2.3.4 Kekurangan Insertion Sort

1. Kurang Efisien untuk Array Besar: Insertion Sort memiliki kompleksitas waktu O(n²) untuk kasus terburuk, membuatnya
kurang efisien untuk array besar.

2. Performa Buruk untuk Array yang Tidak Terurut: Jika array sangat tidak terurut, Insertion Sort akan membutuhkan waktu
yang lama untuk mengurutkannya.

3. Tidak Cocok untuk Array Terbesar: Algoritma ini tidak cocok untuk mengurutkan array yang sangat besar karena
performanya yang buruk.

kapan kita dapat menggunakan algoritma insertion Sort? Ketika kita bekerja dengan kumpulan data atau array yang
berukuran kecil. Kinerjanya akan semakin optimal dan melakukan pekerjaan dengan sangat baik apabila data yang diolah
kondisinya sudah hampir terurut. Selain itu, algoritma ini juga menjadi opsi terbaik jika kita membutuhkan kestabilan dalam
hasil pengurutan. Tidak hanya itu, Insertion Sort sangat bersahabat bagi aplikasi yang berjalan di lingkungan dengan memori
terbatas, karena ia hanya membutuhkan ruang tambahan yang sangat kecil untuk dapat beroperasi.

2.3.5 Manfaat Insertion Sort

Salah satu manfaat algoritma Insertion Sort ialah terletak pada kesederhanaannya yang membuat algoritma ini mudah
dipahami dan diimplementasikan. Algoritma ini bekerja sangat efisien ketika diterapkan pada array yang berukuran kecil
serta bersifat adaptif, yang artinya kinerjanya akan semakin cepat jika data yang diolah sudah dalam kondisi hampir terurut.
Selain itu, Insertion Sort merupakan pilihan yang tepat jika stabilitas pengurutan diperlukan karena mampu mempertahankan
urutan elemen dengan nilai yang sama, dan sangat hemat memori (in-place) karena hanya membutuhkan sedikit ruang
tambahan saat beroperasi. Algoritma ini juga memiliki keunggulan online, yaitu mampu mengurutkan data secara langsung
pada saat data tersebut diterima.

2.4 Merge Sort

Merge Sort adalah algoritma sorting kompleks yang menggunakan metode divide and conquer. Cara kerja algoritma ini
adalah dengan membagi array menjadi 2 bagian yang lebih kecil, lalu masing-masing bagian diurutkan secara terpisah.
Kemudian, kedua bagian yang sudah terurut digabungkan kembali menjadi satu dengan urutan yang benar. Algoritma Merge
Sort memiliki kompleksitas waktu O(n log n) dalam semua kasus, baik best case, average case, maupun worst case. Artinya,
algoritma ini selalu memiliki performa yang optimal tanpa dipengaruhi oleh jumlah data atau apakah sebagian data sudah
terurut sebelumnya. Namun, proses penggabungan (merging) dalam algoritma ini membutuhkan tambahan memori dan
langkah-langkah tambahan (overhead), yang membuatnya kurang efisien dalam pengurutan data kecil.

Algoritma Merge Sort bekerja dengan membagi daftar menjadi 2 bagian, left_half dan right_half, hingga masing-masing
bagian tersisa 1 elemen. Algoritma ini menggunakan proses rekursi untuk mengurutkan elemen di masing-masing bagiannya.
Seteleh setiap bagian memiliki elemen yang sudah terurut, kedua bagian tersbeut akan digabungkan kembali melalui proses
merging.

Proses ini menggunakan 3 loop while yang berbeda, antara lain:

1.​ while i < len(left_half) and j < len(right_half) , digunakan untuk membandingkan setiap elemen dari kedua bagian
satu per satu, kemudian elemen-elemen tersebut akan disusun kembali dalam urutan yang benar.
2.​ while i < len(left_half) dan while j < len(right_half) , digunakan untuk memastikan sisa elemen di masing-masing
bagian yang belum dimasukkan akan tetap ditambahkan ke daftar utama arr.

2.4.1 Trik Pemecahan Pada Merge Sort

Trik pemecahan pada Merge Sort adalah langkah-langkah utama yang digunakan untuk membagi dan mengurutkan data
secara terpisah sebelum dilakukan penggabungan kembali. Berikut adalah penjelasan perpoin secara panjang mengenai trik
pemecahan pada Merge Sort:

1. “Divide” atau Pemisahan

Langkah pertama dalam algoritma Merge Sort adalah membagi daftar data yang akan diurutkan menjadi dua bagian hampir
sama ukurannya. Hal ini dilakukan dengan menentukan elemen tengah dari daftar data sebagai titik pembagiannya.

Proses ini berlangsung secara rekursif, artinya kedua bagian yang baru terbentuk juga akan dibagi menjadi bagian-bagian
lebih kecil. Pembagian ini terus berlanjut hingga setiap bagian hanya memiliki satu elemen atau tidak memiliki elemen sama
sekali (jika daftar datanya kosong).

Pembagian yang berulang ini akan menciptakan pohon rekursi, di mana setiap simpul mewakili proses pengurutan pada
bagian-bagian data yang berbeda.

2. “Conquer” atau Penaklukkan

Setelah proses pembagian berakhir, langkah selanjutnya adalah mengurutkan masing-masing bagian secara terpisah. Ini
dilakukan dengan membandingkan elemen-elemen dalam setiap bagian dan menyusunnya dalam urutan yang benar.

Bagian-bagian yang sudah diurutkan ini akan membentuk daftar data yang lebih kecil, namun sudah terurut dengan benar
sesuai aturan algoritma Merge Sort.

3. “Merge” atau Penggabungan

Setelah bagian-bagian data terurut, langkah selanjutnya adalah menggabungkannya kembali menjadi satu kesatuan dengan
urutan yang benar. Inilah sebabnya mengapa algoritma ini disebut “Merge Sort”.
Proses penggabungan dimulai dengan membandingkan elemen pertama dari masing-masing bagian. Elemen yang lebih kecil
ditempatkan terlebih dahulu dalam daftar hasil penggabungan.

Selanjutnya, elemen yang lebih kecil tadi akan dihapus dari bagian asalnya dan akan dibandingkan lagi dengan elemen
pertama pada bagian yang sama atau berbeda. Proses ini berlanjut hingga semua elemen dari kedua bagian tergabung dengan
urutan yang tepat dalam daftar hasil penggabungan.

Jika ada elemen yang tersisa di salah satu bagian setelah proses penggabungan selesai, elemen-elemen tersebut akan langsung
ditambahkan ke daftar hasil karena kita sudah mengetahui bahwa elemen-elemen tersebut sudah dalam urutan yang benar.

2.4.2 Contoh Soal Iterasi Merge Sort

Misalkan kita punya array: [ 38, 27, 43, 10 ]

FASE 1: DIVIDE (Memecah)

Kita belah array ini menjadi dua bagian terus menerus sampai habis.

Awal: [ 38, 27, 43, 10 ]

Belah jadi dua: [ 38, 27 ] dan [ 43, 10 ]

Belah lagi: [ 38 ], [ 27 ], [ 43 ], [ 10 ](Sekarang kita punya 4 potongan terpisah. Karena isinya cuma 1 angka, mereka
dianggap "sudah urut" secara individu).

FASE 2: MERGE (Menggabungkan & Mengurutkan)

Sekarang kita gabungkan kembali potongan-potongan tersebut sambil diurutkan.

Langkah A (Gabung Level Bawah):

Gabungkan [38] vs [27].

Cek: Mana lebih kecil? 27.

Hasil: [ 27, 38 ]

Gabungkan [43] vs [10].

Cek: Mana lebih kecil? 10.

Hasil: [ 10, 43 ]

Langkah B (Gabung Level Atas/Final):

Sekarang kita punya dua kelompok yang sudah urut internalnya:

Kelompok Kiri: [ 27, 38 ] | Kelompok Kanan: [ 10, 43 ]

Proses Merging (Komparasi Kepala vs Kepala):

Bandingkan kepala kiri (27) vs kepala kanan (10).

10 lebih kecil. Ambil 10

Hasil sementara: [ 10 ]

Bandingkan kepala kiri (27) vs kepala kanan selanjutnya (43).

27 lebih kecil. Ambil 27.

Hasil sementara: [ 10, 27 ]

Bandingkan kepala kiri selanjutnya (38) vs kepala kanan (43).

38 lebih kecil. Ambil 38.

Hasil sementara: [ 10, 27, 38 ]

Sisa di kanan tinggal 43. Masukkan saja.

Hasil Akhirnya Ialah : [ 10, 27, 38, 43 ]

Selesai. Data terurut.

2.4.3 Kelebihan Algoritma Merge Sort

Algoritma Merge Sort memiliki beberapa kelebihan yang membuatnya menjadi pilihan yang baik dalam mengurutkan data.
Berikut adalah beberapa kelebihan Algoritma Merge Sort:

1. Stabilitas

Merge Sort adalah algoritma pengurutan yang stabil, artinya jika ada dua elemen dengan nilai yang sama, maka urutan relatif
kedua elemen tersebut tetap dipertahankan setelah proses pengurutan. Hal ini penting dalam beberapa kasus di mana kita
ingin mempertahankan urutan asli elemen-elemen yang memiliki kunci atau atribut yang sama.
2. Efisiensi pada Data Besar

Salah satu kelebihan utama Merge Sort adalah kinerja waktu yang baik pada data dengan ukuran besar. Karena algoritma ini
menggunakan pendekatan “divide and conquer”, di mana data dibagi menjadi bagian-bagian kecil yang diurutkan terlebih
dahulu sebelum digabungkan kembali, kompleksitas waktunya adalah O(n log n). Hal ini membuatnya lebih efisien
dibandingkan beberapa metode pengurutan lainnya, terutama pada data dalam skala besar.

3. Penggunaan Memori

Meskipun Merge Sort menggunakan pendekatan rekursif dan membagi data menjadi beberapa bagian, algoritma ini dapat
diimplementasikan dengan penggunaan memori yang moderat.

Selain itu, Merge Sort tidak memerlukan memori tambahan (in-place), kecuali pada tahap penggabungan. Hal ini memastikan
bahwa algoritma ini tidak akan menghabiskan terlalu banyak memori bahkan untuk data dengan ukuran yang sangat besar.

4. Kasus Terburuk yang Konsisten

Beberapa algoritma pengurutan, seperti Quick Sort, memiliki kinerja yang sangat baik pada sebagian besar kasus, namun bisa
memiliki kasus terburuk yang memiliki kompleksitas waktu yang sangat tinggi.

Namun, Merge Sort memiliki kinerja yang konsisten dalam berbagai kasus dan tidak bergantung pada pilihan elemen acak
(seperti pada Quick Sort). Oleh karena itu, algoritma ini lebih dapat diandalkan dan meminimalkan risiko terjadinya kasus
terburuk yang menyebabkan penurunan performa.

5. Pengurutan Linked List

Merge Sort juga dapat digunakan untuk mengurutkan Linked List dengan efisien tanpa perlu memodifikasi struktur
data aslinya. Karena algoritma ini hanya memerlukan penggabungan simpul-simpul dalam urutan yang benar, Merge Sort
menjadi pilihan yang baik untuk mengurutkan Linked List dengan kinerja yang baik.
Kekurangan Algoritma Merge Sort

2.4.4 Kelemahan Algoritma Merge Sort

Meskipun Algoritma Merge Sort memiliki banyak kelebihan, seperti yang telah dijelaskan sebelumnya, namun algoritma ini
juga memiliki beberapa kekurangan yang perlu dipertimbangkan. Berikut adalah beberapa kekurangan Algoritma Merge Sort:

1. Penggunaan Memori Tambahan

Salah satu kelemahan utama Merge Sort adalah penggunaan memori tambahan untuk menyimpan sementara bagian-bagian
data selama proses penggabungan (merge). Saat data dipecah menjadi bagian-bagian kecil, diperlukan tempat penyimpanan
untuk setiap bagian tersebut, yang mempengaruhi penggunaan memori secara keseluruhan. Algoritma ini memerlukan ruang
memori tambahan yang sebanding dengan ukuran data yang akan diurutkan.

2. Kompleksitas Penggabungan

Tahap penggabungan (merge) pada Algoritma Merge Sort memerlukan lebih banyak operasi pembandingan dan penyalinan
elemen. Meskipun algoritma ini efisien dalam hal kinerja waktu, namun proses penggabungan ini bisa menjadi lebih
kompleks dan memakan waktu jika tidak diimplementasikan secara efisien.

3. Pengurutan Data Terkini

Merge Sort merupakan algoritma pengurutan non-inplace, artinya ia menghasilkan urutan data baru tanpa mengubah data asli.
Hal ini bisa menjadi kelemahan terutama jika data asli besar dan harus diurutkan secara langsung. Pengurutan tanpa
modifikasi data asli memerlukan alokasi memori tambahan untuk hasil pengurutan.

4. Tidak Optimal untuk Data Kecil

Meskipun Merge Sort memiliki kinerja yang sangat baik pada data dengan ukuran besar, algoritma ini mungkin tidak optimal
untuk data yang relatif kecil. Pendekatan rekursif dan penggabungan data kecil bisa mengakibatkan sedikit overhead yang
menyebabkan algoritma ini tidak seefisien saat mengurutkan data kecil.

5. Tidak Stabil pada Beberapa Implementasi

Walaupun Merge Sort secara teori adalah algoritma pengurutan stabil, namun implementasinya dapat mempengaruhi
stabilitasnya. Beberapa implementasi Merge Sort bisa kehilangan stabilitas jika tidak diatur dengan benar saat melakukan
penggabungan.

2.4.5 Manfaat Merge Sort

Salah satu manfaat utama menggunakan algoritma Merge Sort adalah keandalan performanya yang sangat konsisten dengan
kompleksitas waktu O(n log n) pada semua situasi, baik itu kasus terbaik, rata-rata, maupun terburuk. Hal ini menjadikannya
pilihan yang sangat efisien untuk mengolah data dalam jumlah besar. Selain itu, Merge Sort sangat cocok diterapkan pada
struktur data Linked List dan memiliki sifat stabil (stable sort), yang artinya mampu menjaga urutan asli dari elemen-elemen
yang bernilai sama. Keunggulan lainnya adalah algoritma ini mendukung paralelisasi, sehingga proses pengurutan dapat
dibagi-bagi dan dijalankan secara bersamaan untuk mempercepat kinerja.

2.5 Quick Sort

Quick Sort adalah algoritma sorting berbasis divide and conquer dan dikenal sebagai salah satu algoritma pengurutan in-place
yang paling efisien. Algoritma ini bekerja dengan memilih salah satu elemen sebagai pivot. Pivot ini akan digunakan sebagai
patokan untuk membagi elemen menjadi dua kelompok, yaitu kelompok elemen yang lebih kecil dari pivot dan kelompok
elemen yang lebih besar dari pivot. Proses ini terus berulang hingga seluruh elemen berada di posisi dengan urutan yang
benar.

Pemilihan pivot dalam algoritma ini harus dipertimbangkan dengan baik. Jika tidak, maka akan terjadi inefisiensi yang
menyebabkan kompleksitas waktu memburuk menjadi O(n²). Hal ini dapat dihindari dengan menggunakan teknik randomized
pivot atau median-of-three. Dalam praktiknya, Quick Sort mampu melakukan pengurutan lebih cepat dari Merge Sort,
meskipun keduanya sama-sama sama-sama memiliki kompleksitas waktu O(n log n) dalam kasus terbaiknya (best case).

Algoritma quick sort akan mencari dan memilih pivot secara rekursif hingga setiap subdaftar tersisa satu elemen sebagai
pivot. Pemilihan pivot dilakukan untuk membagi daftar menjadi tiga bagian, yaitu:

1.​ left: elemen yang lebih kecil dari pivot

2.​ middle: elemen yang sama dengan pivot
3.​ right: elemen yang lebih besar dari pivot

Proses ini terus berulang hingga seluruh elemen dalam masing-masing bagian berada di posisi dengan urutan yang benar.
Setelah itu, ketiga bagian tersebut akan digabungkan kembali menjadi satu daftar yang telah terurut.

2.5.1 Tips Pemilihan Pivot.

Dalam algoritma quick sort, pemilihan pivot adalah hal yang menentukan apakah algoritma quick sort tersebut akan
memberikan performa terbaik atau terburuk. Berikut beberapa cara pemilihan pivot :

1. Pivot adalah elemen pertama, elemen terakhir, atau elemen tengah tabel. Cara ini hanya bagus jika elemen tabel tersusun
secara acak, tetapi tidak bagus jika elemen tabel semula sudah terurut. Misalnya, jika elemen tabel semula menurun, maka
semua elemen tabel akan terkumpul di upatabel kanan.

2. Pivot dipilih secara acak dari salah satu elemen tabel. Cara ini baik, tetapi mahal, sebab memerlukan biaya (cost) untuk
pembangkitan prosedur acak. Lagi pula, itu tidak mengurangi kompleksitas waktu algoritma.

3. Pivot adalah elemen median tabel. Cara ini paling bagus, karena hasil partisi menghasilkan dua bagian tabel yang
berukuran seimbang (masing masing ≈ n/2 elemen). Cara ini memberikan kompleksitas waktu yang minimum. Masalahnya,
mencari median dari elemen tabel yang belum terurut adalah persoalan tersendiri. Algoritma Quick Sort terdiri dari dua
prosedur, yaitu prosedur PARTISI dan prosedur QUICKSORT.

2.5.2 Contoh Soal Iterasi Quick Sort

TAHAP 1: Partisi Seluruh Array

Data: [ 10, 80, 30, 90, 40 ]

Kita pilih 40 (elemen terakhir) sebagai Pivot.

Tugas: Pindahkan angka < 40 ke kiri, > 40 ke kanan.

Cek 10: Lebih kecil dari 40? Ya. (Biarkan di kiri).

Cek 80: Lebih kecil dari 40? Tidak. (Tahan, dia harus ke kanan nanti).

Cek 30: Lebih kecil dari 40? Ya.

Aksi: Karena tadi ada 80 yang "menghalangi", tukar 30 dengan 80.

Array jadi: [ 10, 30, 80, 90, 40 ]

Cek 90: Lebih kecil dari 40? Tidak.

Finalisasi Pivot: Masukkan Pivot (40) di antara batas kecil dan besar (tukar dengan 80).

Hasil Tahap 1: [ 10, 30, **40**, 90, 80 ]

Status: Angka 40 sudah paten di posisinya. Sekarang kita punya dua sayap:

Sayap Kiri: [ 10, 30 ]

Sayap Kanan: [ 90, 80 ]

TAHAP 2: Partisi Sayap Kiri ([ 10, 30 ])

Kita pilih 30 (elemen terakhir sub-array) sebagai Pivot.

Cek 10: Lebih kecil dari 30? Ya. (Biarkan).

Finalisasi Pivot: 30 sudah berada di posisi yang benar setelah 10.

Hasil Tahap 2: [ 10, **30** ]

Status: Sayap kiri sudah beres.

TAHAP 3: Partisi Sayap Kanan ([ 90, 80 ])

Kita pilih 80 (elemen terakhir sub-array) sebagai Pivot.

Cek 90: Lebih kecil dari 80? Tidak. (Tahan).

Finalisasi Pivot: Pivot (80) harus berada sebelum angka besar (90). Maka tukar 80 dengan 90.

Hasil Tahap 3: [ **80**, 90 ]

Status: Sayap kanan sudah beres.

Hasil Akhirnya Ialah : Gabungkan semua posisi yang sudah paten:[ 10, 30, 40, 80, 90 ] -> Terurut.

2.5.3 Keunggulan Quick sort

1. Secara umum memiliki kompleksitas O(n log n).

2. Algoritmanya sederhana dan mudah diterapkan pada berbagai bahasa pemrograman dan arsitektur mesin secara efisien.

3. Dalam prakteknya adalah yang tercepat dari berbagai algoritma pengurutan dengan perbandingan, seperti mergesort dan
heapsort.

4. Melakukan proses langsung pada input (in-place) dengan sedikit tambahan memori.

5. Bekerja dengan baik pada berbagai jenis input data (seperti angka dan karakter).

2.5.4 Kekurangan Quick short

1. Sedikit kesalahan dalam penulisan program membuatnya bekerja tidak beraturan (hasilnya tidak benar atau tidak pernah
selesai).

2. Memiliki ketergantungan terhadap data yang dimasukkan, yang dalam kasus terburuk memiliki kompleksitas O(n2).

3. Secara umum bersifat tidak stable, yaitu mengubah urutan input dalam hasil akhirnya (dalam hal inputnya bernilai sama).
4. Pada penerapan secara rekursif (memanggil dirinya sendiri) bila terjadi kasus terburuk dapat menghabiskan stack dan
memacetkan program.

5. Pada bahasa pemrograman, quicksort ada dalam pustaka stdlib.h untuk bahasa C, dan class TList dan TStringList dalam
Delphi (Object Pascal) maupun FreePascal.

2.5.5 Manfaat Quick Sort

Salah satu manfaat utama menggunakan algoritma Quick Sort adalah efisiensinya yang sangat tinggi, di mana algoritma ini
sering dianggap sebagai salah satu metode pengurutan tercepat dalam praktiknya dengan kompleksitas waktu rata-rata O(n
log n). Selain kinerjanya yang cepat, Quick Sort juga sangat hemat memori karena bekerja secara in-place, yang berarti ia
tidak membutuhkan ruang tambahan yang besar untuk menampung data sementara seperti halnya Merge Sort. Keunggulan
lainnya adalah algoritma ini memiliki cache locality yang baik, sehingga sangat cocok dan efisien saat dijalankan pada
arsitektur komputer modern.

2.6 Shell Sort

Shell Sort adalah algoritma pengurutan yang merupakan pengembangan atau optimasi dari Insertion Sort. Algoritma ini
pertama kali diperkenalkan oleh Donald Shell pada tahun 1959. Jika Insertion Sort bekerja dengan membandingkan elemen
yang bersebelahan (jarak=1), Shell Sort bekerja dengan membandingkan elemen-elemen yang memiliki jarak (gap) tertentu.
Tujuannya adalah untuk memindahkan elemen yang "salah posisi" agar bisa melompat jauh ke posisi yang lebih mendekati
posisi akhirnya, sehingga mengurangi jumlah pergeseran data yang diperlukan di tahap akhir.

Masalah utama pada Insertion Sort biasa adalah jika elemen terkecil berada di posisi paling belakang (ujung kanan), butuh
banyak sekali pergeseran untuk memindahkannya ke depan.

Shell Sort mengatasi ini dengan cara:

1. Menentukan Gap (Interval): Data dibagi menjadi sub-kelompok berdasarkan jarak indeks tertentu (misalnya jarak 4, lalu 2,
lalu 1).

2. Sorting Sub-kelompok: Elemen-elemen yang berjarak sama dibandingkan dan ditukar jika urutannya salah.

3. Memperkecil Gap: Proses diulang dengan jarak yang semakin kecil.

4. Final Step: Langkah terakhir selalu dilakukan dengan Gap = 1. Pada tahap ini, Shell Sort menjadi sama dengan Insertion
Sort biasa, tetapi karena data sudah "hampir terurut" (almost sorted) akibat langkah sebelumnya, prosesnya menjadi sangat
cepat.

2.6.1 Cara Kerja Penyortiran Shell

1. Dalam jenis penyisipan, elemen dipindahkan hanya satu posisi pada satu waktu. Sebaliknya, shell sort membagi array
menjadi bagian-bagian yang lebih kecil berdasarkan nilai interval dan mengeksekusi penyisipan pada bagian-bagian tersebut.

2. Secara bertahap, nilai interval berkurang, dan ukuran potongan yang terbagi bertambah. Karena potongan-potongan
tersebut telah disortir satu per satu sebelumnya, penggabungan potongan-potongan tersebut memerlukan langkah yang lebih
sedikit dibandingkan sebelumnya jenis penyisipan.

2.6.2 Contoh Soal Iterasi Shell Sort

Langkah 1: Gap = 4 (N/2) Kita bandingkan elemen dengan jarak 4

Indeks 0 & 4: (23 vs 31) -> Aman

Indeks 1 & 5: (29 vs 7) -> TUKAR karena 7 lebih kecil dari 29

Indeks 2 & 6: (15 vs 9) -> TUKAR karena 9 ebih kecil daripada 15

Indeks 3 & 7: (19 vs 5) -> TUKAR karena 5 lebih kecil dari 19

Hasil sementara: [ 23, 7, 9, 5, 31, 29, 15, 19 ](Perhatikan angka kecil seperti 5 dan 7 sudah "melompat" jauh ke depan)

Langkah 2: Gap = 2 Bandingkan elemen berjarak 2, lalu urutkan

Indeks 1 & 3: (23 vs 9) -> TUKAR

Indeks 2 & 4: (7 vs 5) -> TUKAR

Indeks 3 & 5: (23 vs 31) -> TIDAK

Indeks 4 & 6: (5 vs 29) -> TIDAK

Indeks 5 & 7: (31 vs 15) -> TUKAR

Indeks 6 & 8: (29 vs 19) -> TUKAR

Kita ulang lagi lihat indeks awalnya

Indeks 1 & 3: (9 vs 23) -> TIDAK

Indeks 2 & 4: (7 vs 5) -> TUKAR

Indeks 3 & 5: (23 vs 15) -> TUKAR

Indeks 4 & 6: (7 vs 19) -> TIDAK

Indeks 5 & 7: (23 vs 31) -> TIDAK

Indeks 6 & 8: (19 vs 29) ->TIDAK​

Hasil sementara: [ 9, 5, 15, 7, 23, 19, 31, 29 ]

Langkah 3: Gap = 1 Lakukan Insertion Sort biasa. Karena data sudah hampir urut, pergeserannya sedikit.

Indeks 1 & 2: (9 vs 5) -> TUKAR

Indeks 2 & 3: (9 vs 15) -> TIDAK

Indeks 3 & 4: (15 vs 7) -> TUKAR

Indeks 4 & 5: (15 vs 23) -> TUKAR

Indeks 5 & 6: (23 vs 219) -> TUKAR

Indeks 6 & 7: (23 vs 31) -> TIDAK

Indeks 7 & 8: (31 vs 29) -> TUKAR

Kita ulang lagi lihat indeks awalnya

Indeks 1 & 2: (5 vs 9) -> TIDAK

Indeks 2 & 3: (9 vs 7) -> TUKAR

Indeks 3 & 4: (9 vs 5) -> TIDAK

Indeks 4 & 5: (15 vs 19) -> TIDAK

Indeks 5 & 6: (19 vs 23) -> TIDAK

Indeks 6 & 7: (23 vs 29) -> TIDAK

Indeks 7 & 8: (29 vs 31) -> TIDAK

Hasil Akhir Ialah : [ 5, 7, 9, 15, 19, 23, 29, 31 ]

2.6.3 Kelebihan Shell Sort

1. Jauh Lebih Cepat dari Algoritma $O(n^2)$ Biasa

Dibandingkan dengan Bubble Sort atau Insertion Sort murni, Shell Sort jauh lebih efisien untuk jumlah data menengah
(misalnya 500 - 5.000 data). Alasannya: Shell Sort memungkinkan pertukaran data jarak jauh (long-distance swapping). Ini
memecahkan masalah utama Insertion Sort di mana angka kecil di ujung kanan harus "bergeser" satu per satu ke ujung kiri.

2. Efisien Memori (In-Place)

Sama seperti saudaranya (Insertion Sort), Shell Sort tidak membutuhkan memori tambahan yang signifikan (Kompleksitas
memori $O(1)$). Ini berbeda dengan Merge Sort yang membutuhkan array tambahan untuk menampung data sementara.

3. Algoritma Adaptif

Jika data input sudah "hampir terurut" (partially sorted), Shell Sort akan bekerja sangat cepat. Semakin data mendekati urut,
semakin sedikit kerja yang dilakukan algoritma ini.

4. Mudah Diimplementasikan

Meskipun logikanya sedikit lebih maju dari Insertion Sort, kode programnya masih relatif pendek dan sederhana
dibandingkan Quick Sort atau Heap Sort. Tidak memerlukan konsep rekursi yang rumit (tidak membebani stack memori).

2.6.4 Kekurangan Shell Sort

1. Tidak Stabil (Unstable Sort)

Ini adalah kelemahan utamanya dibanding Insertion Sort. Artinya: Jika ada dua angka yang nilainya sama (misal ada dua
angka 5, yaitu 5a dan 5b), urutan relatif mereka bisa berubah setelah di-sort (bisa jadi 5b dulu baru 5a). Hal ini terjadi karena
proses lompat jarak jauh (gap) tadi.

2. Sangat Bergantung pada Urutan Gap (Gap Sequence)

Kinerja Shell Sort sangat ditentukan oleh rumus jarak yang dipakai (apakah dibagi 2 terus menerus, atau pakai rumus Knuth,
Hibbard, dll). Jika salah memilih urutan gap, kinerjanya bisa memburuk mendekati $O(n^2)$. Analisis kompleksitas
waktunya sangat rumit secara matematis karena variasi gap ini.

3. Tidak Efisien untuk Data Sangat Besar

Untuk data berjumlah masif (misalnya jutaan data), Shell Sort masih kalah cepat dibandingkan algoritma $O(n \log n)$ sejati
seperti Quick Sort atau Merge Sort.

2.6.5 Manfaat Shell Sort

Salah satu manfaat utama algoritma Shell Sort adalah sebagai bentuk optimasi atau perbaikan dari Insertion Sort yang
dirancang untuk mengatasi kelemahan pergeseran data, sehingga algoritma ini menjadi sangat efisien untuk mengurutkan data
dengan ukuran menengah. Metode ini bekerja dengan membandingkan elemen-elemen yang terpisah oleh jarak (gap) tertentu,
yang memungkinkan elemen data bergerak menuju posisi akhirnya dengan langkah yang lebih besar dan cepat dibandingkan
metode konvensional. Selain kinerjanya yang lebih cepat pada ukuran data tertentu, Shell Sort juga memiliki keunggulan
berupa penggunaan memori yang hemat (in-place), karena tidak memerlukan alokasi ruang tambahan yang signifikan saat
proses pengurutan berlangsung.

KESIMPULAN YANG DAPAT DI AMBIL DARI MODUL PEMBELAJARAN INI :

​ ​ ​ ​ ​ KAPAN DIGUNAKAN
ALGORITMA METODE KOMPLEKSITAS KOMPLEKSITAS SIFAT
DASAR WAKTU RUANG (BEST USE CASE)
2
𝑂(𝑛 )
BUBLE SORT Penukaran​ 𝑂(1)in-place Stabil Digunakan untuk pembelajaran
(Exchange) konsep dasar sorting atau data
sangat kecil. Kurang efisien untuk
data besar.
2
𝑂(𝑛 )
SELECTION Pemilihan 𝑂(1)in-place Tidak Digunakan ketika memori sangat
SORT (Selection) Stabil terbatas dan ingin meminimalkan
jumlah operasi penukaran (swap).
2
𝑂(𝑛 )
INSERTION Penyisipan 𝑂(1)in-place Stabil Sangat efisien untuk array kecil
SORT (Insertion) atau data yang hampir terurut
sepenuhnya.
𝑂(𝑛 log 𝑙𝑜𝑔 𝑛 )
MERGE SORT Divide & 𝑂(𝑛) Butuh Stabil Sangat baik untuk data jumlah
Conquer memori lebih besar dan struktur data Linked
List karena performanya stabil di
semua kasus.
𝑂(𝑛 log 𝑙𝑜𝑔 𝑛 ) 𝑂(log 𝑙𝑜𝑔 𝑛 )
QUICK SORT Divide & Tidak Sering dianggap algoritma tercepat
Conquer Stabil untuk general purpose pada
arsitektur modern
𝑂(𝑛 log 𝑙𝑜𝑔 𝑛 ) 𝑎𝑡𝑎𝑢
SHELL SORT Penyisipan 𝑂(1)in-place Tidak Optimasi dari Insertion Sort untuk
(Insertion) 2 Stabil mengurangi pergeseran data; cocok
𝑂(𝑛 ) tergantung
dengan gap untuk data ukuran menengah.
gap

Tabel 1. Kesimpulan
Pada Tabel 1. Diatas Algoritma sorting dibagi menjadi tiga kategori utama. Kelompok pertama adalah algoritma dasar
(Bubble, Selection, Insertion) dengan kompleksitas O(n²) yang cocok untuk data kecil, di mana Insertion Sort sangat unggul
jika data sudah hampir terurut. Kelompok kedua adalah algoritma tingkat lanjut (Merge dan Quick Sort) dengan efisiensi O(n
log n) untuk data besar; Merge Sort diandalkan karena kestabilannya, sedangkan Quick Sort dikenal sebagai yang tercepat.
Terakhir, Shell Sort hadir sebagai optimasi dari Insertion Sort yang efisien untuk menangani data berukuran menengah.

DAFTAR PUSTAKA

Daisma Bali. (2019. Des 14). Mengenal Sorting Berserta Contoh Source Code Pada Struktur Data.
[Link]
.html
AlgoCademy (Tidak ada keterangan waktu). Sorting Algorithms Explained: From Bubble Sort to Quick Sort
 [Link]
Sutiono, [Link].(Tidak ada keterangan waktu). Algoritma Merge Sort: Pengertian, Kelebihan dan Contoh
[Link]
[4] Setiawan, Y (2016, Jan 16). Algoritma Bubble Sort dengan Java
[Link]
Slide Share.(Tidak ada keterangan waktunya). Materi sorting(pengurutan)-Dasar-Dasar Pemprograman
[Link]
Chen, S. (2025, July 28). Algoritma Pengurutan Shell dengan CONTOH
[Link]
Helloit, K. (Tidak ada keterangan waktu). Mengenal Struktur Data Heap: Implementasi dan Contoh Kasus Penggunaannya
[Link]
admin1. (2018, Nov 2), Quick Sort pengertian, agoritma dan contoh pemrogramannya dalam C++, java, C dan PHP
[Link]
Agung, G.(2021. July 4). Makalah Algoritma Shell Sort
[Link]
Setiawan, Y. (2016, Jan 11). Algoritma Bubble Sort dengan Java
[Link]
How To Tekno. (2023, May 19). Contoh Bubble Sort, Pengertian, Manfaat, dan Cara Kerjanya.
[Link]
Firdausi, K. (2024, Feb 28). Insertion Sort: Pengertian, Cara Kerja, dan Implementasinya
[Link]
Simanjuntak, J. (2018/2019). Algoritma Sorting: Analisis Insertion, Bubble, dan Merge Sort
[Link]
Firdausi, K. (2024, Feb 28). Selection Sort: Pengertian, Cara Kerja, dan Implementasinya.
[Link]
How To Tekno. (2023, May 19). Contoh Merge Sort, Pengertian, beserta Cara Kerjanya.
[Link]