Code C++ Heap Sort & Quick Sort cho thuyết trình DSA UIT IT003.O24 (giảng viên cô Dương Việt Hằng)

heapSort.cpp

#include <bits/stdc++.h>
using namespace std;

void heapify(int[], int, int);
void heapSort(int[], int);
void display(int[], int);

int main()
{
    int arr[] = {1, 14, 3, 7, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Mang chua sap xep: " << endl;
    display(arr, n);
    heapSort(arr, n);
    cout << "Mang da sap xep: " << endl;
    display(arr, n);
}

void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << "\t";
    cout << endl;
}

void heapify(int arr[], int n, int i)
{
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest])
        largest = l;
    if (r < n && arr[r] > arr[largest])
        largest = r;
    if (largest != i)
    {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n)
{
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (int i = n - 1; i >= 0; i--)
    {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

quickSort_Hoare_v1.cpp

#include <bits/stdc++.h>
using namespace std;

int partition(int[], int, int);
void quickSort(int[], int, int);
void printArray(int[], int);

int main()
{
    int arr[] = {3, 6, 8, 10, 1, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Original array: ";
    printArray(arr, n);
    quickSort(arr, 0, n - 1);
    cout << "Sorted array: ";
    printArray(arr, n);
    return 0;
}

void printArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int partition(int arr[], int low, int high)
{
    int pivot = arr[low];
    int i = low - 1, j = high + 1;
    while (true)
    {
        do
            i++;
        while (arr[i] < pivot);
        do
            j--;
        while (arr[j] > pivot);
        if (i >= j)
            return j;
        swap(arr[i], arr[j]);
    }
}

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi);
        quickSort(arr, pi + 1, high);
    }
}

quickSort_Hoare_v2.cpp

#include <bits/stdc++.h>
using namespace std;

int partition(int[], int, int);
void quickSort(int[], int, int);
void printArray(int[], int);

int main()
{
    int arr[] = {3, 6, 8, 10, 1, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Original array: ";
    printArray(arr, n);
    quickSort(arr, 0, n - 1);
    cout << "Sorted array: ";
    printArray(arr, n);
    return 0;
}

void printArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int partition(int arr[], int low, int high)
{
    int pivot = arr[low];
    int i = low, j = high;
    while (true)
    {
        while (arr[i] < pivot)
            i++;
        while (arr[j] > pivot)
            j--;
        if (i >= j)
            return j;
        swap(arr[i], arr[j]);
        i++;
        j--;
    }
}

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi);
        quickSort(arr, pi + 1, high);
    }
}

quickSort_Lomuto.cpp

#include <bits/stdc++.h>
using namespace std;

int partition(int[], int, int);
void quickSort(int[], int, int);
void printArray(int[], int);

int main()
{
	int arr[] = {3, 6, 8, 10, 1, 2, 1};
	int n = sizeof(arr) / sizeof(arr[0]);
	cout << "Original array: ";
	printArray(arr, n);
	quickSort(arr, 0, n - 1);
	cout << "Sorted array: ";
	printArray(arr, n);
	return 0;
}

void printArray(int arr[], int size)
{
	for (int i = 0; i < size; i++)
		cout << arr[i] << " ";
	cout << endl;
}

int partition(int arr[], int low, int high)
{
	int pivot = arr[high];
	int i = low - 1;
	for (int j = low; j <= high; j++)
		if (arr[j] <= pivot)
		{
			i++;
			if (i != j)
				swap(arr[i], arr[j]);
		}
	return i;
}

void quickSort(int arr[], int low, int high)
{
	if (low < high)
	{
		int pi = partition(arr, low, high);
		quickSort(arr, low, pi - 1);
		quickSort(arr, pi + 1, high);
	}
}