Модификация метода сортировки в программе, на Си Опции

[Quant]

Подскажите пожалуйста еще как эту программу можно модифицировать из сортировки пузырьком в такую, чтобы ее оценка эффективности была примерно [n(n-1)]/2...ну тут же сортируется, только вот я недопонимаю как пределать хотя вроде говорят немного... вся прога прилагается

Код

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <signal.h>
#include <string.h>
#include <stdlib.h>

typedef struct _list {
    char s[81];
    struct _list *next;
} list;

list *head = NULL;
int count = 0;
pthread_t pt;
int exit_status = 0;

//--------------------------------------------------------------------------------------------------------------------------
void printlist()
{
    list *curr = head;
    
    printf("//---------List:\n");
    while (curr) {
     printf("%s\n", curr->s);
     curr = curr->next;
    }
    printf("---------------//\n");
}

int oins(list *head, list *item)
{
    int i = 0;
    list *curr = head, *prev = NULL;
    
    if (!head)
     return (0);
    while (curr && (strcmp(item->s, curr->s) > 0)) {
     prev = curr;
     curr = curr->next;
     i++;
    }

    if (prev) {
     prev->next = item;
     item->next = curr;
    }
    return (i);
}

void vesicule()
{
    list *prev, *curr;
    int i;
    
//    if (!head) {
//     count = 0;
//     return;
//    }
//    for (i = 0; i < count; i++) {
//     prev = NULL;
//     curr = head;
     while (curr && curr->next) {
         if (strcmp(curr->s, curr->next->s) > 0) {
          if (prev) {
              prev->next = curr->next;
          } else {
              head = head->next;
          }
          oins(curr->next, curr);
         }
             prev = curr;
         curr = curr->next;
     }
    }
//    count = 0;
//}
//--------------------------------------------------------------------------------------------------------------------------

pthread_mutex_t mut = PTHREAD_MUTEX_INITIALIZER;

void* pthread_proc(void *p)
{
    while (1) {    
     sleep(5);
     pthread_mutex_lock(&mut);
        
     if (head) {
         vesicule();        
     }
    
     pthread_mutex_unlock(&mut);
    }
    return (NULL);
}

void sigint(int a)
{
    if (a == SIGINT) {
     exit_status = 1;
    }
}

void insert(char *s)
{
    list *curr;

    pthread_mutex_lock(&mut);
    curr = (list *)malloc(sizeof(list));
    if (!curr) {
     printf("malloc error.\n");
    } else {
     strncpy(curr->s, s, 80);
     curr->next = head;
     head = curr;
     count++;
    }
    pthread_mutex_unlock(&mut);
}

int main()
{
    char s[81];
    char c;
    list *curr;
    int tmp;
    
    if (sigset(SIGINT, sigint) == SIG_HOLD) {
            printf("Signal is holded.\n");
        return (1);
    }
    if (pthread_create(&pt, NULL, pthread_proc, NULL) != 0) {
     printf("The second thread is not created\n");
     return (1);
    }
    while (1) {
     s[0] = 0;

     tmp = 0;
     do {

      c = getchar();
      printf("c = %c, tmp = %d.\n", c, tmp);
         if (exit_status == 1) {
          pthread_mutex_lock(&mut);
    
              while (head) {
               curr = head;
               head = head->next;
               free(curr);
             }
        
          pthread_cancel(pt);
        
             pthread_mutex_unlock(&mut);
             pthread_join(pt, NULL);
             pthread_mutex_destroy(&mut);
             printf("\x8\x8");
             return (0);
         }
        
     if (c == '\n') {
         s[tmp] = 0;
         if (tmp != 0)
          insert(s);
         break;
     }
     s[tmp] = c;
     tmp++;
     if (tmp == 80) {
       s[tmp] = 0;
       insert(s);
       tmp = 0;
     }
     } while (1);

     if (!tmp) {
      pthread_mutex_lock(&mut);
         printlist();
         pthread_mutex_unlock(&mut);
     }
    }
    pthread_exit(0);

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