fork download
copy 
  1. #include <iostream>
  2. #include <cstdlib>
  3. void b_heapify(int* arr, size_t N, size_t i, 
  4. 	           bool (*pcmp)(int, int));
  5. void psort(int* arr, size_t N, bool (*pcmp)(int, int));
  6. bool bfind(const int* f, const int* l, int x, 
  7. 	       bool (*pcmp)(int, int));
  8.  
  9. bool compare(int a, int b){ return (a > b); }
  10.  
  11.  
  12.  
  13. int main(void){
  14. 	const size_t N = 20;
  15. 	int A[N];
  16.  
  17. 	for(size_t i = 0; i < N; ++i){
  18. 		A[i] = std::rand() % 10;
  19. 		std::cout << A[i] << ' ';
  20. 	}
  21. 	std::cout << std::endl;
  22.  
  23. 	//сортируем
  24. 	psort(A, N, compare);
  25.  
  26. 	//вывести отсортированный массив
  27. 	for(size_t j = 0; j < N; ++j){
  28. 		// для теста
  29. 		if(bfind(A, A + N, A[j], compare))
  30. 			std::cout << A[j] << ' ';
  31. 	}
  32. 	std::cout << std::endl;
  33.  
  34. 	// найти число X
  35. 	int X = 7;
  36. /*	
  37. 	std::cout << "Enter X: ";
  38. 	std::cin  >> X;
  39. 	std::cin.sync();
  40. */
  41. 	if(bfind(A, A + N, X, compare))
  42. 		std::cout << "Yes find." << std::endl;
  43. 	else
  44. 		std::cerr << "not found X!" << std::endl;
  45. 	return 0;
  46. }
  47.  
  48.  
  49. /* двоичный поиск ищет значение в упорядоченном 
  50.    массиве, значение x */
  51. bool bfind(const int* f, const int* l, int x, 
  52. 	       bool (*pcmp)(int, int)){
  53. 	size_t i, j, m;
  54. 	if((*pcmp)(x, *f) || (*pcmp)(*(l - 1), x))
  55. 		return false;
  56.  
  57. 	i = 0;
  58. 	j = (size_t)(l - f);
  59. 	while(i < j){
  60. 		m = (i + j) >> 1;
  61. 		if((*pcmp)(x, f[m]))
  62. 			j = m;
  63. 		else {
  64. 			if(x == f[m])
  65. 				return true;
  66. 			i = m + 1;
  67. 		}
  68. 	}
  69. 	return false;
  70. }
  71.  
  72. //---------------------------------------------
  73.  
  74. //восстановление свойства бинарной кучи
  75. void b_heapify(int* arr, size_t N, size_t i, 
  76. 	           bool (*pcmp)(int, int)) {
  77. 	size_t li, ri, big;
  78.  
  79. 	while(1){
  80. 		li = (i << 1) + 1;
  81. 		ri = (i << 1) + 2;
  82. 		if((li < N) && (*pcmp)(arr[i], arr[li]))
  83. 			big = li;
  84. 		else
  85. 			big = i;
  86.  
  87. 		if((ri < N) && (*pcmp)(arr[big], arr[ri]))
  88. 			big = ri;
  89.  
  90. 		if(big != i){
  91. 			std::swap(arr[big], arr[i]);
  92. 			i = big;
  93. 		} else
  94. 			break;
  95. 	}
  96. }
  97.  
  98. // пирамидальная сортировка
  99. void psort(int* arr, size_t N, bool (*pcmp)(int, int)){
  100. 	//собрать кучу
  101. 	for(size_t i = N >> 1; i > 0; --i) 
  102. 		b_heapify(arr, N, i, pcmp);
  103. 	b_heapify(arr, N, 0, pcmp);
  104.  
  105. 	for(size_t j = 0; j < N; ++j){
  106. 		std::swap(arr[0], arr[N - 1 - j]);
  107. 		b_heapify(arr, N - 1 - j, 0, pcmp);
  108. 	}
  109. }
Success #stdin #stdout 0s 3096KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3 6 7 5 3 5 6 2 9 1 2 7 0 9 3 6 0 6 2 6 
9 9 7 7 6 6 6 6 6 5 5 3 3 3 2 2 2 1 0 0 
Yes find.
https://ideone.com/HuaPtD
language:
C++ (gcc 8.3)
created:
8 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!