Pushswap Epitech Project

Authorized functions

The list of authorized functions are only:

• write
• malloc
• free

Description

The goal of the project is to return the series of actions for sorting a list. You will have two lists : l_a and l_b.

The l_b starts empty and l_a contain the list of integers you need to sort.

The objective can be to sort the l_a list, but there is a mystery strategy of only printing and not sorting, that gives you great performances, but I don’t know this technique so you are going to sort the l_a list.

If you want to try the mysterious strategy, I only know that you need to print a specific number of bubble sort actions.

So from the beginning I tell you you will need actions, and here the list of them :

The l_a list is passed as paramter.

Exemple

We are going to take l_a = [1, 2, 3, 4, 5] and l_b = [] (empty).

Tutorial

The project Pushswap is quite simple when you understand how to do. It is splited into 3 parts:

• Linked List the l_a with args passed as parameters.

• Actions asked on the subject.

• Algorithm radix sort by Bit Shifting method.

The project can be done by multiple different way:

• By using array.

• By using simply linked list.

• By using doubly linked list.

• By using doubly circular linked list.

I am sure you know which one we will choose 😂 …. doubly circular linked list. You: 😭: readding this tutorial. Don’t be afraid, it is not as complicated as you’re thinking !

Linked List

To create a doubly circular linked list you need to have a linked list following this schema:

This schema shows you how to construct it. So now let take a look at some code.

1
2
3
4
5
6

typedef struct node
{
    int data;
    struct node *next;
    struct node *prev;
} node_t;

This is how can looks your linked list. A next and a prev for the links and data your list of integers.

To create you doubly circular linked list you will need to save temporarily the pointer of the first node to make the last node point on it. You will also need to keep a pointer on the previous node to make point the prev of the next to his previous node.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

struct node *init_linked_list(char **av)
    node_t *node_last;
    node_t *node_first;
    node_t *node = malloc(sizeof(node_t));

    if (!node)
        return NULL;
    node->data = my_atoi(av[1]);
    node->prev = node;
    node->next = node;
    node_first = node;

Here you have a node linked to itself, that’s what we want for only one element, but it will change a bit for the next step of adding other nodes.

For adding other nodes, you need to initialise a new_node, fill his data by the integer you want and make it point to the first node. When you have done that, make point your next current node on the new node you have created. Move to the next node of your current node and now you can link the prev with your previous node.

A bit hard to understand ? Take a look on the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

    // function could have others_nodes as name
    node_t *node_next;

    for (int i = 2; av[i] != NULL; i++) {
        node_next = malloc(sizeof(node_t));
        node_next->data = my_atoi(av[i]);
        node_next->next = node_first;
        node->next = node_next;
        node_last = node;
        node = node->next;
        node->prev = node_last;
}

Only one thing is missing here ! The last link !!

1
2
3
4

    node_last = node;
    node = node->next;
    node->prev = node_last;
    return (node);

You were on the last node, you moved to the next that point on the first and you have linked the previous of the first on his previous that is the end’s node. So you should have something looking like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

struct node *set_linked_list(char **av)
{
    node_t *node_last;
    node_t *node_first;
    node_t *node = malloc(sizeof(node_t));

    if (!node)
        return NULL;
    node->data = my_atoi(av[1]);
    node->prev = node;
    node->next = node;
    node_first = node;
    others_nodes(av, &node_first, &node_last, &node);
    node_last = node;
    node = node->next;
    node->prev = node_last;
    return (node);
}

I let you understand by yourself how are working the references I sent to the others_nodes function.

Actions

Actions are, NO FAKE, the EASIEST part of the project !

sa, sb and sc

Let’s call a s_action function that will swap the two first elements of a list.

1
2
3
4
5

// You really thought you are going to do the bubble sort ISSOU !

// If you have read the radix sort doc you know you wont use it !

// But if you want to do it for bonuses, after this tutorial I think will be able to do it by yourself.

Next !

pa and pb

Let’s call a p_action or push_to_other_list function that will move the first element of a list at the first position of another. But !…

You will first need a delete_node function that will check if a linked list contain only one or more node. If it contains only one, then set the linked list at NULL. If the list contains more, you will need to make your previous node (from the node you want to delete) point on the next (from the node you want to delete).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void delete_node(node_t *from)
{
    if (from == from->next) {
        from = NULL;
    } else {
        from->prev->next = from->next;
        from->next->prev = from->prev;
        from = from->next;
    }
}

Now you have the delete_node function you can save the node you want to delete into a saver and delete the integer from the linked list.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void push_to_other_list(node_t *from, node_t *to)
{
    node_t *save;
    node_t *stock;

    if (!from)
        return;
    save = from;
    delete_node(from);
}

Only what you need now is to insert the saved node into the next linked list. So check if this list is empty. When it is empty, just place the node in it and make point on itself. If the linked list contains nodes, it will be a bit harder. I let you take a look on the code and I explain you after.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

    if (to) {
        stock = to->prev;
        to->prev = save;
        to->prev->next = to;
        to->prev->prev = stock;
        to->prev->prev->next = save;
        to = to->prev;
    } else {
        to = save;
        to->next = to;
        to->prev = to;
    }

Here you are on the first node, so you save the previous to insert it on the previous and the first node. Remember the previous of the first is the end. So you change that and you place your saver on the previous of your first node. This new first node need to his next point on the now second node (that was your first node previously). Likewise, you need to your previous of your first node point on the previous of the previously first node, so you make point on the one you saved (stock variable). And so now the end’s node needs to point to the first node. You now have the element of the other list at the first position in this list. But, your current pointer is pointing to the second, so you move to the first element of your list by using to = to->prev.

Hard but you have succeeded !

Next !

ra, rb and rr

Let’s call a r_action or first_to_end function that will move the first element at the end of this list.

1
2
3
4

void first_to_end(node_t *list)
{
    list = list->next;
}

Here is, you have just moved your pointer to the next, so the first becomes the end as you have a doubly circular linked list.

Next !

rra, rrb and rrr

Let’s call a rr_action or end_to_first function that will move the end element at the first position of this list, and I am sure that you know how to do it !

1
2
3
4

void first_to_end(node_t *list)
{
    list = list->prev;
}

Algorithm

First of all, before starting the algorithm in your code you would maybe checks if the list is already sorted. So write a function that check with bubble travel if your list is sorted.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

bool is_sorted_list(node_t *l_a, int args_number)
{
    bool is_sort = true;

    for (int j = 1; j < args_number; j++) {
        if (l_a->data < l_a->next->data)
            is_sort = false;
        l_a = l_a->next;
    }
    l_a = l_a->next;
    return is_sort;
}

So now, for the algorithm, you will need to bitshift. What is the bitshift ?

The bitshift transform your numbers on bits, an integer in on 32 bits:

• 31: for the positive part

• The ‘1’ of 31 + 1 = 32: for the negative part

You need a loop for looking the 31 bits and a last check for the negative bit. So lets do something like that:

1
2
3
4
5
6
7
8

    save_t save;

    for (save.i = 0; save.i < 31; save.i++) {
        save.k = 0;
        // function for positive
    }
    save.k = 0;
    // last function for negative

Why did I save 'i' and 'k' ? Because with The Epitech’s coding style we can’t have more than 4 parameters per function and here you will need more, so you save values in structure like 'i' and 'k'.

Now you know that, you can create the positive function with bitshifting radix algorithm.

You need to loop on each element from the args that are in your l_a list and look if the save->i bit of your bitshifted number has the same weight. If it has the number will be placed in the l_b list. Like so, you will sort par each weight of bits. If I represent in on a schema it will do that:

As you can see the smaller number as been putted at the end of the list. You only need to loop on every bit and the project is done !

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void positive_sort(node_t *l_a, node_t *l_b, save_t *save, int args_number)
{
    for (int j = 1; j <= args_number; j++) {
        if (((*l_a)->data >> save->i) & 1) {
            push_to_list(l_a, l_b);
            first_to_end(l_b);
            write(1, "pb rb ", 6);
            save->k++;
        }
        else {
            first_to_end(l_a);
            write(1, "ra ", 3);
        }
    }
    if (l_b != NULL) {
        for (int j = 0; j < save->k; j++) {
            push_to_list(l_b, l_a);
            write(1, "pa ", 3);
            first_to_end(l_a);
            write(1, "ra ", 3);
        }
    }
}

I reseume: You look “every” bit (31 bits) on every arg. At each look, you compare the bit’s weight. If it weight one you push in the l_b list, otherwise you put your first node at the end (to travel your linked list). When you have traveled the entire list, fill at the end of the l_a list the l_b.

After doing positives, do the same for the negative.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

void negative_sort(node_t **l_a, node_t **l_b, save_t *save, int args_number)
{
    for (int j = 1; j <= args_number; j++) {
        if (((*l_a)->data >> 31) & 1) {
            push_to_list(l_a, l_b);
            write(1, "pb ", 3);
            save->k++;
        }
        else {
            first_to_end(l_a);
            write(1, "ra ", 3);
        }
    }
    if (l_b != NULL) {
        for (int j = 0; j < save->k; j++) {
            push_to_list(l_b, l_a);
            write(1, "pa ", 3);
        }
    }
}

And it is done ! You should now have a main loop like that, with the negative after the loop:

1
2
3
4
5
6
7

    for (save.i = 0; save.i < 31; save.i++) {
            save.k = 0;
            positive_sort(&l_a, &l_b, &save, len);
        }
    save.k = 0;
    negative_sort(&l_a, &l_b, &save, len);
    write(1, "rb\n", 3);

You have finished your project well done !

Bonus ideas

• Print the evolution of the sort

• Print in color

• Print with a grafical library

• Do for floats

• Optimisation for small list (by using another algorithm)