QuickSort

Implementazione in Linguaggio C dell’algoritmo QuickSort su un vettore generico

typedef int(*compare_ptr)(void* V, int a, int b);
typedef void(*swap_ptr)(void* V, int a, int b);

int partition(void* V, int lo, int hi, compare_ptr cmp, swap_ptr swp){
int perno = lo;
int inf = lo + 1;
int sup = hi;

while(inf<=sup){
while( cmp(V,perno,inf) )inf++;

while( cmp(V,sup,perno) )sup--;

if(inf=hi)return;
int m = partition(V,lo,hi,cmp,swp);
quicksort(V,lo,m-1,cmp,swp);
quicksort(V,m+1,hi,cmp,swp);
return;
}

RadixSort

Implementazione in Linguaggio C dell’algoritmo RadixSort su una Lista.
E’ necessario includere i sorgenti di BucketSort e della Lista


queue_t* radixSort(queue_t* head, int numCifre){
int step = 0;
int i = 1;

queue_t* dummy;

while(step key = (*((int*)(dummy->val))/i) % 10;
dummy = dummy->next;
}
head = bucketSort(head);
step++;
i *= 10;
}

return head;
}

BubbleSort

Implementazione in Linguaggio C dell’algoritmo BubbleSort su un vettore generico

#define TRUE 1
#define FALSE 0

typedef int (*compare_ptr)(void* V, int a, int b);
typedef void (*swap_ptr)(void* V, int a, int b);

void bubbleSort(void* V, int n, compare_ptr cmp, swap_ptr swp){
int flag = TRUE;
int i;

while(flag){
flag = FALSE;
for(i=0; i < n-1; i++){
if( cmp(V,i,i+1) ){
swp(V,i,i+1);
flag = TRUE;
}
}
}
}

MergeSort

Implementazione in Linguaggio C dell’algoritmo MergeSort

#include

typedef int (*compare_ptr)(void** V, int a, int b);

void merge(void** V, int first, int middle, int last, compare_ptr cmp){
int n = last - first + 1;
if(n==1)return;

void** aux = (void**)malloc(n*sizeof(void*));

int lowOne = first;
int lowTwo = middle + 1;
int i = 0;

while(lowOne <= middle && lowTwo <= last){

if( cmp(V,lowOne,lowTwo) )
aux[i] = V[lowTwo++];

else
aux[i] = V[lowOne++];

i++;
}

int k;
if(lowOne <= middle)
for(k=i; k<n; k++)
aux[k] = V[lowOne++];

else if(lowTwo <= last)
for(k=i; k<n; k++)
aux[k] = V[lowTwo++];

for(i=0; i=hi)return;
int m = (lo+hi)/2;

mergesort(V,lo,m,cmp);
mergesort(V,m+1,hi,cmp);
merge(V,lo,m,hi,cmp);

return;
}

Lista

Implementazione parziale in Linguaggio C di una Lista, sono riportate soltanto le funzioni necessarie per il BucketSort.

#ifndef QUEUE
#define QUEUE

#include
#include

typedef struct s_queue {
void* val;
int key;
struct s_queue *next;
} queue_t;

//inizializza la lista
queue_t* queue_init(queue_t** head){
*head = NULL;
return *head;
}

//restituisce l'ultimo elemento nella lista
queue_t* queue_tail(queue_t* head){
if(head == NULL)return NULL;
queue_t* dummy = head;

while(dummy->next != NULL)
dummy = dummy->next;

return dummy;
}

//restituisce il numero di nodi della lista
int queue_nodeNum(queue_t* head){
int i = 0;
queue_t* dummy = head;
while(dummy != NULL){
i++;
dummy = dummy->next;
}
return i;
}

//concatena due liste
queue_t* queue_enqueue(queue_t* head, queue_t* node){
if(node==NULL)return NULL;

queue_t* tail = queue_tail(head);
if(tail == NULL)
head = node;
else
tail->next = node;

return head;
}

//accoda un elemento alla lista
queue_t* queue_enqueueOne(queue_t* head, queue_t* node){
if(node==NULL)return head;
node->next = NULL;

if(head == NULL)
head = node;
else{
queue_t* tail = queue_tail(head);
tail->next = node;
}

return head;

}

//crea un nuovo nodo
queue_t* queue_newNode(void* val, int key){
queue_t* node = (queue_t*)malloc(sizeof(queue_t));
node->next = NULL;
node->val = val;
node->key = key;
return node;
}

#endif

BucketSort

Implementazione in Linguaggio C dell’algoritmo BucketSort su una Lista.
La lista è implementata parzialmente (solamente le funzioni necessarie per l’esecuzione di questo sorgente).

int maxNode(queue_t* head){
int max = 0;
queue_t* dummy = head;
while(dummy!= NULL){
if(dummy->key > max )
max = dummy->key;
dummy = dummy->next;
}
return max;
}

queue_t* bucketSort(queue_t* head){
int n = maxNode(head) + 1;
if(n<=1)return head;
queue_t** V = (queue_t**)malloc(n*sizeof(head));
int i;

for(i=0; ikey;
dummy = head;
head = head->next;
V[i] = queue_enqueueOne(V[i],dummy);
}

head = NULL;

for(i=0; i<n; i++)
if(V[i] != NULL)
head = queue_enqueue(head,V[i]);

free(V);
return head;
}

HeapSort

Implementazione in Linguaggio C dell’algoritmo HeapSort su un vettore generico.

typedef int (*compare_ptr)(void* V, int a, int b);
typedef void (*swap_ptr)(void* V, int a, int b);

void heapify(void* V, int n, int i, compare_ptr cmp, swap_ptr swp){
if(n==1)return;
int max = i;
int l = 2*i + 1;
int r = l + 1;

if( l<n && cmp(V,l,max) )
max = l;
if( r=0; i--)
heapify(V,n,i,cmp,swp);
}

void heapSort(void* V, int n, compare_ptr cmp, swap_ptr swp){
heapBuild(V,n,cmp,swp);
int i;
for(i=1; i<n; i++){
swp(V,n-i,0);
heapify(V,n-i,0,cmp,swp);
}

return;
}