Сортировка слишком медленная

Question

Итак, я делаю проект для своего класса языков программирования, и мне нужно создать структуру, отсортировать ее, а затем показать время, необходимое для ее выполнения, это сортировка пузырьков (случай 1) требуется 60 секунд, вставка (случай 2) 5 секунд, а выбор (случай 4) занимает 10 секунд. Все это сортирует 100000 элементов. shell принимает только 0,03, поэтому я начал думать, что у меня могут быть что-то неправильно с моими алгоритмами. Кто-нибудь может мне помочь?

void ordenesc(compleja * vd, int tam) 
    { 
    int i=0,j=0,k=0,aux=0,op=0,inc=0,minimo=0; 
    char auxcad[20]; 
    clock_t start, end; 
    double tiempo; 

    op=menus(3); 
    start = clock(); 
    switch(op) 
    { 
     case 1://Burbujeo 
      for(i=1;i<=tam;i++) 
      { 
       for(j=0;j<tam-1;j++) 
       { 
        if(vd[j].nro>vd[j+1].nro) 
        { 
         aux=vd[j].nro; 
         vd[j].nro=vd[j+1].nro; 
         vd[j+1].nro=aux; 
         strcpy(auxcad,vd[j].cad); 
         strcpy(vd[j].cad,vd[j+1].cad); 
         strcpy(vd[j+1].cad,auxcad); 
        } 

       } 
      } 
      break; 

     case 2://Inserccion 
      for(i = 1; i < tam; i++) 
      { 
       aux=vd[i].nro; 
       strcpy(auxcad,vd[i].cad); 
       for (j = i - 1; j >= 0 && vd[j].nro > aux; j--) 
       { 
        vd[j+1].nro=vd[j].nro; 
        strcpy(vd[j+1].cad,vd[j].cad); 
        j--; 
       } 
        vd[j+1].nro=aux; 
        strcpy(vd[j+1].cad,auxcad); 
      } 
      break; 
        case 3://Shell 
       inc=(tam/2); 
       while (inc > 0) 
       { 
        for (i=0; i < tam; i++) 
        { 
         j = i; 
         aux = vd[i].nro; 
         strcpy(auxcad,vd[i].cad); 
         while ((j >= inc) && (vd[j-inc].nro > aux)) 
         { 
         vd[j].nro = vd[j - inc].nro; 
         strcpy(vd[j].cad,vd[j-inc].cad); 
         j = j - inc; 
         } 
        vd[j].nro = aux; 
        strcpy(vd[j].cad,auxcad); 
        } 
        if (inc == 2) 
         inc = 1; 
        else 
         inc = inc * 5/11; 
        } 
       break; 
     case 4://Seleccion 
      for(i=0;i<tam-1;i++) 
      { 
       minimo=i; 
       for(j=i+1;j<tam;j++) 
       { 
        if(vd[minimo].nro > vd[j].nro) minimo=j; 
       } 
       aux=vd[minimo].nro; 
       vd[minimo].nro=vd[i].nro; 
       vd[i].nro=aux; 
       strcpy(auxcad,vd[minimo].cad); 
       strcpy(vd[minimo].cad,vd[i].cad); 
       strcpy(vd[i].cad,auxcad); 
      } 
      break; 

     case 9: 
      break; 

     default: 
      break; 
     } 
    end = clock(); 
    tiempo = ((double) (end - start))/CLOCKS_PER_SEC; 
    //system("cls"); 
    i=0; 
    for(i=0;i<tam;i++){ 
    printf("%d %s \n",vd[i].nro,vd[i].cad);} 
    printf("\n Tardo %f segundos \n", tiempo); 
    return; 
} 

P.d: редактировали текст извините за мой английский не мой первый язык, и мой мозг не удается из-за этого.

Answer 1

Чтобы убедиться, что алгоритм сортировки работает так, как ожидалось, вы можете добавить проверку в конечный цикл, чтобы элементы были упорядочены при их печати. Его относительно маловероятно, что в алгоритме есть фундаментальная ошибка, и он все еще правильно сортируется.

Одним из пунктов упражнения может быть показать, что алгоритмы сортировки действительно имеют значение, а выбор сортировки - это единственный алгоритм, который имеет лучшую производительность, чем O (n^2) в вашем списке. Поэтому я не был бы слишком удивлен широкими различиями в производительности.

Одним из улучшений, которые можно сделать для создания пузырьков, является то, что вам нужно только перебирать элементы i во внутреннем цикле (вместо tam), так как i-самый большой элемент будет вспучиваться во всем внутреннем цикле.

Другим усовершенствованием может быть просто копирование указателей вместо содержимого массивов символов, например.

вместо

char auxcad[20]; 

... 

strcpy(auxcad, vd[j].cad); 
strcpy(vd[j].cad, vd[j+1].cad); 
strcpy(vd[j+1].cad, auxcad); 

вы можете написать

char* auxcad; 

... 

auxcad = vd[j].cad; 
vd[j].cad = vd[j+1].cad; 
vd[j+1].cad = auxcad;