# 12523 - Inventory

>author: Utin
###### tags: `bubble sort`

---

## Brief
See the code below

## Solution 0 (Node Array)

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    char name[21];
    int c, m, status;
} Node;

Node arr[101]; // 存Node的陣列

void swap(int a, int b);

int main() {
    int n;
    int c, m;
    Node* new_node;
    scanf("%d", &n);

    for(int i = 0; i < n; i++) {
        scanf("%s %d %d", arr[i].name, &arr[i].c, &arr[i].m);
        if(arr[i].c < arr[i].m) arr[i].status = 0;
        else arr[i].status = 1;
    }

    // bubble sort
    for(int t = n; t > 0; t--) {
        for(int i = 0; i < t-1; i++) {
            if(arr[i].status > arr[i+1].status) swap(i, i+1);
            else if(arr[i].status == arr[i+1].status) {
                if(arr[i].status == 0) {
                    if(arr[i].c > arr[i+1].c) swap(i, i+1);
                    else if(arr[i].c == arr[i+1].c) {
                        if(arr[i].m > arr[i+1].m) swap(i, i+1);
                    }
                }
                else if(arr[i].m > arr[i+1].m) swap(i, i+1);
            }
        }
    }

    // output
    for(int i = 0; i < n; i++) {
        printf("%s %d %d\n", arr[i].name, arr[i].c, arr[i].m);
    }
}

void swap(int a, int b) {
    Node temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
// By Utin

## Solution 1 (Node* Array)

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
	char name[21];
	int c, m, status;
} Node;

Node* arr[101]; // 記Node的位址

void swap(int a, int b);

int main() {
    int n;
    Node* new_node;
    scanf("%d", &n);

    for(int i = 0; i < n; i++) {
        new_node = (Node*) malloc(sizeof(Node));
        scanf("%s %d %d", new_node->name, &new_node->c, &new_node->m);
        if(new_node->c < new_node->m) new_node->status = 0;
        else new_node->status = 1;
        arr[i] = new_node;
    }

    // bubble sort
    for(int t = n; t > 0; t--) {
        for(int i = 0; i < t-1; i++) {
            if(arr[i]->status > arr[i+1]->status) swap(i, i+1);
            else if(arr[i]->status == arr[i+1]->status) {
                if(arr[i]->status == 0) {
                    if(arr[i]->c > arr[i+1]->c) swap(i, i+1);
                    else if(arr[i]->c == arr[i+1]->c) {
                        if(arr[i]->m > arr[i+1]->m) swap(i, i+1);
                    }
                }
                else if(arr[i]->m > arr[i+1]->m) swap(i, i+1);
            }
        }
    }

    // output
    for(int i = 0; i < n; i++) {
        printf("%s %d %d\n", arr[i]->name, arr[i]->c, arr[i]->m);
        free(arr[i]);
    }
}

void swap(int a, int b) {
    Node* temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
// By Utin

## Solution 2 (Linked List)

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
	char name[21];
	int c, m, status;
	struct node* next;
} Node;

Node* head = NULL;
Node* end = NULL;

Node* swap(Node* pre_a, Node* a, Node* b);

int main() {
    int n;
    char name[21];
    int c, m;
    Node* new_node;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        // 新增一個Node
        new_node = (Node*) malloc(sizeof(Node));
        scanf("%s %d %d", new_node->name, &new_node->c, &new_node->m);
        if(new_node->c < new_node->m) new_node->status = 0;
        else new_node->status = 1;
        new_node->next = NULL;

        // 放進連結串列
        if(head == NULL) {
            head = new_node;
            end = new_node;
        }
        else {
            end->next = new_node;
            end = end->next;
        }
    }

    Node* curr;
    Node* pre_curr;

    // bubble sort
    for(int t = n; t > 0; t--) {
        pre_curr = NULL;
        curr = head;
        for(int i = 0; i < t-1; i++) {
            if(curr->status > curr->next->status)
                curr = swap(pre_curr, curr, curr->next);
            else if(curr->status == curr->next->status) {
                if(curr->status == 0) {
                    if(curr->c > curr->next->c)
                        curr = swap(pre_curr, curr, curr->next);
                    else if(curr->c == curr->next->c) {
                        if(curr->m > curr->next->m)
                            curr = swap(pre_curr, curr, curr->next);
                    }
                }
                else if(curr->m > curr->next->m)
                    curr = swap(pre_curr, curr, curr->next);
            }
            pre_curr = curr;
            curr = curr->next;
        }
    }

    // output
    curr = head;
    pre_curr = NULL;
    while(curr != NULL) {
        printf("%s %d %d\n", curr->name, curr->c, curr->m);
        pre_curr = curr;
        curr = curr->next;
        free(pre_curr);
    }
}

Node* swap(Node* pre_a, Node* a, Node* b) {
    // 有換到首項的情況
    if(a == head) {
        a->next = b->next;
        b->next = a;
        head = b;
    }

    // 其他情況
    else {
        pre_a->next = b;
        a->next = b->next;
        b->next = a;
    }

    // 因為要做bubble sort，所以要回傳前面節點的位址
    return b;
}
// By Utin

## Reference