So sánh thời gian chạy (Sort algorithms)

So sánh thời gian chạy, số lần so sánh (comparison count) và số lần hoán vị (swap count) của các thuật toán sắp xếp như: selection sort, insertion sort, interchange sort, bubble sort, quick sort
 avatar
user_1746670
c_cpp
a month ago
4.8 kB
3
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

// Selection Sort
void selectionSort(vector<int>& arr, int& comparison_count, int& swap_count) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            comparison_count++;
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }
        if (min_idx != i) {
            swap(arr[i], arr[min_idx]);
            swap_count++;
        }
    }
}

// Insertion Sort
void insertionSort(vector<int>& arr, int& comparison_count, int& swap_count) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            comparison_count++;
            arr[j + 1] = arr[j];
            j--;
            swap_count++;
        }
        if (j >= 0) comparison_count++;
        arr[j + 1] = key;
    }
}

// Interchange Sort
void interchangeSort(vector<int>& arr, int& comparison_count, int& swap_count) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            comparison_count++;
            if (arr[i] > arr[j]) {
                swap(arr[i], arr[j]);
                swap_count++;
            }
        }
    }
}

// Bubble Sort
void bubbleSort(vector<int>& arr, int& comparison_count, int& swap_count) {
    int n = arr.size();
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            comparison_count++;
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swap_count++;
                swapped = true;
            }
        }
        if (!swapped)
            break;
    }
}

// Quick Sort
int partition(vector<int>& arr, int low, int high, int& comparison_count, int& swap_count) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        comparison_count++;
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
            swap_count++;
        }
    }
    swap(arr[i + 1], arr[high]);
    swap_count++;
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high, int& comparison_count, int& swap_count) {
    if (low < high) {
        int pi = partition(arr, low, high, comparison_count, swap_count);
        quickSort(arr, low, pi - 1, comparison_count, swap_count);
        quickSort(arr, pi + 1, high, comparison_count, swap_count);
    }
}

void PhatSinhVector(vector<int>& vec, int n) {
    srand(0);
    vec.resize(n);
    for (int i = 0; i < n; i++) {
        vec[i] = rand() % 10000;
    }
}

int main() {
    vector<int> arr1, arr2, arr3, arr4, arr5;
    PhatSinhVector(arr1, 50000);
    arr2 = arr1;
    arr3 = arr1;
    arr4 = arr1;
    arr5 = arr1;

    int comparison_count, swap_count;

    // Selection Sort
    comparison_count = 0;
    swap_count = 0;
    clock_t start = clock();
    selectionSort(arr1, comparison_count, swap_count);
    clock_t end = clock();
    double t = double(end - start) / CLOCKS_PER_SEC;
    cout << "Selection Sort - Time: " << t << " sec, Comparisons: " << comparison_count << ", Swaps: " << swap_count << endl;

    // Insertion Sort
    comparison_count = 0;
    swap_count = 0;
    start = clock();
    insertionSort(arr2, comparison_count, swap_count);
    end = clock();
    t = double(end - start) / CLOCKS_PER_SEC;
    cout << "Insertion Sort - Time: " << t << " sec, Comparisons: " << comparison_count << ", Swaps: " << swap_count << endl;

    // Interchange Sort
    comparison_count = 0;
    swap_count = 0;
    start = clock();
    interchangeSort(arr3, comparison_count, swap_count);
    end = clock();
    t = double(end - start) / CLOCKS_PER_SEC;
    cout << "Interchange Sort - Time: " << t << " sec, Comparisons: " << comparison_count << ", Swaps: " << swap_count << endl;

    // Bubble Sort
    comparison_count = 0;
    swap_count = 0;
    start = clock();
    bubbleSort(arr4, comparison_count, swap_count);
    end = clock();
    t = double(end - start) / CLOCKS_PER_SEC;
    cout << "Bubble Sort - Time: " << t << " sec, Comparisons: " << comparison_count << ", Swaps: " << swap_count << endl;

    // Quick Sort
    comparison_count = 0;
    swap_count = 0;
    start = clock();
    quickSort(arr5, 0, arr5.size() - 1, comparison_count, swap_count);
    end = clock();
    t = double(end - start) / CLOCKS_PER_SEC;
    cout << "Quick Sort - Time: " << t << " sec, Comparisons: " << comparison_count << ", Swaps: " << swap_count << endl;

    return 0;
}
Leave a Comment