Gerar caso de teste para IntroSort

[bcribas]

Falta um conjunto de testes que faça as implemetações do introsort migrarem de algoritmo.

[CauaMatheus]

Não consegui fazer em shellscript, mas fiz em c um algoritmo que gera sempre o pior caso do quicksort com mediana de 3.

Se for útil, o código está aqui para o senhor analisar e em qualquer caso, podemos prosseguir com otimizações ou traduções para inserir ao conjunto de entradas:

A ideia é simples, de acordo com um vetor com números desconhecidos, a gente escolhe os piores pivores, faz os 4 swaps que o quicksort faria e vai seguindo assim, escolhendo sempre os piores pivores. Ao final, basta ordenar pelo indice inicial e sabemos qual é o vetor original que geraria esse pior caso.

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

typedef struct {
  int index;
  int value;
} Item;

#define swap(A, B) {Item tmp = A; A = B; B = tmp;}

int compare(const void*a, const void*b) {
  return ((Item*)a)->index - ((Item*)b)->index;
}

int main() {
  int n;
  scanf("%d", &n);
  if((n & 1) == 0) {
    n++;
  }

  Item *values = malloc(sizeof(Item) * n);
  for(int i = 0; i < n; i++) {
    values[i].index = i;
  }
  values[0].value = n;

  for(int i = n; i > 1; i -= 2) {
    values[i/2].value = i-1;
    values[i-1].value = i-2;

    swap(values[i/2], values[i-1]);
    swap(values[i/2], values[0]);
    swap(values[i-2], values[i/2]);
    swap(values[i-2], values[i-1]);
  }

  qsort(values, n, sizeof(Item), compare);
  printf("%d\n%d", n, values[0].value);
  for(int i = 1; i < n; i++) {
    printf(" %d", values[i].value);
  }
  printf("\n");
}