owned this note
owned this note
Published
Linked with GitHub
# Sorting Algorithms
Mencakup:
- Bubble Sort
- Insertion Sort
- Quick Sort
- Merge Sort
- Selection Sort
```python=
from abc import ABC
import matplotlib.pyplot as plt
import copy
# made by: velo/malik
class SortingAlgorithm(ABC):
def __init__(self):
pass
def sort(self, data):
raise NotImplementedError()
class BubbleSort(SortingAlgorithm):
def __init__(self):
super().__init__()
def sort(self, data: list[int]):
n = len(data)
self.original = copy.deepcopy(data)
for i in range(n):
for j in range(0, n-i-1):
if data[j] > data[j+1]:
data[j], data[j+1] = data[j+1], data[j]
self.visualize(data, i, j)
return data
def visualize(self, data, iteration, j):
colors = ['blue' if x == j or x == j+1 else 'lightblue' for x in range(len(data))]
plt.clf()
plt.bar(range(len(data)), data, color=colors)
plt.title(f'Bubble Sort: {self.original} - Iteration {iteration}')
plt.savefig(f'./saves/bubblesort_{"".join([str(h) for h in self.original])}_{iteration:03d}_swap_{j:03d}.png')
class InsertionSort(SortingAlgorithm):
def __init__(self):
super().__init__()
def sort(self, data: list[int]):
n = len(data)
self.original = copy.deepcopy(data)
for iteration in range(1, n):
key = data[iteration]
j = iteration - 1
while j >= 0 and key < data[j]:
data[j + 1] = data[j]
j -= 1
data[j + 1] = key
self.visualize(data, iteration, j)
return data
def visualize(self, data, iteration, j):
colors = ['blue' if x == j or x == iteration else 'lightblue' for x in range(len(data))]
plt.clf()
plt.bar(range(len(data)), data, color=colors)
plt.title(f'Insertion Sort: {self.original} - Iteration {iteration}')
plt.savefig(f'./saves/insertionsort_{"".join([str(h) for h in self.original])}_{iteration:03d}_swap_{j:03d}.png')
class QuickSort(SortingAlgorithm):
def __init__(self):
super().__init__()
self.count = 0
def sort(self, data: list[int]):
self.original = copy.deepcopy(data)
self.visualize(data, 0, len(data) - 1, -1, -1)
self.quick_sort(data, 0, len(data) - 1)
self.visualize(data, 0, len(data) - 1, -1, -1)
return data
def quick_sort(self, data, low, high):
if low < high:
pi = self.partition(data, low, high)
self.quick_sort(data, low, pi - 1)
self.quick_sort(data, pi + 1, high)
def partition(self, data, low, high):
mid = (low + high) // 2
pivot = sorted([data[low], data[mid], data[high]])[1]
if pivot == data[low]:
data[low], data[high] = data[high], data[low]
elif pivot == data[mid]:
data[mid], data[high] = data[high], data[mid]
i = low - 1
for j in range(low, high):
if data[j] < pivot:
i += 1
data[i], data[j] = data[j], data[i]
self.visualize(data, low, high, i, j)
data[i + 1], data[high] = data[high], data[i + 1]
return i + 1
def visualize(self, data, low, high, i, j):
colors = ['blue' if x == i or x == j else 'lightblue' for x in range(len(data))]
plt.clf()
plt.bar(range(len(data)), data, color=colors)
plt.title(f'Quick Sort: {self.original} - Partition {low}-{high}')
plt.savefig(f'./saves/quicksort_{"".join([str(h) for h in self.original])}_{self.count}.png')
self.count += 1
class MergeSort(SortingAlgorithm):
def __init__(self):
super().__init__()
self.count = 0
def sort(self, data: list[int]):
self.original = copy.deepcopy(data)
self.visualize(data, 0, len(data) - 1)
self.merge_sort(data, 0, len(data) - 1)
self.visualize(data, 0, len(data) - 1)
return data
def merge_sort(self, data, low, high):
if low < high:
mid = (low + high) // 2
self.merge_sort(data, low, mid)
self.merge_sort(data, mid + 1, high)
self.merge(data, low, mid, high)
self.visualize(data, low, high)
def merge(self, data, low, mid, high):
left = data[low:mid+1]
right = data[mid+1:high+1]
i = j = 0
k = low
while i < len(left) and j < len(right):
if left[i] < right[j]:
data[k] = left[i]
i += 1
else:
data[k] = right[j]
j += 1
k += 1
while i < len(left):
data[k] = left[i]
i += 1
k += 1
while j < len(right):
data[k] = right[j]
j += 1
k += 1
def visualize(self, data, low, high):
colors = ['blue' if x >= low and x <= high else 'lightblue' for x in range(len(data))]
plt.clf()
plt.bar(range(len(data)), data, color=colors)
plt.title(f'Merge Sort: {self.original} - Merging {low}-{high}')
plt.savefig(f'./saves/mergesort_{"".join([str(h) for h in self.original])}_{self.count}.png')
self.count += 1
class SelectionSort(SortingAlgorithm):
def __init__(self):
super().__init__()
self.count = 0
def sort(self, data: list[int]):
self.original = copy.deepcopy(data)
self.visualize(data, 0, len(data) - 1)
self.selection_sort(data)
self.visualize(data, 0, len(data) - 1)
return data
def selection_sort(self, data):
n = len(data)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if data[j] < data[min_idx]:
min_idx = j
data[i], data[min_idx] = data[min_idx], data[i]
self.visualize(data, i, min_idx)
def visualize(self, data, i, j):
colors = ['blue' if x == i or x == j else 'lightblue' for x in range(len(data))]
plt.clf()
plt.bar(range(len(data)), data, color=colors)
plt.title(f'Selection Sort: {self.original} - Swapping {i}-{j}')
plt.savefig(f'./saves/selectionsort_{"".join([str(h) for h in self.original])}_{self.count}.png')
self.count += 1
def main():
test_cases = [
[2, 2, 1, 0, 4, 3, 7, 6],
[2, 2, 1, 0, 4, 8, 3, 2],
[2, 2, 1, 0, 4, 8, 6, 9],
[2, 2, 1, 0, 4, 6, 4, 3],
[2, 2, 1, 0, 4, 3, 7, 5],
[2, 2, 1, 0, 4, 1, 6, 2],
[2, 2, 1, 0, 4, 8, 7, 6],
[2, 2, 1, 0, 4, 6, 3, 5],
[2, 2, 1, 0, 4, 9, 3, 6],
[2, 2, 1, 0, 4, 5, 7, 6],
]
for idx, item in enumerate(test_cases):
case = idx % 5
if case == 0:
algorithm = BubbleSort()
elif case == 1:
algorithm = InsertionSort()
elif case == 2:
algorithm = QuickSort()
elif case == 3:
algorithm = MergeSort()
else:
algorithm = SelectionSort()
result = algorithm.sort(item)
if result == sorted(item):
print(f"Sorting {item} with {algorithm.__class__.__name__} is correct")
if __name__ == "__main__":
main()
```
# Bubble Sort
## Penjelasan
```python=
class BubbleSort(SortingAlgorithm):
def __init__(self):
super().__init__()
def sort(self, data: list[int]):
n = len(data)
self.original = copy.deepcopy(data)
for i in range(n):
for j in range(0, n-i-1):
if data[j] > data[j+1]:
data[j], data[j+1] = data[j+1], data[j]
self.visualize(data, i, j)
return data
def visualize(self, data, iteration, j):
colors = ['blue' if x == j or x == j+1 else 'lightblue' for x in range(len(data))]
plt.clf()
plt.bar(range(len(data)), data, color=colors)
plt.title(f'Bubble Sort: {self.original} - Iteration {iteration}')
plt.savefig(f'./saves/bubblesort_{"".join([str(h) for h in self.original])}_{iteration:03d}_swap_{j:03d}.png')
```
How it works:
1. Initialization
Fungsi bubble sort menggunakan $n$ sebagai panjang array.
```python
n = len(data)
```
2. Looping 1 ($i$)
Artinya, program melintasi seluruh array, dari elemen pertama sampai akhir dengan $i$ sebagai indeks elemen.
```python
for i in range(n):
```
3. Looping 2 ($j$)
Iterasi dalam dimulai. Setiap iterasi $j$ akan membandingkan dua elemen bersebelahan dalam array.
```python
for j in range(0, n-i-1):
```
4. Swap
Pada setiap langkah dalam iterasi dalam, dilakukan pengecekan apakah elemen ke-$j$ lebih besar dari elemen ke-($j+1$). Jika ya, dilakukan pertukaran.
```python
if data[j] > data[j+1]:
data[j], data[j+1] = data[j+1], data[j]
self.visualize(data, i, j)
```
## Contoh
Langkah-langkah yang ditampilkan hanya yang pada kondisi $N[j] > N[j+1]$, atau artinya apabila ada swap.
### Input: $[2, 2, 1, 0, 4, 1, 6, 2]$
| Swap | Image |
|---------------|---------------------------------------------------------------------------------------------|
| $i = 0, j = 1$|  |
| $i = 0, j = 2$|  |
| $i = 0, j = 4$|  |
| $i = 0, j = 6$|  |
| $i = 1, j = 0$|  |
| $i = 1, j = 1$|  |
| $i = 1, j = 3$|  |
| $i = 1, j = 5$|  |
| $i = 2, j = 0$|  |
| $i = 2, j = 2$|  |
Final array: $[0, 1, 1, 2, 2, 2, 4, 6]$
### Input: $[2, 2, 1, 0, 4, 3, 7, 6]$
| Swap | Image |
|---------------------------------------|---------------------------------------------------------|
| $i = 0, j = 1$ |  |
| $i = 0, j = 2$ |  |
| $i = 0, j = 4$ |  |
| $i = 0, j = 6$ |  |
| $i = 1, j = 0$ |  |
| $i = 1, j = 1$ |  |
| $i = 2, j = 0$ |  |
Final array: $[0, 1, 2, 2, 3, 4, 6, 7]$
# Insertion Sort
## Penjelasan
```python=
class InsertionSort(SortingAlgorithm):
def __init__(self):
super().__init__()
def sort(self, data: list[int]):
n = len(data)
self.original = copy.deepcopy(data)
for iteration in range(1, n):
key = data[iteration]
j = iteration - 1
while j >= 0 and key < data[j]:
data[j + 1] = data[j]
j -= 1
data[j + 1] = key
self.visualize(data, iteration, j)
return data
def visualize(self, data, iteration, j):
colors = ['blue' if x == j or x == iteration else 'lightblue' for x in range(len(data))]
plt.clf()
plt.bar(range(len(data)), data, color=colors)
plt.title(f'Insertion Sort: {self.original} - Iteration {iteration}')
plt.savefig(f'./saves/insertionsort_{"".join([str(h) for h in self.original])}_{iteration:03d}_swap_{j:03d}.png')
```
How it works:
1. Initialization
Fungsi insertion sort menggunakan $n$ sebagai panjang array.
```python
n = len(data)
```
2. Looping
Untuk setiap elemen $iteration$ (mulai dari indeks 1), cek berulang-ulang sampai indeks 0 atau sampai ada elemen-elemen sebelumnya yang lebih besar dari $iteration$. Jika berhenti, maka pindahkan elemen ke indeks tersebut.
```python
for iteration in range(1, n):
key = data[iteration]
j = iteration - 1
while j >= 0 and key < data[j]:
data[j + 1] = data[j]
j -= 1
data[j + 1] = key
self.visualize(data, iteration, j)
```
## Contoh
### Input: $[2, 2, 1, 0, 4, 8, 3, 2]$
Final array: $[0, 1, 2, 2, 2, 3, 4, 8]$
### Input: $[2, 2, 1, 0, 4, 8, 7, 6]$
Final array: $[0, 1, 2, 2, 4, 6, 7, 8]$
# Quick Sort
## Penjelasan
Quick Sort jenis "Median of Three"
```python=
class QuickSort(SortingAlgorithm):
def __init__(self):
super().__init__()
self.count = 0
def sort(self, data: list[int]):
self.original = copy.deepcopy(data)
self.visualize(data, 0, len(data) - 1, -1, -1)
self.quick_sort(data, 0, len(data) - 1)
self.visualize(data, 0, len(data) - 1, -1, -1)
return data
def quick_sort(self, data, low, high):
if low < high:
pi = self.partition(data, low, high)
self.quick_sort(data, low, pi - 1)
self.quick_sort(data, pi + 1, high)
def partition(self, data, low, high):
mid = (low + high) // 2
pivot = sorted([data[low], data[mid], data[high]])[1]
if pivot == data[low]:
data[low], data[high] = data[high], data[low]
elif pivot == data[mid]:
data[mid], data[high] = data[high], data[mid]
i = low - 1
for j in range(low, high):
if data[j] < pivot:
i += 1
data[i], data[j] = data[j], data[i]
self.visualize(data, low, high, i, j)
data[i + 1], data[high] = data[high], data[i + 1]
return i + 1
def visualize(self, data, low, high, i, j):
colors = ['blue' if x == i or x == j else 'lightblue' for x in range(len(data))]
plt.clf()
plt.bar(range(len(data)), data, color=colors)
plt.title(f'Quick Sort: {self.original} - Partition {low}-{high}')
plt.savefig(f'./saves/quicksort_{"".join([str(h) for h in self.original])}_{self.count}.png')
self.count += 1
```
How it works:
1. Untuk contoh, array $N = [2, 1, 4, 6, 8]$
2. Pivoting
Ambil pivot yaitu median dari awal, tengah, dan akhir array, yaitu $\text{pivot} = \text{median}([2, 4, 8]) = 4$
Pivot diposisikan di akhir data.
Jika pivot bukan elemen pertama, maka swap dilakukan untuk memindahkannya ke akhir.
```python
mid = (low + high) // 2
pivot = sorted([data[low], data[mid], data[high]])[1]
if pivot == data[low]:
data[low], data[high] = data[high], data[low]
elif pivot == data[mid]:
data[mid], data[high] = data[high], data[mid]
```
3. Iterating and Partitioning
Iterasi dilakukan pada seluruh data. Setiap elemen dibandingkan dengan pivot. Jika elemen lebih kecil dari pivot, maka elemen tersebut dipindahkan ke sebelah kiri (partisi kiri).
```python
i = low - 1
for j in range(low, high):
if data[j] < pivot:
i += 1
data[i], data[j] = data[j], data[i]
self.visualize(data, low, high, i, j)
data[i + 1], data[high] = data[high], data[i + 1]
```
4. Recursion
Panggilan rekursif dilakukan untuk dua bagian data yang terpisah, yaitu bagian sebelum pivot dan bagian setelah pivot.
```python
def quick_sort(self, data, low, high):
if low < high:
pi = self.partition(data, low, high)
self.quick_sort(data, low, pi - 1)
self.quick_sort(data, pi + 1, high)
```
## Contoh
### Input: $[2, 2, 1, 0, 4, 6, 3, 5]$
Final array:$[0, 1, 2, 2, 3, 4, 5, 6]$
### Input: $[2, 2, 1, 0, 4, 8, 6, 9]$
Final array: $[0, 1, 2, 2, 4, 6, 8, 9]$
# Merge Sort
## Penjelasan
```python=
class MergeSort(SortingAlgorithm):
def __init__(self):
super().__init__()
self.count = 0
def sort(self, data: list[int]):
self.original = copy.deepcopy(data)
self.visualize(data, 0, len(data) - 1)
self.merge_sort(data, 0, len(data) - 1)
self.visualize(data, 0, len(data) - 1)
return data
def merge_sort(self, data, low, high):
if low < high:
mid = (low + high) // 2
self.merge_sort(data, low, mid)
self.merge_sort(data, mid + 1, high)
self.merge(data, low, mid, high)
self.visualize(data, low, high)
def merge(self, data, low, mid, high):
left = data[low:mid+1]
right = data[mid+1:high+1]
i = j = 0
k = low
while i < len(left) and j < len(right):
if left[i] < right[j]:
data[k] = left[i]
i += 1
else:
data[k] = right[j]
j += 1
k += 1
while i < len(left):
data[k] = left[i]
i += 1
k += 1
while j < len(right):
data[k] = right[j]
j += 1
k += 1
def visualize(self, data, low, high):
colors = ['blue' if x >= low and x <= high else 'lightblue' for x in range(len(data))]
plt.clf()
plt.bar(range(len(data)), data, color=colors)
plt.title(f'Merge Sort: {self.original} - Merging {low}-{high}')
plt.savefig(f'./saves/mergesort_{"".join([str(h) for h in self.original])}_{self.count}.png')
self.count += 1
```
How it works:
1. Divide and Conquer
Fungsi `merge_sort` membagi array menjadi array dengan panjang 1 dengan dipanggil secara rekursif.
```python
def merge_sort(self, data, low, high):
if low < high:
mid = (low + high) // 2
self.merge_sort(data, low, mid)
self.merge_sort(data, mid + 1, high)
self.merge(data, low, mid, high)
self.visualize(data, low, high)
```
2. Merge
Fungsi `merge` menggabungkan array dengan urutan yang benar.
```python
def merge(self, data, low, mid, high):
left = data[low:mid+1]
right = data[mid+1:high+1]
i = j = 0
k = low
while i < len(left) and j < len(right):
if left[i] < right[j]:
data[k] = left[i]
i += 1
else:
data[k] = right[j]
j += 1
k += 1
while i < len(left):
data[k] = left[i]
i += 1
k += 1
while j < len(right):
data[k] = right[j]
j += 1
k += 1
```
## Contoh
### Input: $[2, 2, 1, 0, 4, 6, 4, 3]$
Final array: $[0, 1, 2, 2, 3, 4, 4, 6]$
### Input: $[2, 2, 1, 0, 4, 9, 3, 6]$
Final array: $[0, 1, 2, 2, 3, 4, 6, 9]$
# Selection Sort
## Penjelasan
```python=
class SelectionSort(SortingAlgorithm):
def __init__(self):
super().__init__()
self.count = 0
def sort(self, data: list[int]):
self.original = copy.deepcopy(data)
self.visualize(data, 0, len(data) - 1)
self.selection_sort(data)
self.visualize(data, 0, len(data) - 1)
return data
def selection_sort(self, data):
n = len(data)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if data[j] < data[min_idx]:
min_idx = j
data[i], data[min_idx] = data[min_idx], data[i]
self.visualize(data, i, min_idx)
def visualize(self, data, i, j):
colors = ['blue' if x == i or x == j else 'lightblue' for x in range(len(data))]
plt.clf()
plt.bar(range(len(data)), data, color=colors)
plt.title(f'Selection Sort: {self.original} - Swapping {i}-{j}')
plt.savefig(f'./saves/selectionsort_{"".join([str(h) for h in self.original])}_{self.count}.png')
self.count += 1
```
How it works:
1. The Smallest
Fungsi mencari elemen terkecil di array dengan indeks lebih dari $i$ yang lebih kecil dari $\text{data}[\text{min_idx}]]$.
```python
for i in range(n):
min_idx = i
for j in range(i+1, n):
if data[j] < data[min_idx]:
min_idx = j
```
2. Swappage
Saat iterasi array dengan indeks lebih dari $i$ selesai, jika ditemukan yang matching maka akan di swap.
```python
data[i], data[min_idx] = data[min_idx], data[i]
```
3. Looping
Looping berulang sampai selesai.
## Contoh
### Input: $[2, 2, 1, 0, 4, 3, 7, 5]$
Final array: $[0, 1, 2, 2, 3, 4, 5, 7]$
## Input: $[2, 2, 1, 0, 4, 5, 7, 6]$
Final array: $[0, 1, 2, 2, 4, 5, 6, 7]$
Google Drive
Gist
Clipboard
Sign in with Wallet
