SHARE
TWEET

Untitled

a guest Oct 9th, 2019 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cmath>
  4. #include <ctime>
  5. #include <stdlib.h>
  6.  
  7. using namespace std;
  8.  
  9. void HoanVi(int &x, int &y)  {  
  10.     int temp = x;  
  11.     x = y;  
  12.     y = temp;  
  13. }  
  14.  
  15. // Hàm phát sinh mảng dữ liệu ngẫu nhiên
  16. void GenerateRandomData(int a[], int n)
  17. {
  18.     srand((unsigned int)time(NULL));
  19.  
  20.     for (int i = 0; i < n; i++)
  21.     {
  22.         a[i] = rand()%n;
  23.     }
  24. }
  25.  
  26. // Hàm phát sinh mảng dữ liệu có thứ tự tăng dần
  27. void GenerateSortedData(int a[], int n)
  28. {
  29.     for (int i = 0; i < n; i++)
  30.     {
  31.         a[i] = i;
  32.     }
  33. }
  34.  
  35. // Hàm phát sinh mảng dữ liệu có thứ tự ngược (giảm dần)
  36. void GenerateReverseData(int a[], int n)
  37. {
  38.     for (int i = 0; i < n; i++)
  39.     {
  40.         a[i] = n - 1 - i;
  41.     }
  42. }
  43.  
  44. // Hàm phát sinh mảng dữ liệu gần như có thứ tự
  45. void GenerateNearlySortedData(int a[], int n)
  46. {
  47.     for (int i = 0; i < n; i++)
  48.     {
  49.         a[i] = i;
  50.     }
  51.     srand((unsigned int) time(NULL));
  52.     for (int i = 0; i < 10; i ++)
  53.     {
  54.         int r1 = rand()%n;
  55.         int r2 = rand()%n;
  56.         HoanVi(a[r1], a[r2]);
  57.     }
  58. }
  59.  
  60. void GenerateData(int a[], int n, int dataType)
  61. {
  62.     switch (dataType)
  63.     {
  64.     case 0: // ngẫu nhiên
  65.         GenerateRandomData(a, n);
  66.         break;
  67.     case 1: // có thứ tự
  68.         GenerateSortedData(a, n);
  69.         break;
  70.     case 2: // có thứ tự ngược
  71.         GenerateReverseData(a, n);
  72.         break;
  73.     case 3: // gần như có thứ tự
  74.         GenerateNearlySortedData(a, n);
  75.         break;
  76.     default:
  77.         printf("Error: unknown data type!\n");
  78.     }
  79. }
  80.  
  81.  
  82.  
  83. void selectionSort(int arr[], int n) {  
  84.     int i, j, min_idx;  
  85.  
  86.     for (i = 0; i < n-1; i++)  {  
  87.         min_idx = i;  
  88.         for (j = i+1; j < n; j++)  
  89.         if (arr[j] < arr[min_idx])  
  90.             min_idx = j;  
  91.  
  92.         HoanVi(arr[min_idx], arr[i]);  
  93.     }  
  94. }
  95. void insertionSort(int arr[], int n)  
  96. {  
  97.     int i, key, j;  
  98.     for (i = 1; i < n; i++)
  99.     {  
  100.         key = arr[i];  
  101.         j = i - 1;  
  102.  
  103.         /* Move elements of arr[0..i-1], that are  
  104.         greater than key, to one position ahead  
  105.         of their current position */
  106.         while (j >= 0 && arr[j] > key)
  107.         {  
  108.             arr[j + 1] = arr[j];  
  109.             j = j - 1;  
  110.         }  
  111.         arr[j + 1] = key;  
  112.     }  
  113. }  
  114.  
  115.  
  116.  
  117. int main() {
  118.     const int n = 100000;
  119.     int a[n];
  120.     GenerateData(a, n, 0);
  121.    
  122.     ofstream f("output.dat");
  123.    
  124.     f << n;
  125.  
  126.     for(int i = 0; i < n; i++) {
  127.         f << a[i] << " ";
  128.     }
  129.  
  130.     f << "\n";
  131.  
  132.  
  133.     clock_t tStart = clock();
  134.  
  135.     insertionSort(a, n);
  136.  
  137.     printf("Time taken: %.9fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
  138.  
  139.  
  140.     for(int i = 0; i < n; i++) {
  141.         f << a[i] << " ";
  142.     }
  143.     f << "\n";
  144.  
  145.     return 0;
  146. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top