Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- class List {
- public:
- int value;
- class List *next, *prev;
- List() {
- this->value = 0;
- this->next = NULL;
- this->prev = NULL;
- };
- int pop() {
- List *aux = this;
- while (aux->next->next != NULL)
- aux = aux->next;
- int last = aux->next->value;
- delete aux->next;
- aux->next = NULL;
- return last;
- };
- void print() {
- List *aux = this;
- while (aux != NULL) {
- if (aux->value > 0)
- printf("%d", aux->value);
- if (aux->next != NULL)
- printf(" ");
- aux = aux->next;
- }
- };
- void push(int v) {
- if (this->next == NULL && this->value == 0) {
- this->value = v;
- return;
- }
- List *aux = this;
- while (aux->next != NULL)
- aux = aux->next;
- List *l = new List();
- l->value = v;
- l->prev = aux;
- l->next = NULL;
- aux->next = l;
- };
- };
- int getSize(List *lista) {
- float size = 0;
- List *aux = lista;
- while (aux != NULL) {
- aux = aux->next;
- size++;
- }
- return size;
- }
- List *mergeSort(List *lista) {
- float size = getSize(lista);
- List *aux;
- aux = lista;
- List *init = new List();
- List *end = new List();
- if (size < 2)
- return aux;
- if (size < 3) {
- if (aux->value > aux->next->value) {
- init->push(aux->next->value);
- init->push(aux->value);
- return init;
- }
- return aux;
- }
- int i = 1;
- while (i < size + 1 && aux != NULL) {
- if (i <= size / 2)
- init->push(aux->value);
- else
- end->push(aux->value);
- aux = aux->next;
- i++;
- }
- init = mergeSort(init);
- end = mergeSort(end);
- List *result = new List();
- while (init != NULL && end != NULL) {
- if (init->value < end->value) {
- result->push(init->value);
- init = init->next;
- } else {
- result->push(end->value);
- end = end->next;
- }
- }
- while (init != NULL) {
- result->push(init->value);
- init = init->next;
- }
- while (end != NULL) {
- result->push(end->value);
- end = end->next;
- }
- return result;
- }
- int main() {
- List *lista = new List();
- int n;
- while (scanf("%d", &n) != EOF) {
- if (n <= 100000)
- lista->push(n);
- }
- lista = mergeSort(lista);
- lista->print();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement