algoritmo

main.cpp

#include <iostream>
#include "heap.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.ins(a[i]);
      }

        cout << "Heapsorted array: \n";
        m.hSort();
        m.print();

    } else if (c == 'q' || c == 'Q') {

        cout << "Prueba de Q";



    } 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";

      order m(n);

      for (int i = 0; i < n; i++){
        m.ins(a[i]);
      }

        cout << "Heapsorted array: \n";

        m.mSort();
        m.print();

    } 

    return 0;

}

order.cpp

#include "order.hpp"

  order::order(int c){
    n = c;
    s = 0;
    a = new int[n];
  }

  order::~order(){

    delete[] a;
  }

 void order::ins(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

#include "order.hpp"

  order::order(int c){
    n = c;
    s = 0;
    a = new int[n];
  }

  order::~order(){

    delete[] a;
  }

 void order::ins(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);

    }
}

Blog

Leo

Join Our Newsletter. No Spam, Only the good stuff.

Related