online compiler and debugger for c/c++

#include <stdio.h> #include <time.h> #include <stdlib.h> #include <limits.h> #include <string.h> #include <chrono> #include <unistd.h> #include <iostream> using namespace std; int *v, *v1, *v2, *v3, *v4, *v5, *v6, *v7; //------------------------------------------------------------------------------------- void bubbleSort (int v[], int n) { bool trocou; int k = n; do { trocou = false; k--; for (int i = 0; i < k; i++) if (v[i + 1] < v[i]) { int aux = v[i + 1]; v[i + 1] = v[i]; v[i] = aux; trocou = true; } } while (trocou); } //------------------------------------------------------------------------------------- void insertionSort (int v[], int n) { int i, j, chave; for (j = 1; j < n; j++) { chave = v[j]; i = j - 1; while (i >= 0 && v[i] > chave) { v[i + 1] = v[i]; i--; } v[i + 1] = chave; } } //------------------------------------------------------------------------------------- void selectionSort (int v[], int n) { int i, j, min; for (i = 0; i < n - 1; i++) { min = i; for (j = i + 1; j < n; j++) if (v[j] < v[min]) min = j; if (min != i) { int temp = v[min]; v[min] = v[i]; v[i] = temp; } } } //------------------------------------------------------------------------------------- void shellSort (int v[], int n) { int i, j, valor; int h = 1; while (h < n) { h = 3 * h + 1; } while (h > 1) { h /= 3; for (i = h; i < n; i++) { valor = v[i]; j = i - h; while (j >= 0 && valor < v[j]) { v[j + h] = v[j]; j -= h; } v[j + h] = valor; } } } //------------------------------------------------------------------------------------- void quickSort1 (int v[], int ini, int fim) { int i = ini; int j = fim; int pivo = v[(ini + fim) / 2]; // Pivo e o elemento central do { while (v[i] < pivo && i < fim) i++; while (pivo < v[j] && j > ini) j--; if (i <= j) { int aux = v[i]; v[i] = v[j]; v[j] = aux; i++; j--; } } while (i <= j); if (ini < j) quickSort1 (v, ini, j); if (i < fim) quickSort1 (v, i, fim); } void quickSort (int v[], int tam) { quickSort1 (v, 0, tam - 1); } //------------------------------------------------------------------------------------- void intercala (int v[], int aux[], int ini, int meio, int fim) { int i = ini, j = fim, k; for (k = ini; k <= meio; k++) aux[k] = v[k]; for (k = meio + 1; k <= fim; k++) aux[fim + meio + 1 - k] = v[k]; for (k = ini; k <= fim; k++) if (aux[i] <= aux[j]) v[k] = aux[i++]; else v[k] = aux[j--]; } void mergeSort1 (int v[], int aux[], int ini, int fim) { if (ini < fim) { int meio = (ini + fim) / 2; mergeSort1 (v, aux, ini, meio); mergeSort1 (v, aux, meio + 1, fim); intercala (v, aux, ini, meio, fim); } } void mergeSort (int v[], int n) { int *aux = (int *) malloc (n * sizeof (int)); mergeSort1 (v, aux, 0, n - 1); free (aux); } //------------------------------------------------------------------------------------- int getMax (int v[], int tam) { int max = v[0]; for (int i = 1; i < tam; i++) if (v[i] > max) max = v[i]; return max; } void countSort (int v[], int tam, int exp) { int output[tam], i, count[10] = { 0 }; for (i = 0; i < tam; i++) count[(v[i] / exp) % 10]++; for (i = 1; i < 10; i++) count[i] += count[i - 1]; for (i = tam - 1; i >= 0; i--) { output[count[(v[i] / exp) % 10] - 1] = v[i]; count[(v[i] / exp) % 10]--; } for (i = 0; i < tam; i++) v[i] = output[i]; } void radixsort (int v[], int tam) { int exp, m; m = getMax (v, tam); for (exp = 1; m / exp > 0; exp *= 10) countSort (v, tam, exp); } //------------------------------------------------------------------------------------- void gerar (int v[], int tam) { srand ((unsigned int) time (NULL)); for (int i = 0; i < tam; i++) v[i] = rand () % 100000001; } //------------------------------------------------------------------------------------- void copiar (int origem[], int destino[], int n) { for (int i = 0; i < n; i++) destino[i] = origem[i]; } //------------------------------------------------------------------------------------- bool verifica (int v[], int n) { for (int i = 0; i < n - 1; i++) if (v[i] > v[i + 1]) return false; return true; } //------------------------------------------------------------------------------------- void inverte (int v[], int n) { for (int i = 0, j = n - 1; i < n / 2; i++, j--) v[i] = v[j]; } //------------------------------------------------------------------------------------- int main (void) { chrono::steady_clock::time_point start, end; long double cpu_time; int tam, iter; char metodos[100]; long double tempo[] = { 0, 0, 0, 0, 0, 0 }; tam = 0; printf ("Quantos numeros? "); scanf ("%d", &tam); getchar (); if (tam <= 0) return 0; printf ("Selecione os metodos:\n 1-Bubble sort\n 2-Selection sort\n 3-Insertion sort\n 4-Shell sort\n 5-Quicksort\n 6-Mergesort\n 7-Radix sort\nMetodos: "); gets (metodos); printf ("Quantas execucoes (1, 2, 3, ...)? "); scanf ("%d", &iter); getchar (); if (iter <= 0) return 0; v = (int *) malloc (tam * sizeof (int)); v1 = (int *) malloc (tam * sizeof (int)); v2 = (int *) malloc (tam * sizeof (int)); v3 = (int *) malloc (tam * sizeof (int)); v4 = (int *) malloc (tam * sizeof (int)); v5 = (int *) malloc (tam * sizeof (int)); v6 = (int *) malloc (tam * sizeof (int)); v7 = (int *) malloc (tam * sizeof (int)); for (int i = 1; i <= iter; i++) { printf ("------------------------------------------------\nExecucao %d:\n------------------------------------------------\n", i); printf ("Gerando %d elementos...\n", tam); gerar (v, tam); copiar (v, v1, tam); copiar (v, v2, tam); copiar (v, v3, tam); copiar (v, v4, tam); copiar (v, v5, tam); copiar (v, v6, tam); copiar (v, v7, tam); // bubble if (strchr (metodos, '1') != NULL) { printf ("Bubble sort...\n"); start = chrono::steady_clock::now (); bubbleSort (v1, tam); end = chrono::steady_clock::now (); cpu_time = chrono::duration_cast < chrono::nanoseconds > (end - start).count () / (long double) 1000000.0; printf ("%s. Tempo: %lf ms (%lf s)\n", verifica (v1, tam) ? "OK" : "ERRO", cpu_time, cpu_time / 1000); tempo[0] += cpu_time; } // selection if (strchr (metodos, '2') != NULL) { printf ("Selection sort...\n"); start = chrono::steady_clock::now (); selectionSort (v3, tam); end = chrono::steady_clock::now (); cpu_time = chrono::duration_cast < chrono::nanoseconds > (end - start).count () / (long double) 1000000.0; printf ("%s. Tempo: %lf ms (%lf s)\n", verifica (v3, tam) ? "OK" : "ERRO", cpu_time, cpu_time / 1000); tempo[1] += cpu_time; } // insertion if (strchr (metodos, '3') != NULL) { printf ("Insertion sort...\n"); start = chrono::steady_clock::now (); insertionSort (v2, tam); end = chrono::steady_clock::now (); cpu_time = chrono::duration_cast < chrono::nanoseconds > (end - start).count () / (long double) 1000000.0; printf ("%s. Tempo: %lf ms (%lf s)\n", verifica (v2, tam) ? "OK" : "ERRO", cpu_time, cpu_time / 1000); tempo[2] += cpu_time; } // shell if (strchr (metodos, '4') != NULL) { printf ("Shell sort...\n"); start = chrono::steady_clock::now (); shellSort (v4, tam); end = chrono::steady_clock::now (); cpu_time = chrono::duration_cast < chrono::nanoseconds > (end - start).count () / (long double) 1000000.0; printf ("%s. Tempo: %lf ms (%lf s)\n", verifica (v4, tam) ? "OK" : "ERRO", cpu_time, cpu_time / 1000); tempo[3] += cpu_time; } // quick if (strchr (metodos, '5') != NULL) { printf ("Quick sort...\n"); start = chrono::steady_clock::now (); quickSort (v5, tam); end = chrono::steady_clock::now (); cpu_time = chrono::duration_cast < chrono::nanoseconds > (end - start).count () / (long double) 1000000.0; printf ("%s. Tempo: %lf ms (%lf s)\n", verifica (v5, tam) ? "OK" : "ERRO", cpu_time, cpu_time / 1000); tempo[4] += cpu_time; } // merge if (strchr (metodos, '6') != NULL) { printf ("Merge sort...\n"); start = chrono::steady_clock::now (); mergeSort (v6, tam); end = chrono::steady_clock::now (); cpu_time = chrono::duration_cast < chrono::nanoseconds > (end - start).count () / (long double) 1000000.0; printf ("%s. Tempo: %lf ms (%lf s)\n", verifica (v6, tam) ? "OK" : "ERRO", cpu_time, cpu_time / 1000); tempo[5] += cpu_time; } //radixsort if (strchr (metodos, '7') != NULL) { printf ("Radix sort...\n"); start = chrono::steady_clock::now (); radixsort (v7, tam); end = chrono::steady_clock::now (); cpu_time = chrono::duration_cast < chrono::nanoseconds > (end - start).count () / (long double) 1000000.0; printf ("%s. Tempo: %lf ms (%lf s)\n", verifica (v7, tam) ? "OK" : "ERRO", cpu_time, cpu_time / 1000); tempo[6] += cpu_time; } } if (iter > 1) { printf ("-------------------------------------------\nTempos medios:\n"); if (strchr (metodos, '1') != NULL) printf ("Bubble sort: %lf ms (%lf s)\n", tempo[0] / iter, tempo[0] / (iter * 1000)); if (strchr (metodos, '2') != NULL) printf ("selection sort: %lf ms (%lf s)\n", tempo[1] / iter, tempo[1] / (iter * 1000)); if (strchr (metodos, '3') != NULL) printf ("Insertion sort: %lf ms (%lf s)\n", tempo[2] / iter, tempo[2] / (iter * 1000)); if (strchr (metodos, '4') != NULL) printf ("Shell sort: %lf ms (%lf s)\n", tempo[3] / iter, tempo[3] / (iter * 1000)); if (strchr (metodos, '5') != NULL) printf ("Quick sort: %lf ms (%lf s)\n", tempo[4] / iter, tempo[4] / (iter * 1000)); if (strchr (metodos, '6') != NULL) printf ("Merge sort: %lf ms (%lf s)\n", tempo[5] / iter, tempo[5] / (iter * 1000)); if (strchr (metodos, '7') != NULL) printf ("Radix sort: %lf ms (%lf s)\n", tempo[6] / iter, tempo[6] / (iter * 1000)); } free (v); free (v1); free (v2); free (v3); free (v4); free (v5); free (v6); free (v7); }