fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void swap(int *a, int i, int j){
  5. 	if(a[i] ^ a[j]){
  6. 		a[i] ^= a[j];
  7. 		a[j] ^= a[i];
  8. 		a[i] ^= a[j];
  9. 	}
  10. }
  11.  
  12. void heapify(int *a, int i, int n){
  13.     int large, l, r;
  14.  
  15.     while(i < n){
  16.     	large = i;
  17.     	l = 2 * i + 1, r = l + 1;
  18.  
  19. 	    if(l < n && a[l] > a[large])
  20. 	        large = l;
  21.  
  22. 	    if(r < n && a[r] > a[large])
  23. 	        large = r;
  24.  
  25. 	    if(large ^ i){
  26. 	        swap(a, i, large);
  27. 	        i = large;
  28. 	    }
  29. 	    else{
  30. 	    	break;
  31. 	    }
  32.     }
  33. }
  34.  
  35. void heapSort(int *a, int n){
  36.  
  37.     for(int i = n/2-1; i > -1; --i)
  38.         heapify(a, i, n);
  39.  
  40.     for(int i = n-1; i > 0; --i){
  41.         swap(a, 0, i);
  42.  
  43.         cout<<"[";
  44.         for(int j = 0; j < i+1; ++j)
  45.             cout<<a[j]<<(j != i ? "," : "");
  46.         cout<<"]\n";
  47.  
  48.         heapify(a, 0, i);
  49.     }
  50. }
  51.  
  52. int main() {
  53.     int n; cin>>n;
  54.  
  55.     int a[n];
  56.  
  57.     for(int i=0; i<n; ++i)
  58.         cin>>a[i];
  59.  
  60.     heapSort(a, n);
  61.  
  62.     cout<<"[";
  63.     for(int i = 0; i < n; ++i)
  64.         cout<<a[i]<<(i != n-1 ? "," : "");
  65.     cout<<"]";
  66.  
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0s 4512KB
comments (?)
stdin
copy 
10
5 3 2 1 4 9 7 6 8 10
stdout
copy 
[3,8,9,6,4,2,7,5,1,10]
[1,8,7,6,4,2,3,5,9]
[1,6,7,5,4,2,3,8]
[1,6,3,5,4,2,7]
[2,5,3,1,4,6]
[2,4,3,1,5]
[1,2,3,4]
[1,2,3]
[1,2]
[1,2,3,4,5,6,7,8,9,10]
https://ideone.com/bDpFMw
Heap Sort C++ || Time complexity: O(n log n)
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

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!