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:

1. Initialization
   Fungsi bubble sort menggunakan
   $n$ sebagai panjang array.

        n = len(data)

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

        for i in range(n):

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

            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.

                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:

1. Initialization
   Fungsi insertion sort menggunakan
   $n$ sebagai panjang array.

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.

        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"

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.

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

        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.

    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

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.

    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.

    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

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}]]$.

        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.

            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]$