DS6

Problem A

If the key sequence of the initial record is with the key (49,38,65,97,76,13,27,50), give the results of shell sort with intervals d=4 and then with d=2;

创建数组及其他函数

1
2
3
4
int main() {
    int arr[8] = {49, 38, 65, 97, 76, 13, 27, 50};
    return 0;
}

交换函数，用来交换两个整数

1
2
3
4
5
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

打印函数，遍历输出数组

1
2
3
4
5
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

排序算法

1
2
3
4
5
6
7
8
9
10
11
12
void shellsort(int arr[], int len, int gap) {
    //i可以从1或者0开始，但是没什么用。。。
    for (int i = gap; i < len; i++) {
        int j = i;
        //与同一组的前一个数（大数组的前`gap`个数）比较、交换。模拟插入到合适的位置
        while (j >= gap && arr[j] > arr[j - gap]) {
            swap(&arr[j], &arr[j - gap]);
            j -= gap;
        }
    }
    printarr(arr, len);
}

输出

1
2
3
4
interval:4
76,38,65,97,49,13,27,50,
interval:2
76,97,65,50,49,38,27,13,

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>

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

void printarr(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d,", arr[i]);
    }
    printf("\n");
}

void shellsort(int arr[], int len, int gap) {

    for (int i = gap; i < len; i++) {
        int j = i;
        while (j >= gap && arr[j] > arr[j - gap]) {
            swap(&arr[j], &arr[j - gap]);
            j -= gap;
        }
    }
    printarr(arr, len);
}

int main() {
    int arr[8] = {49, 38, 65, 97, 76, 13, 27, 50};
    printf("interval:4\n");
    shellsort(arr, 8, 4);

    printf("interval:2\n");
    shellsort(arr, 8, 2);
    return 0;
}

Problem B

If the initial sequence is (24，35，12，27，18，26), give the results after the third iteration of insertion sort and selection sort.

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
void insertsort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int j = i;
        while (j > 0 && arr[j] < arr[j - 1]) {
            swap(&arr[j], &arr[j - 1]);
            j--;
        }
        if (i == 3) {
            printf("Insert Generation %d: ", i);
            printarr(arr, n);
        }
    }
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void selectsort(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        swap(&arr[i], &arr[min]);
        if (i == 3) {
            printf("Select Generation %d: ", i);
            printarr(arr, n);
        }
    }
}

输出

1
2
Insert Generation 3: 12,24,27,35,18,26,
Select Generation 3: 12,18,24,26,35,27,

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>

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

void printarr(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d,", arr[i]);
    }
    printf("\n");
}

void insertsort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int j = i;
        while (j > 0 && arr[j] < arr[j - 1]) {
            swap(&arr[j], &arr[j - 1]);
            j--;
        }
        if (i == 3) {
            printf("Insert Generation %d: ", i);
            printarr(arr, n);
        }
    }
}

void selectsort(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        swap(&arr[i], &arr[min]);
        if (i == 3) {
            printf("Select Generation %d: ", i);
            printarr(arr, n);
        }
    }
}

int main() {
    int arr1[6] = {24, 35, 12, 27, 18, 26};
    insertsort(arr1, 6);
    int arr2[6] = {24, 35, 12, 27, 18, 26};
    selectsort(arr2, 6);
    return 0;
}

Problem C

The sequence is (20，38，24，23，26，32，21，29，38，28), give the results of quick sort after each iteration, using Median3 to select the pivot.

排序策略

  1. 如果序列过短，采用直接插入排序
  2. 利用分割函数返回分割点（左面小于分割点、右面大于分割点）
  3. 对分割点左右递归调用分割函数
1
2
3
4
5
6
7
8
9
10
void quicksort(int arr[], int left, int right) {
    if (left + 3 < right) {
        int pivotidx = partition(arr, left, right);
        quicksort(arr, left, pivotidx - 1);
        quicksort(arr, pivotidx + 1, right);
    }
    else {
        //insertion sort
    }
}

分割策略

  1. 获取主元值pivot
  2. 从最左侧开始向右搜索，（左1有序，为中和++i提前1位，综合左0开始），找到大于主元值的
  3. 从最右侧-1向左搜索，（右1，右2有序，为中和–i落后以为，综合右-1开始），找到小于主元值的
  4. 如果上面两个值位置合法（不越位）则交换两数
  5. 最后i停留的位置一定大于pivot，j停留的位置一定小于pivot(先++ --搜索，后比较)
  6. 将大于pivot的i与pivot（right-1）互换，实现pivot分割大小堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int partition(int arr[], int left, int right) {
    int pivot = getpivot(arr, left, right);
    int i = left;
    int j = right - 1;
    while (1) {
        while (arr[++i] < pivot) {}
        while (arr[--j] > pivot) {}
        if (i < j) {
            swap(&arr[i], &arr[j]);
        }
        else {
            break;
        }
    }
    swap(&arr[i], &arr[right - 1]);
    return i;
}

三数取中主元策略

  1. 从序列左中右取三个数，并排序
  2. 中位数作为pivot
  3. 将pivot放于最右-1位置
  4. 三数与序列最终关系为[small, … , mid(pivot), big]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int getpivot(int arr[], int left, int right) {
    //less than 3 elements
    if (right - left < 2) {
        return arr[left];
    }
    int mid = (left + right) / 2;
    if (arr[left] > arr[mid]) {
        swap(&arr[left], &arr[mid]);
    }
    if (arr[left] > arr[right]) {
        swap(&arr[left], &arr[right]);
    }
    if (arr[mid] > arr[right]) {
        swap(&arr[mid], &arr[right]);
    }
    //将piviot 放于 right - 1
    swap(&arr[mid], &arr[right - 1]);
    return arr[right - 1];
}

输出

1
20,21,23,24,26,28,29,32,38,38,

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <stdio.h>

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

void printarr(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d,", arr[i]);
    }
    printf("\n");
}

int getpivot(int arr[], int left, int right) {
    //less than 3 elements
    if (right - left < 2) {
        return arr[left];
    }
    int mid = (left + right) / 2;
    if (arr[left] > arr[mid]) {
        swap(&arr[left], &arr[mid]);
    }
    if (arr[left] > arr[right]) {
        swap(&arr[left], &arr[right]);
    }
    if (arr[mid] > arr[right]) {
        swap(&arr[mid], &arr[right]);
    }
    //将piviot 放于 right - 1
    swap(&arr[mid], &arr[right - 1]);
    return arr[right - 1];
}

int partition(int arr[], int left, int right) {
    int pivot = getpivot(arr, left, right);
    int i = left;
    int j = right - 1;
    while (1) {
        while (arr[++i] < pivot) {}
        while (arr[--j] > pivot) {}
        if (i < j) {
            swap(&arr[i], &arr[j]);
        }
        else {
            break;
        }
    }
    printf("i = %d, j = %d, pivotval = %d\n", arr[i], arr[j], pivot);
    swap(&arr[i], &arr[right - 1]);
    return i;
}


void quicksort(int arr[], int left, int right) {
    if (left + 3 < right) {
        int pivotidx = partition(arr, left, right);
        quicksort(arr, left, pivotidx - 1);
        quicksort(arr, pivotidx + 1, right);
    }
    else {
        //insertion sort
        for (int i = left + 1; i <= right; i++) {
            int temp = arr[i];
            int j = i;
            for (; j > left && arr[j - 1] > temp; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }
}

int main() {

    int arr[10] = {20, 38, 24, 23, 26, 32, 21, 29, 38, 28};
    quicksort(arr, 0, 9);
    printarr(arr, 10);
    return 0;
}

Problem D

Implement the insertion sort algorithm with linked list.

下面以序列 1,4,5,3,2 为例

构建链表

1 -> 4 -> 5 -> 3 -> 2

1
2
3
4
5
6
7
8
9
10
int num[5] = {1, 4, 5, 3, 2};
PTNode head = (PTNode) malloc(sizeof(Node));
PTNode h = head;
for (int i = 0; i < 5; i++) {
    PTNode temp = (PTNode) malloc(sizeof(Node));
    temp->data = num[i];
    temp->next = NULL;
    h->next = temp;
    h = h->next;
}

排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
while (pre->next != NULL) {
    //反了
    if (aft->data < pre->data) {
        //从头遍历插入位置<小于aft><位置><大于aft>
        PTNode temp = head->next;
        //PTNode temp_pre = head;
        while (temp->next->data < aft->data) {
            temp = temp->next;
        }
        //插入
        PTNode copy = aft->next;
        aft->next = temp->next;
        temp->next = aft;
        pre->next = copy;
        //更新aft位置（pre是有序列最大值位置）
        aft = pre->next;
    }
        //正常,向后移位
    else {
        pre = pre->next;
        aft = aft->next;
    }
}

输出

1
1 2 3 4 5

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
#include <stdlib.h>

typedef struct node *PTNode;
typedef struct node {
    int data;
    PTNode next;
} Node;

int main() {
    //creat linklist 1,4,5,3,2
    int num[5] = {1, 4, 5, 3, 2};
    PTNode head = (PTNode) malloc(sizeof(Node));
    PTNode h = head;
    for (int i = 0; i < 5; i++) {
        PTNode temp = (PTNode) malloc(sizeof(Node));
        temp->data = num[i];
        temp->next = NULL;
        h->next = temp;
        h = h->next;
    }
    //insertsort
    PTNode pre = head->next;
    PTNode aft = pre->next;
    while (pre->next != NULL) {
        //反了
        if (aft->data < pre->data) {
            //从头遍历插入位置<小于aft><位置><大于aft>
            PTNode temp = head->next;
            //PTNode temp_pre = head;
            while (temp->next->data < aft->data) {
                temp = temp->next;
            }
            //插入
            PTNode copy = aft->next;
            aft->next = temp->next;
            temp->next = aft;
            pre->next = copy;

            //更新aft位置（pre是有序列最大值位置）
            aft = pre->next;
        }
            //正常,向后移位
        else {
            pre = pre->next;
            aft = aft->next;
        }
    }
    //printlist
    PTNode p = head->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    return 0;
}