fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <random>
  4. #include <chrono>
  5.  
  6. //documet from ttp://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%A0%E3%82%BD%E3%83%BC%E3%83%88
  7.  
  8. std::vector<int> MakeData(std::size_t N){
  9. 	std::random_device rd;
  10. 	std::mt19937 mt(rd());
  11. 	std::uniform_int_distribution<> uid;
  12. 	std::vector<int> ret;
  13.  
  14. 	for (std::size_t i = 0; i < N; i++){
  15. 		ret.push_back(uid(mt));
  16. 	}
  17.  
  18. 	return ret;
  19. }
  20.  
  21. bool BubbleSort(std::vector<int>& vec){
  22. 	for (std::size_t i = 0; i < vec.size(); i++){
  23. 		for (std::size_t j = i + 1; j < vec.size(); j++){//maybe this is best speed of bubble sort.but has value line limited issue for large value.
  24. 			if (vec[i] < vec[j])std::swap(vec[i], vec[j]);
  25. 		}
  26. 	}
  27. 	return true;
  28. }
  29.  
  30. bool CombSort(std::vector<int>& vec){
  31. 	std::size_t h = vec.size();
  32. 	bool IsSwap = false;
  33.  
  34. 	while (h>1 || IsSwap){
  35. 		IsSwap = false;
  36. 		if (h > 1) h=(h * 10) / 13;
  37. 		for (int i = 0; i < vec.size() - h; i++){
  38. 			if (vec[i] < vec[i + h]){
  39. 				std::swap(vec[i], vec[i + h]);
  40. 				IsSwap = true;
  41. 			}
  42. 		}
  43. 	}
  44. 	return true;
  45. }
  46.  
  47. int main(){
  48.  
  49. 	//static const std::size_t N = 3000;//this number is use about 1sec in bubule sort for my pc.
  50. 	static const std::size_t N =25000;
  51. 	auto r1 = MakeData(N);
  52. 	auto r2 = r1;
  53.  
  54. 	auto S1 = std::chrono::system_clock::now();
  55. 	BubbleSort(r1);
  56. 	auto E1 = std::chrono::system_clock::now();
  57.  
  58. 	auto Eli1 = std::chrono::duration_cast <std::chrono::milliseconds>(E1 - S1);
  59.  
  60. 	auto S2 = std::chrono::system_clock::now();
  61. 	CombSort(r2);
  62. 	auto E2 = std::chrono::system_clock::now();
  63.  
  64. 	auto Eli2 = std::chrono::duration_cast <std::chrono::milliseconds>(E2 - S2);
  65.  
  66. 	std::cout << "bubble sort:" << Eli1.count() << "ms" << std::endl;
  67. 	std::cout << "comb sort:" << Eli2.count() << "ms" << std::endl;//oh fast!
  68.  
  69. 	bool F = false;
  70.  
  71. 	for (std::size_t i = 0; i < N; i++)	{
  72. 		F = r1[i] == r2[i];
  73. 		if (F == false) break;
  74. 	}
  75.  
  76. 	std::cout << "this is " << (F ? "Valid." : "Invalid.") << std::endl;
  77.  
  78. 	return 0;
  79. }
Success #stdin #stdout 1.26s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
bubble sort:1265ms
comb sort:3ms
this is Valid.
https://ideone.com/Hfv2Nf
language:
C++14 (gcc 8.3)
created:
11 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!