main
#include “order.hpp”
int main() {
srand(time(NULL));
int n;
char c;
cin >> n >> c;
if (c == ‘h’ || c == ‘H’) {
int *a = new int [n];
for (int i = 0; i < n; i++){
int x = rand() % (10*n) + 1;
a[i] = x;
}
cout << “Array: n”;
cout << “[ “;
for (int i = 0; i < n; i++) cout << a[i] <<” “;
cout << “]n”;
order m(n);
for (int i = 0; i < n; i++){
m.hins(a[i]);
}
cout << “Heapsorted array: n”;
m.hSort();
m.print();
} else if (c == ‘q’ || c == ‘Q’) {
cout << “Prueba de Q”;
int *a = new int [n];
for (int i = 0; i < n; i++){
int x = rand() % (10*n) + 1;
a[i] = x;
}
cout << “Array: n”;
cout << “[ “;
for (int i = 0; i < n; i++) cout << a[i] <<” “;
cout << “]n”;
cout << “Qsorted array: n”;
//m.mSort();
m.print();
} else if (c == ‘m’ || c == ‘M’) {
int *a = new int [n];
for (int i = 0; i < n; i++){
int x = rand() % (10*n) + 1;
a[i] = x;
}
cout << “Array: n”;
cout << “[ “;
for (int i = 0; i < n; i++) cout << a[i] <<” “;
cout << “]n”;
cout << “Mergesorted array: n”;
//m.mSort();
m.print();
}
return 0;
}
order.cpp
order::order(int c){
n = c;
s = 0;
a = new int[n];
}
order::~order(){
delete[] a;
}
void order::hins(int x){
assert(!full());
a[s] = x;
int i = s++;
while (i > 0 && a[i] > a[parent(i)]) {
int c = a[i];
a[i] = a[parent(i)];
a[parent(i)] = c;
i = parent(i);
}
}
int order::maxChild(int i) {
assert(i < parent(s));
if (right(i) > s) return left(i);
if (a[left(i)] > a[right(i)]) { return left(i); }
else return right(i);
}
void order::print(){
cout << “[ “;
for (int i = 0; i < s; i++) cout << a[i] <<” “;
cout << “]n”;
}
void order::hSort() {
int k = s;
while (k > 0) {
swap(a[0], a[–k]);
int i = 0;
while ( i < parent(k) and a[i] < a[maxChild(i)] ) {
int m = maxChild(i);
swap(a[i], a[m]);
i = m;
}
}
if (a[0] > a[1]) swap(a[0], a[1]);
}
/*
void order::merge() {
int *c = new int[n+m];
int i = 0, j = 0, k = 0;
while (i < n && j < m) c[k++] = a[i] < b[j] ? a[i++] : b[j++];
while (i < n) c[k++] = a[i++];
while (j < m) c[k++] = b[j++];
}
void order::mSort() {
if (s > 0) {
int k = s/2;
int *a = new int [k];
int *b = new int [k];
mSort(a);
mSort(b);
int *c = merge(a,b);
}
}
*/
order.hpp
#define order_hpp
#include <stdio.h>
#include <iostream>
#include <cassert>
using namespace std;
class order {
int parent(int i) { return (i – 1) / 2; }
int left(int i) { return 2 * i + 1; }
int right(int i) { return 2 * i + 2; }
int n; // capacidad
int s; // tamaño
int *a; // arreglo
public:
order(int);
~order();
void hins(int);
int maxChild(int);
void hSort();
void mSort();
void merge();
void qSort();
int capacity() const { return n; }
int size() const { return s; }
bool empty() const { return s == 0; }
bool full() const { return s == n; }
void print();
};
#endif /* order_hpp */
