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 sortuser_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