Numerical algorithms: equation solving, calculus, finite element analysis, signal processing, etc

Non-numerical algorithms: sorting, searching

A, bubble sort:

1. Algorithm:

9,7,5,3,1 scan 1: 7,5,3,1,9 scan 2: 5,3,1,7,9… ,3,5,7,9 scan N – 1:1


  • (1) Compare adjacent elements, and if the first is larger than the second, swap them both

  • (2) Do the same for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end. After this step, the last element will be the maximum

  • (3) Repeat the steps for all elements except the last one

  • (4) Keep repeating the above steps for fewer and fewer elements at a time until there are no elements to swap

Example:
#include <stdio.h> void bubble_sort(int data[], size_t size) { size_t i; For (I = 0; i < size - 1; ++i) { int ordered = 1; size_t j; For (j = 0; j < size - 1 - i; ++j) { if (data[j+1] < data[j]) { data[j] = data[j] ^ data[j+1]; data[j+1] = data[j] ^ data[j+1]; data[j] = data[j] ^ data[j+1]; ordered = 0; } } if (ordered) { break; }}} int main (void) {int data [] = 9,0,7,2,5,4,3,6,1,8 {}; size_t size = sizeof(data) / sizeof(data[0]); bubble_sort(data, size); size_t i; for (i = 0; i < size; ++i) { printf("%d ", data[i]); } printf("\n"); return 0; } /* Output: 0 1 2 3 4 5 6 7 8 9 */Copy the code

2. Evaluation:

Average time complexity,O(N^2), stable, very sensitive to data order.

Stable is the element with the same data, in the same order

Sensitive to data means that the closer the data is to order, the shorter the consumption time is; the closer the data is to reverse order, the longer the consumption time is

Insert sort

1, the algorithm

  • (1) Start with the first element, which can be considered sorted

  • (2) Take out the next element and scan from back to front in the sorted element sequence

  • (3) If the element is larger than the new element, the element will be moved to the next position

  • (4) If the element is less than or equal to the new element, the new element is inserted after the element

  • (5) Repeat Step 2 until all elements are processed

Example:
void insert_sort(int data[], size_t size) { size_t i; for (i = 1; i < size; ++i) { int temp = data[i]; size_t j; for (j = i; j - 1 >= 0; --j) { if (data[j-1] > temp) { data[j] = data[j-1]; } else { data[j] = temp; break; }}}}Copy the code

2. Evaluation:

Average time complexity, O(N^2), stable, very sensitive to data order. Bubble sort swaps values while insert sort moves values, so insert sort is superior to bubble sort.

Three, selection sort

1. Algorithm:

First, find the smallest element in the unsorted sequence and store it at the beginning of the sorted sequence. Then, continue to find the smallest element from the remaining unsorted elements and put it at the end of the sorted sequence. And so on until all the elements are sorted.

Example:
void select_sort(int data[], size_t size) { size_t i; for (i = 0; i < size - 1; ++i) { int k = i; for (int j = i + 1; j < size; ++j) { if (data[j] < data[k]) { k = j; } } if (k ! = i) { data[i] = data[i] ^ data [k]; data[k] = data[i] ^ data [k]; data[i] = data[i] ^ data [k]; }}}Copy the code

2. Evaluation:

Average time complexity, O(N^2), unstable. Insensitive to data order. Although the comparison times are large, but the data exchange is small, so it is generally faster than bubble sort.

Quicksort

1. Algorithm:

  • (1) Select an element from the sequence and make it the reference;

  • (2) To reorder the sequence, all the elements smaller than the base are placed in front of the base, and all the elements larger than the base are placed behind the base (the same elements can be placed on either side). This process is called partitioning

  • (3) Recursively sort the partition of elements smaller than the benchmark and those larger than the benchmark respectively

Example:
void quick_sort(int data[], size_t left, size_t right) { size_t p = (left + right) / 2; int pivot = data[p]; size_t i = left, j = right; While (I < j) {for (; ! (i >= p || pivot < data[i]); If (I < p) {data[p] = data[I]; if (data[p] = data[I]; p = i; } for (; ! (j <= p || data[j] < pivot); --j) {} if (j > p) { data[p] = data[j]; p = j; } } data[p] = pivot; if (p - left > 1) { quick_sort(data, left, p-1); } if (right - p > 1) { quick_sort(data, p + 1, right); }}Copy the code

2. Evaluation:

Average time complexity, order NlogN, log base N of N log2. Unstable. It’s the fastest sorting algorithm if you can divide the sequence equally every time. Each time the number of greater than the base value and the number of less than the base value of the difference is very small, the less time consumed.

Example 2: Implement the quicksort method in the C library
void quick_sort2(void* base, size_t left, size_t right, size_t size, int(*compar)(const void*, Const void*)) {// memcpy(pa, pb, size); Size_t p = (left + right) / 2; size_t p = (left + right) / 2; void* pivot = malloc(size); memcpy(pivot, base + p * size, size); size_t i = left, j = right; while (i < j) { for (; ! (i >= p || compar(base+i*size, pivot) > 0); ++i) {} if (i < p) { memcpy(base+p*size, base+i*size, size); p = i; } for (; ! (j <= p || compar(base+j*size, pivot) < 0); --j) {} if (j > p) { memcpy(base+p*size, base+j*size, size); p = j; } } memcpy(base + p * size, pivot, size); free(pivot); if (p - left > 1) { quick_sort2(base, left, p - 1, size, compar); } if (right - p > 1) { quick_sort2(base, p + 1, right, size, compar); } } void myqsort(void* base, size_t nmemb, size_t size, int(*compar)(const void*, const void*)) { quick_sort2(base, 0, nmemb - 1, size, compar); } int main(void) {int na[] = {55,23,65,2,4,75}; size_t size = sizeof(na[0]); size_t numb = sizeof(na) / size; Qsort (na, numb, size, cmpint); qsort(na, numb, size, cmpint); myqsort(na, numb, size, cmpint); size_t i; for (i = 0; i < numb; ++i) { printf("%d ", na[i]); } printf("\n"); const char* sa[] = {"daf", "ddeee", "rre", "awq", "bbfu"}; size = sizeof(sa[0]); numb = sizeof(sa) / size; //qsort(sa, numb, size, cmpstr); myqsort(sa, numb, size, cmpstr); for (i = 0; i < numb; ++i) { printf("%s ", sa[i]); } printf("\n"); return 0; } /* Output: 2 4 23 55 65 75 awq bbfu daf ddeee rre */Copy the code

Merge sort

1. Algorithm:

  • (1) Apply for a space that is the sum of the two sorted sequences, which is used to store the combined sequence

  • (2) Set two Pointers, the initial positions are respectively the starting positions of the two sorted sequences

  • (3) Compare the elements pointed to by the two Pointers, select the relatively small element into the merge space, and move the pointer to the next position

  • (4) Repeat Step 3 until a pointer reaches the end of the sequence

  • (5) Copy all the remaining elements of the other sequence directly to the end of the merged sequence

2. Evaluation:

Average time complexity, O(2NlogN). Stable, insensitive to data order. Non-in-place sorting, which requires the same amount of auxiliary space as the sequence to be sorted, is not suitable for sorting large amounts of data.

Example:
Void outer_merge(int data1[], size_t size1, int data2[], size_t size2, int data2[], size_t size2, int data3[]) { size_t i = 0, j = 0, k = 0; for (;;) { if (i < size1 && j < size2) { if (data1[i] < data2[j]) { data3[k++] = data1[i++]; } else { data3[k++] = data2[j++]; } } else if (i < size1) { data3[k++] = data1[i++]; } else if (j < size2) { data3[k++] = data2[j++]; } else { break; Void inner_merge(int data[], size_t left, size_t mid, int data[], size_t left, size_t mid, size_t right) { size_t size = (right - left + 1) * sizeof(int); int* merge = malloc(size); outer_merge(data + left, mid - left + 1, data + mid + 1, right - mid, merge); memcpy(data + left, merge, size); free(merge); } // merge sort void merge_sort(int data[], size_t left, size_t right) {if (left < right) {int mid = (left + right) / 2; merge_sort(data, left, mid); merge_sort(data, mid + 1, right); inner_merge(data, left, mid, right); }}Copy the code