Sorting Algorithms

Mencakup:

Bubble Sort
Insertion Sort
Quick Sort
Merge Sort
Selection Sort





































































































































































































































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























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:

Initialization
Fungsi bubble sort menggunakan \(n\) sebagai panjang array.

        n = len(data)

Looping 1 (\(i\))
Artinya, program melintasi seluruh array, dari elemen pertama sampai akhir dengan \(i\) sebagai indeks elemen.

        for i in range(n):

Looping 2 (\(j\))
Iterasi dalam dimulai. Setiap iterasi \(j\) akan membandingkan dua elemen bersebelahan dalam array.

            for j in range(0, n-i-1):

Swap
Pada setiap langkah dalam iterasi dalam, dilakukan pengecekan apakah elemen ke-\(j\) lebih besar dari elemen ke-(\(j+1\)). Jika ya, dilakukan pertukaran.

                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


























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:

Initialization
Fungsi insertion sort menggunakan \(n\) sebagai panjang array.

n = len(data)

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.

        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]\)

insertionsort_22104832_001_swap_000
insertionsort_22104832_002_swap_-01
insertionsort_22104832_003_swap_-01
insertionsort_22104832_004_swap_003
insertionsort_22104832_005_swap_004
insertionsort_22104832_006_swap_003
insertionsort_22104832_007_swap_003

Final array: \([0, 1, 2, 2, 2, 3, 4, 8]\)

Input: \([2, 2, 1, 0, 4, 8, 7, 6]\)

insertionsort_22104876_001_swap_000
insertionsort_22104876_002_swap_-01
insertionsort_22104876_003_swap_-01
insertionsort_22104876_004_swap_003
insertionsort_22104876_005_swap_004
insertionsort_22104876_006_swap_004
insertionsort_22104876_007_swap_004

Final array: \([0, 1, 2, 2, 4, 6, 7, 8]\)

Quick Sort

Penjelasan

Quick Sort jenis "Median of Three"












































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:

Untuk contoh, array \(N = [2, 1, 4, 6, 8]\)
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.

        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]

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).

        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]

Recursion
Panggilan rekursif dilakukan untuk dua bagian data yang terpisah, yaitu bagian sebelum pivot dan bagian setelah pivot.

    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]\)

quicksort_22104635_0
quicksort_22104635_1
quicksort_22104635_2
quicksort_22104635_3
quicksort_22104635_4
quicksort_22104635_5
quicksort_22104635_6
quicksort_22104635_7
quicksort_22104635_8

Final array:\([0, 1, 2, 2, 3, 4, 5, 6]\)

Input: \([2, 2, 1, 0, 4, 8, 6, 9]\)

quicksort_22104869_0
quicksort_22104869_1
quicksort_22104869_2
quicksort_22104869_3
quicksort_22104869_4
quicksort_22104869_5
quicksort_22104869_6
quicksort_22104869_7
quicksort_22104869_8

Final array: \([0, 1, 2, 2, 4, 6, 8, 9]\)

Merge Sort

Penjelasan




















































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:

Divide and Conquer
Fungsi merge_sort membagi array menjadi array dengan panjang 1 dengan dipanggil secara rekursif.

    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)

Merge
Fungsi merge menggabungkan array dengan urutan yang benar.

    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]\)

mergesort_22104643_0
mergesort_22104643_1
mergesort_22104643_2
mergesort_22104643_3
mergesort_22104643_4
mergesort_22104643_5
mergesort_22104643_6
mergesort_22104643_7
mergesort_22104643_8

Final array: \([0, 1, 2, 2, 3, 4, 4, 6]\)

Input: \([2, 2, 1, 0, 4, 9, 3, 6]\)

mergesort_22104936_0
mergesort_22104936_1
mergesort_22104936_2
mergesort_22104936_3
mergesort_22104936_4
mergesort_22104936_5
mergesort_22104936_6
mergesort_22104936_7
mergesort_22104936_8

Final array: \([0, 1, 2, 2, 3, 4, 6, 9]\)

Selection Sort

Penjelasan





























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:

The Smallest
Fungsi mencari elemen terkecil di array dengan indeks lebih dari \(i\) yang lebih kecil dari \(\text{data}[\text{min_idx}]]\).

        for i in range(n):
            min_idx = i
            for j in range(i+1, n):
                if data[j] < data[min_idx]:
                    min_idx = j

Swappage
Saat iterasi array dengan indeks lebih dari \(i\) selesai, jika ditemukan yang matching maka akan di swap.

            data[i], data[min_idx] = data[min_idx], data[i]

Looping
Looping berulang sampai selesai.

Contoh

Input: \([2, 2, 1, 0, 4, 3, 7, 5]\)

selectionsort_22104375_0
selectionsort_22104375_1
selectionsort_22104375_2
selectionsort_22104375_3
selectionsort_22104375_4
selectionsort_22104375_5
selectionsort_22104375_6
selectionsort_22104375_7
selectionsort_22104375_8
selectionsort_22104375_9

Final array: \([0, 1, 2, 2, 3, 4, 5, 7]\)

Input: \([2, 2, 1, 0, 4, 5, 7, 6]\)

selectionsort_22104576_0
selectionsort_22104576_1
selectionsort_22104576_2
selectionsort_22104576_3
selectionsort_22104576_4
selectionsort_22104576_5
selectionsort_22104576_6
selectionsort_22104576_7
selectionsort_22104576_8
selectionsort_22104576_9

Final array: \([0, 1, 2, 2, 4, 5, 6, 7]\)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.