fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int numswap = 0;
  5. void swap(int a[], int i, int j)
  6. {
  7. 	int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
  8. 	numswap++;
  9. }
  10.  
  11. void minHeapify(int a[], int s, int elem)
  12. {
  13. 	int left = 2*elem + 1;
  14. 	int right = 2*elem + 2;
  15. 	int smallest = elem;
  16. 	if (left < s && a[smallest] > a[left])
  17. 		smallest = left;
  18. 	if (right < s && a[smallest] > a[right])
  19. 		smallest = right;
  20. 	if (smallest != elem)
  21. 	{
  22. 		swap(a,smallest,elem);
  23. 		minHeapify(a,s,smallest);
  24. 	}
  25. }
  26.  
  27. void buildHeap(int a[], int s)
  28. {
  29. 	for (int i = s/2; i >= 0; --i)
  30. 		minHeapify(a,s,i);
  31. }
  32.  
  33. void heapSort(int a[], int s)
  34. {
  35. 	buildHeap(a,s);
  36. 	for (int i=s-1; i>=1; --i)
  37. 	{
  38. 		swap(a,0,i);
  39. 		minHeapify(a,i,0);
  40. 	}
  41. }
  42.  
  43. const int SIZE = 1000000;
  44. int a[SIZE+1];
  45. void generate()
  46. {
  47. 	numswap = 0;
  48. 	for (int i=0; i<=SIZE; ++i)
  49. 		a[i] = rand() % 3000;
  50. }
  51.  
  52. void verify(int s)
  53. {
  54. 	for (int i=1; i<s; ++i)
  55. 		if (a[i-1] < a[i]) { printf("Invalid sort"); exit(-1); }
  56. }
  57.  
  58. int main() {
  59.  
  60. 	for (int i=10; i<=SIZE; i*=10)
  61. 	{
  62. 		generate();
  63. 		heapSort(a,i);
  64. 		//for (int j=0; j<i; ++j)
  65. 			//printf("%i ", a[j]);
  66. 		//printf("\n");
  67. 		verify(i);
  68. 		printf("Sorting %8i elements in %8i swaps\n", i, numswap);
  69. 	}
  70.  
  71. 	return 0;
  72. }
Success #stdin #stdout 0.43s 7200KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Sorting       10 elements in       28 swaps
Sorting      100 elements in      576 swaps
Sorting     1000 elements in     9071 swaps
Sorting    10000 elements in   124213 swaps
Sorting   100000 elements in  1574718 swaps
Sorting  1000000 elements in 19044820 swaps
https://ideone.com/3tZslM
heapsort
language:
C++14 (gcc 8.3)
created:
10 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!