# 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
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;
}
```