# 2019q3 homework4 (quiz4)
contributed by < `kksweet8845` >
```cpp
typedef struct __list {
int data;
struct __list *next;
} list;
```
```cpp
list *sort(list *start) {
if (!start || !start->next)
return start;
list *left = start;
list *right = left->next;
left->next = NULL;
left = sort(left);
right = sort(right);
for (list *merge = NULL; left || right; ) {
if (!right || (left && left->data < right->data)) {
if (!merge) {
start = merge = left
;
} else {
merge->next = left;
merge = merge->next;
}
left = left->next;
} else {
if (!merge) {
start = merge = right;
} else {
merge->next = right;
merge = merge->next;
}
right = right->next;
}
}
return start;
}
```
## Principle
Merge sort can be seen as a application of divided-and-counquer method.
The main concept is to split the original array into two part until the length of array becomes 1.
Then, merge all the arraies of one length toggether with a descending order or ascending.
That is, the merge sort has two part within this algorithm.
- Divide
- Counquer
Dividing part is simpler but it can apply different strategy when dividing the array.
The example code there is a n = 1 + (n-1) method, which will always split the array into two aprts,1 and n-1, respectively. Then, it is inefficeient because it will invoke itself at least (n-1) times until it reach the both length of array be 1. Then, it starts the merge process.
Let consider what if we must use the 1-(n-1) stratgy. Then, we can optimize the code when the left node is been merge to the main array. We can simple stop the loop to concatenate the right array into main array directly.
```cpp
```
## Circular doubly-linked list
- Rewrite the code according to `list.h`
Data structure, which `list_head` is the circular linked-list, `listitem` is the custimized node for merge sort.
```cpp
struct list_head {
struct list_head *prev;
struct list_head *next;
};
struct listitem {
uint16_t i;
struct list_head list;
};
```
Merge part
```cpp
void merge(struct list_head *left_head, struct list_head *right_head)
{
struct listitem *leftitem, *rightitem, *lisafe, *risafe, *item;
LIST_HEAD(merge_h);
leftitem = list_first_entry(left_head, struct listitem, list);
lisafe = list_entry(leftitem->list.next, struct listitem, list);
rightitem = list_first_entry(right_head, struct listitem, list);
risafe = list_entry(rightitem->list.next, struct listitem, list);
for (; &leftitem->list != left_head && &rightitem->list != right_head;) {
if (cmpint(&leftitem->i, &rightitem->i) < 0) {
list_move_tail(&leftitem->list, &merge_h);
leftitem = lisafe;
lisafe = list_entry((lisafe->list.next), struct listitem, list);
} else {
list_move_tail(&rightitem->list, &merge_h);
rightitem = risafe;
risafe = list_entry((risafe->list.next), struct listitem, list);
}
}
if (&leftitem->list == left_head) {
list_splice_tail(right_head, &merge_h);
}
if (&rightitem->list == right_head) {
list_splice_tail(left_head, &merge_h);
}
list_cut_position(left_head, &merge_h, merge_h.prev);
}
```
Partition part
```cpp
void partition(struct list_head *left_head,
struct list_head *right_head,
struct list_head *head)
{
struct list_head *node = NULL;
struct list_head *pivot = NULL;
int len = 0, mean, i;
list_for_each (node, head)
len++;
mean = len / 2;
for (node = head->next, i = 1; i < mean; i++, node = node->next);
list_cut_position(left_head, head, node);
list_cut_position(right_head, head, head->prev);
}
```
Partition First
```cpp
void partition_first(struct list_head *left_head,
struct list_head *right_head,
struct list_head *head)
{
struct list_head *node = NULL;
int len = 0, mean, i;
list_for_each (node, head)
len++;
if (len == 2) {
list_cut_position(left_head, head, head->next);
list_cut_position(right_head, head, head->prev);
return;
}
list_cut_position(left_head, head, head->next->next);
list_cut_position(right_head, head, head->prev);
}
```
Partition Randomly
```cpp
void partition_rand(struct list_head *left_head,
struct list_head *right_head,
struct list_head *head)
{
struct list_head *node = NULL;
struct list_head *pivot = NULL;
uint16_t rand;
int len = 0, mean, i;
list_for_each (node, head)
len++;
if (len > 2)
rand = get_unsigned16() % (len - 2) + 1;
else {
list_cut_position(left_head, head, head->next);
list_cut_position(right_head, head, head->prev);
return;
}
for (node = head->next, i = 0; i < rand; i++, node = node->next);
list_cut_position(left_head, head, node);
list_cut_position(right_head, head, head->prev);
}
```
## Iterative version
```cpp
void merge_sort_iter(struct list_head *head){
struct list_head *node, *prev;
struct list_head *odd_special = NULL;
int len = 0, original_l = 0;
struct list_head sec, temp;
struct listitem *item = NULL;
INIT_LIST_HEAD(&sec);
INIT_LIST_HEAD(&temp);
/**
* Determine the length
*/
list_for_each(node, head)
original_l++;
if(original_l % 2 != 0){
odd_special = head->prev;
list_del_init(odd_special);
len = original_l - 1;
}else
len = original_l;
size_t i = 0, j, k, t;
for(i=(len>>1),j=2;i != 0 && j!=2*len;j<<=1,i>>=1){
for(k=j;k<=len;k+=j){
for(node = head, t = 0; t<j; t++, node=node->next);
list_cut_position(&sec, head, node);
swap(&sec, j);
list_splice_tail_init(&sec, &temp);
}
list_splice_init(&temp, head);
}
if(odd_special){
list_for_each_entry(item, head, list){
if(item->i > list_entry(odd_special, struct listitem, list)->i){
prev = item->list.prev;
prev->next = odd_special;
odd_special->prev = prev;
item->list.prev = odd_special;
odd_special->next = &item->list;
}
}
}
}
```
## XOR sort
The data structure
```cpp
typedef struct xor_list {
int data;
unsigned long lxr;
} xor_list_t;
typedef struct xor_info {
xor_list_t *left;
xor_list_t *right;
} xor_lxri_t;
```
```cpp
void merge_sort(xor_lxri_t *p_lxri, xor_list_t **start){
if (!(*start) || !p_lxri->right)
return;
xor_list_t *left = *start;
xor_list_t *right = p_lxri->right;
/**
* Construct xor_info for left and right
*/
xor_lxri_t left_lxri = {.left = NULL, .right = NULL};
left->lxr = (unsigned long) left_lxri.left ^ (unsigned long) left_lxri.right;
xor_lxri_t right_lxri = {.left = NULL, .right = NULL};
right_lxri.right = extract_address(right, left);
right->lxr = (unsigned long) right_lxri.left ^ (unsigned long)right_lxri.right;
merge_sort(&left_lxri, &left);
merge_sort(&right_lxri, &right);
xor_lxri_t merge_lxri = {.left = NULL, .right = NULL};
for (xor_list_t *merge = NULL; left || right; ) {
if(!right || (left && left->data < right ->data)) {
if(!merge){
*start = merge = left;
merge->lxr = (unsigned long) merge_lxri.left;
}else {
merge = append_item(&merge_lxri, merge, left);
}
left_lxri.left = left;
left = left_lxri.right;
if(left){
left_lxri.right = extract_address(left, left_lxri.left);
left->lxr = (unsigned long) NULL ^ (unsigned long) left_lxri.right;
}
left_lxri.left = (xor_list_t*) NULL;
}else {
if(!merge){
*start = merge = right;
merge->lxr = (unsigned long) merge_lxri.left;
}else {
merge = append_item(&merge_lxri, merge, right);
}
right_lxri.left = right;
right = right_lxri.right;
if(right){
right_lxri.right = extract_address(right, right_lxri.left);
right->lxr = (unsigned long) NULL ^ (unsigned long) right_lxri.right;
}
right_lxri.left = (xor_list_t*) NULL;
}
p_lxri->right = extract_address(*start, (xor_list_t*)NULL);
p_lxri->left = (xor_list_t*) NULL;
}
}
```
With doubly linked-list
```shell
==25059== HEAP SUMMARY:
==25059== in use at exit: 0 bytes in 0 blocks
==25059== total heap usage: 10 allocs, 10 frees, 240 bytes allocated
```
With xor linked-list
```cpp
==23626== HEAP SUMMARY:
==23626== in use at exit: 0 bytes in 0 blocks
==23626== total heap usage: 10 allocs, 10 frees, 160 bytes allocated
```
We can see that the memory usage of doubly linked-list has additional 8 bytes than the xor linked-list.
Sign in with Wallet
Connect another wallet