C Sort Algorithm: Selection Sort

/**
 * Author: Ozan Özenoğlu
 * Date : 16/10/2020
 * */

struct linked_list_node {
    struct linked_list_node *next;
    int val;
};
typedef struct linked_list_node linked_list_node_t;


struct linked_list {
    int size;
    linked_list_node_t *head;
};

typedef struct linked_list linked_list_t;

void init(linked_list_t *list){
    list->size = 0;
    list->head = (void*)0;
    printf("linked list init completed\n");
}

void add(linked_list_t *list, int val){
    linked_list_node_t *node = malloc(sizeof(linked_list_node_t)*1);
    node->val = val;
    node->next = list->head;
    list->head = node;
    list->size++;
    printf("%d is added\n",val);
}

void swap(int *a , int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

linked_list_node_t *find_min(linked_list_node_t * n) {
    linked_list_node_t * min = malloc(sizeof(linked_list_node_t));
    min->val = INT_MAX;
    linked_list_node_t *tmp = min;

    while(n != (void*)0) {
        if (min->val > n->val) {
            min = n;
        }
        n = n->next;        
    }
    free(tmp);
    return min;
}

void selection_sort(linked_list_t *l) {
    linked_list_node_t *node = l->head;
    while(node->next != (void*)0) {
        linked_list_node_t *min = find_min(node->next); // find min node from rest of the list.
        if (node->val > min->val) {
            swap(&node->val, &min->val);
        }
        node = node->next;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *