Created
February 25, 2018 18:17
-
-
Save ckalbas/fa993a0bcfb4fe7271ef67c4e50a9a57 to your computer and use it in GitHub Desktop.
Heapsort algorithm using recursive and loop solutions in C++
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <iostream> | |
#define LENGTH 10 | |
int heapSize = 0; | |
using namespace std; | |
void Exchange(int* A, int a, int b) | |
{ | |
int temp = A[a]; | |
A[a] = A[b]; | |
A[b] = temp; | |
} | |
void MaxHeapify(int* A, int i) | |
{ | |
while (i <= heapSize) { | |
int left = i*2; | |
int right = left+1; | |
int largest = 0; | |
if (left <= heapSize && A[left] > A[i]) | |
{ | |
largest = left; | |
} | |
else { | |
largest = i; | |
} | |
if (right <= heapSize && A[right] > A[largest]){ | |
largest = right; | |
} | |
if (largest != i) { | |
Exchange(A, largest, i); | |
i = largest; | |
}else { | |
break; | |
} | |
} | |
} | |
void BuildMaxHeap(int* A) | |
{ | |
heapSize = LENGTH-1; | |
for (int i = heapSize/2; i >= 0; i--) | |
{ | |
MaxHeapify(A, i); | |
} | |
} | |
void HeapSort(int* A) | |
{ | |
BuildMaxHeap(A); | |
for (int i = LENGTH -1; i > 0; i--) | |
{ | |
Exchange(A, i, 0); | |
heapSize--; | |
MaxHeapify(A, 0); | |
} | |
} | |
int main() { | |
int test[LENGTH] = {1, 20, 13, 7, 9, 8, 5, 11, 2, 3}; | |
HeapSort(test); | |
for (int i = 0; i <= LENGTH -1; i++) | |
{ | |
cout << test[i] << ' '; | |
} | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <iostream> | |
#define LENGTH 10 | |
int heapSize = 0; | |
using namespace std; | |
void Exchange(int* A, int a, int b) | |
{ | |
int temp = A[a]; | |
A[a] = A[b]; | |
A[b] = temp; | |
} | |
void MaxHeapify(int* A, int i) | |
{ | |
int left = i*2; | |
int right = left+1; | |
int largest = 0; | |
if (left <= heapSize && A[left] > A[i]) { | |
largest = left; | |
} else { | |
largest = i; | |
} | |
if (right <= heapSize && A[right] > A[largest]) { | |
largest = right; | |
} | |
if (largest != i) { | |
Exchange(A, largest, i); | |
MaxHeapify(A, largest); | |
} | |
} | |
void BuildMaxHeap(int* A) | |
{ | |
heapSize = LENGTH-1; | |
for (int i = heapSize/2; i >= 0; i--) | |
{ | |
MaxHeapify(A, i); | |
} | |
} | |
void HeapSort(int* A) | |
{ | |
BuildMaxHeap(A); | |
for (int i = LENGTH -1; i > 0; i--) | |
{ | |
Exchange(A, i, 0); | |
heapSize--; | |
MaxHeapify(A, 0); | |
} | |
} | |
int main() { | |
int test[LENGTH] = {1, 20, 13, 7, 9, 8, 5, 11, 2, 3}; | |
HeapSort(test); | |
for (int i = 0; i <= LENGTH -1; i++) | |
{ | |
cout << test[i] << ' '; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment