fork download
copy 
  1. // sort_vector_vs_array.cpp : Defines the entry point for the console application.
  2. //
  3.  
  4. #include <iostream>
  5. #include <cmath>
  6. #include <vector>
  7. #include <ctime>
  8. #include <cstdlib>
  9. //#include <chrono>
  10.  
  11.  
  12. const int arraylength=2000000;
  13.  
  14. //This is an implementation of merge_sort, an algorithm to sort a list of integers using
  15. //a recursion relation.  The merge_sort is written as two functions, `merge` which takes two
  16. //pre-sorted lists and merges them to a single sorted list.  This is called on by merge_sort, 
  17. //which also recursively calls itself.
  18.  
  19. //I've implemented it here twice, first with the two functions `merge` and `merge_sort`, and then
  20. //again with `vmerge` and `vmerge_sort`.  The first two take as their argument arrays of integers, 
  21. //while the second two take the data type `vector` from the `vector` package (is package the right word?
  22. //or do I say library?).  
  23.  
  24.  
  25. void merge(int A[], int LA[], int RA[], int p, int q, int r)
  26. {
  27.     //n1 and n2 are the lengths of the pre-sorted sublists, A[p..q] and A[q+1..r]
  28.     int n1=q-p+1;
  29.     int n2=r-q;
  30.     //Copy the left and right halves of the A array into the L and R arrays
  31.     for(int i=0;i<n1; i++)
  32.     {
  33.         LA[i]=A[p+i];
  34.     }
  35.     for(int j=0;j<n2; j++)
  36.     {
  37.         RA[j]=A[q+1+j];
  38.     }
  39.  
  40.  
  41.     //Merge the L and R lists
  42.     int i=0;
  43.     int j=0;
  44.     int k = p;
  45.     while(i < n1 && j < n2) {
  46.         A[k++] = (LA[i]<=RA[j])  
  47.                    ? LA[i++]    
  48.                    : RA[j++];
  49.     }
  50.     while(i < n1) {
  51.         A[k++] = LA[i++];
  52.     }
  53.     while(j < n2) {
  54.         A[k++] = RA[j++];
  55.     }
  56. }
  57.  
  58. void merge_sort(int A[], int LA[], int RA[], int p, int r)
  59. {
  60.     //This recursively splits the array A into smaller sections 
  61.     if(p<r)
  62.     {
  63.         int q=(p+r)/2;
  64.         merge_sort(A,LA,RA,p,q);
  65.         merge_sort(A,LA,RA,q+1,r);
  66.         merge(A,LA,RA,p,q,r);
  67.     }
  68.  
  69. }
  70.  
  71.  
  72. void vmerge(std::vector<int>& A, std::vector<int>& LA, std::vector<int>& RA, int p, int q, int r)
  73. {
  74.     //n1 and n2 are the lengths of the pre-sorted sublists, A[p..q] and A[q+1..r]
  75.     int n1=q-p+1;
  76.     int n2=r-q;
  77.     //Copy the left and right halves of the A array into the L and R arrays
  78.     for(int i=0;i<n1; i++)
  79.     {
  80.         LA[i]=A[p+i];
  81.     }
  82.     for(int j=0;j<n2; j++)
  83.     {
  84.         RA[j]=A[q+1+j];
  85.     }
  86.  
  87.  
  88.     //Merge the L and R lists
  89.     int i=0;
  90.     int j=0;
  91.     int k = p;
  92.     while(i < n1 && j < n2) {
  93.         A[k++] = (LA[i]<=RA[j])  
  94.                    ? LA[i++]    
  95.                    : RA[j++];
  96.     }
  97.     while(i < n1) {
  98.         A[k++] = LA[i++];
  99.     }
  100.     while(j < n2) {
  101.         A[k++] = RA[j++];
  102.     }
  103. }
  104.  
  105. void vmerge_sort(std::vector<int>& A, std::vector<int>& LA, std::vector<int>& RA, int p, int r)
  106. {
  107.     //This recursively splits the array A into smaller sections 
  108.     if(p<r)
  109.     {
  110.         int q=(p+r)/2;
  111.         vmerge_sort(A,LA,RA,p,q);
  112.         vmerge_sort(A,LA,RA,q+1,r);
  113.         vmerge(A,LA,RA,p,q,r);
  114.     }
  115.  
  116. }
  117.  
  118.  
  119. int main(void)
  120. {
  121.     //seed the random number generator
  122.     srand(time(0));
  123.     //std::chrono::high_resolution_clock::time_point t1,t2;
  124.  
  125.     std::cout<<"C++ merge-sort test"<<std::endl;
  126.  
  127.     int halfarraylength=arraylength/2+2;
  128.  
  129.     //rlist1 is defined to be an integer array
  130.     //L and R are the subarrays used in the merge function
  131.     int *rlist1= new int[arraylength];
  132.     int *R= new int[halfarraylength];
  133.     int *L= new int[halfarraylength];
  134.  
  135.  
  136.     //vlist is defined to be of type vector<int>
  137.     //vL and vR are the left and right subvectors used in the vmerge function
  138.     std::vector<int> vlist1(arraylength);
  139.     std::vector<int> vL(halfarraylength);
  140.     std::vector<int> vR(halfarraylength);
  141.  
  142.  
  143.     //both vlist1 and rlist1 have the same content, 2 million random integers
  144.     for(int i=0;i<=arraylength-1;i++)
  145.     {
  146.         rlist1[i] = rand() % 1000000;
  147.         vlist1[i] = rlist1[i];
  148.     }
  149.  
  150.  
  151.     //here I sort rlist1
  152.     //t1 = std::chrono::high_resolution_clock::now();
  153.     std::clock_t t1=clock();
  154.     merge_sort(rlist1,L,R,0,arraylength-1);
  155.     //t2 = std::chrono::high_resolution_clock::now();
  156.     std::clock_t t2=clock();
  157.     std::cout << "sorting "<<arraylength<<" random numbers with merge sort took "
  158.     //               << std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count()
  159.     //               << " milliseconds\n";
  160.                    << (double)(t2 - t1) / CLOCKS_PER_SEC << " seconds\n";
  161.  
  162.  
  163.     //here I sort vlist1          
  164.     //t1 = std::chrono::high_resolution_clock::now();
  165.     t1 = clock();
  166.     vmerge_sort(vlist1,vL,vR,0,arraylength-1);
  167.     //t2 = std::chrono::high_resolution_clock::now();
  168.     t2 = clock();
  169.     std::cout << "sorting "<<arraylength<<" random numbers with vmerge sort took "
  170.     //               << std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count()
  171.     //               << " milliseconds\n";
  172.                    << (double)(t2 - t1) / CLOCKS_PER_SEC << " seconds\n";
  173.     //Now we test that both sorted lists are identical
  174.     std::cout << "Testing that both sorted lists are the same"<< std::endl;
  175.     for (int k=0; k< arraylength; k++)
  176.     {
  177.         if (rlist1[k] != vlist1[k])
  178.         {
  179.             std::cout << "The lists are not the same\n";
  180.             return -1;
  181.         }
  182.     }
  183.  
  184.     std::cout<< "Both lists are the same\n";
  185.  
  186.     return 0;
  187. }
  188.  
Success #stdin #stdout 0.88s 18776KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
C++ merge-sort test
sorting 2000000 random numbers with merge sort took 0.405822 seconds
sorting 2000000 random numbers with vmerge sort took 0.406643 seconds
Testing that both sorted lists are the same
Both lists are the same
https://ideone.com/WMXSLM
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!