Code

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct {
    int swaps;
    int calls;
} Counters;

typedef struct {
    char name[3];
    Counters c;
} Method;

// ===================== PIVOT AUX =====================
int pivotMedian3(int *array, int start, int end) {
    int n = end - start + 1;
    int i1 = start + n / 4;
    int i2 = start + n / 2;
    int i3 = start + 3 * n / 4;
    int a = array[i1], b = array[i2], cval = array[i3];
    if ((a >= b && a <= cval) || (a <= b && a >= cval)) return i1;
    else if ((b >= a && b <= cval) || (b <= a && b >= cval)) return i2;
    else return i3;
}

int pivotRandom(int start, int end) {
    return start + rand() % (end - start + 1);
}

// ===================== LOMUTO =====================
int lomuto(int *array, int start, int end, Counters *c) {
    int pivot = array[end], i = start - 1;
    for (int j = start; j < end; j++) {
        if (array[j] <= pivot) {
            i++;
            int tmp = array[i]; array[i] = array[j]; array[j] = tmp;
            c->swaps++;
        }
    }
    int tmp = array[i + 1]; array[i + 1] = array[end]; array[end] = tmp; c->swaps++;
    return i + 1;
}

int lomutoMedian3(int *array, int start, int end, Counters *c) {
    int pivotIndex = pivotMedian3(array, start, end);
    if (pivotIndex != end) { int tmp = array[pivotIndex]; array[pivotIndex] = array[end]; array[end] = tmp; c->swaps++; }
    return lomuto(array, start, end, c);
}

int lomutoRandom(int *array, int start, int end, Counters *c) {
    int pivotIndex = pivotRandom(start, end);
    int tmp = array[end]; array[end] = array[pivotIndex]; array[pivotIndex] = tmp; c->swaps++;
    return lomuto(array, start, end, c);
}

void quickSortLomutoStandard(int *array, int start, int end, Counters *c) {
    c->calls++;
    if (start < end) {
        int p = lomuto(array, start, end, c);
        quickSortLomutoStandard(array, start, p - 1, c);
        quickSortLomutoStandard(array, p + 1, end, c);
    }
}

void quickSortLomutoMedian3(int *array, int start, int end, Counters *c) {
    c->calls++;
    if (start < end) {
        int p = lomutoMedian3(array, start, end, c);
        quickSortLomutoMedian3(array, start, p - 1, c);
        quickSortLomutoMedian3(array, p + 1, end, c);
    }
}

void quickSortLomutoRandom(int *array, int start, int end, Counters *c) {
    c->calls++;
    if (start < end) {
        int p = lomutoRandom(array, start, end, c);
        quickSortLomutoRandom(array, start, p - 1, c);
        quickSortLomutoRandom(array, p + 1, end, c);
    }
}

// ===================== HOARE =====================
int hoare(int *array, int start, int end, Counters *c) {
    int pivot = array[start], i = start - 1, j = end + 1;
    while (1) {
        do { j--; } while (array[j] > pivot);
        do { i++; } while (array[i] < pivot);
        if (i < j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; c->swaps++; }
        else return j;
    }
}

int hoareMedian3(int *array, int start, int end, Counters *c) {
    int pivotIndex = pivotMedian3(array, start, end);
    if (pivotIndex != start) { int tmp = array[start]; array[start] = array[pivotIndex]; array[pivotIndex] = tmp; c->swaps++; }
    return hoare(array, start, end, c);
}

int hoareRandom(int *array, int start, int end, Counters *c) {
    int pivotIndex = pivotRandom(start, end);
    int tmp = array[start]; array[start] = array[pivotIndex]; array[pivotIndex] = tmp; c->swaps++;
    return hoare(array, start, end, c);
}

void quickSortHoareStandard(int *array, int start, int end, Counters *c) {
    c->calls++;
    if (start < end) {
        int p = hoare(array, start, end, c);
        quickSortHoareStandard(array, start, p, c);
        quickSortHoareStandard(array, p + 1, end, c);
    }
}

void quickSortHoareMedian3(int *array, int start, int end, Counters *c) {
    c->calls++;
    if (start < end) {
        int p = hoareMedian3(array, start, end, c);
        quickSortHoareMedian3(array, start, p, c);
        quickSortHoareMedian3(array, p + 1, end, c);
    }
}

void quickSortHoareRandom(int *array, int start, int end, Counters *c) {
    c->calls++;
    if (start < end) {
        int p = hoareRandom(array, start, end, c);
        quickSortHoareRandom(array, start, p, c);
        quickSortHoareRandom(array, p + 1, end, c);
    }
}

// ===================== UTIL =====================
void copyArray(int *src, int *dest, int n) {
    for (int i = 0; i < n; i++) dest[i] = src[i];
}

// ===================== MAIN =====================
int main(int argc, char *argv[]) {
    if (argc < 3) {
        printf("Uso: %s <input> <output>\n", argv[0]);
        return 1;
    }

    srand((unsigned int)time(NULL));

    FILE *fin = fopen(argv[1], "r");
    if (!fin) { perror("Erro ao abrir input"); return 1; }

    FILE *fout = fopen(argv[2], "w");
    if (!fout) { perror("Erro ao abrir output"); fclose(fin); return 1; }

    int totalArrays;
    fscanf(fin, "%d", &totalArrays);

    for (int t = 0; t < totalArrays; t++) {
        int size;
        fscanf(fin, "%d", &size);

        int *original = malloc(size * sizeof(int));
        int *array = malloc(size * sizeof(int));

        for (int i = 0; i < size; i++) fscanf(fin, "%d", &original[i]);

        Method methods[6] = { {"LP"}, {"LM"}, {"LA"}, {"HP"}, {"HM"}, {"HA"} };

        copyArray(original, array, size); quickSortLomutoStandard(array, 0, size - 1, &methods[0].c);
        copyArray(original, array, size); quickSortLomutoMedian3(array, 0, size - 1, &methods[1].c);
        copyArray(original, array, size); quickSortLomutoRandom(array, 0, size - 1, &methods[2].c);
        copyArray(original, array, size); quickSortHoareStandard(array, 0, size - 1, &methods[3].c);
        copyArray(original, array, size); quickSortHoareMedian3(array, 0, size - 1, &methods[4].c);
        copyArray(original, array, size); quickSortHoareRandom(array, 0, size - 1, &methods[5].c);

        // ordena pelo total
        for (int i = 1; i < 6; i++) {
            Method key = methods[i];
            int keyVal = key.c.calls + key.c.swaps;
            int j = i - 1;
            while (j >= 0 && (methods[j].c.calls + methods[j].c.swaps) > keyVal) {
                methods[j + 1] = methods[j];
                j--;
            }
            methods[j + 1] = key;
        }

        fprintf(fout, "[%d]:", size);
        for (int i = 0; i < 6; i++) {
            fprintf(fout, "%s(%d)%s", methods[i].name, methods[i].c.calls + methods[i].c.swaps, (i < 5 ? "," : ""));
        }
        fprintf(fout, "\n");

        free(original);
        free(array);
    }

    fclose(fin);
    fclose(fout);
    return 0;
}