This article was last updated on February 9, 2022, and has not been updated for more than 18 days. If the article content or picture resources fail, please leave a message and feedback. I will deal with it in time. Thank you!
Array sorting
- Sorting algorithm is one of the most basic and important algorithms in programming.
- There are many sorting algorithms. The commonly used ones are selection method, bubbling method, comparison method and insertion method.
Selective sorting method
- 1. Select the subscript of the minimum number from n numbers, and then exchange the position between the minimum number and the first number;
- 2. In addition to the first number, the other n-1 numbers will select the next smaller number according to the method of step 1 and exchange positions with the second number;
- 3. Repeat step n-1 times, and finally form an increasing sequence.
- Sorting process diagram
- For example:
#include <stdio.h>
#define N 10
void main()
{
int i,j,x,min,a[N];
printf("Enter 10 integers randomly:\n");
for (i = 0; i < N; i++) {
scanf_s("%d", &a[i]);
}
for (i = 0; i < N - 1; i++) {
min = i;
for (j = i+1; j < N; j++){
if (a[j] < a[min]) {
min = j;
x = a[i];
a[i] = a[min];
a[min] = x;
}
}
}
for (i = 0; i < 10; i++) {
printf("%d,", a[i]);
}
}
bubble sort
- 1. Start from the first number and compare it with the adjacent number. If it is greater than this number, exchange the position.
- 2. After a round of sorting, the maximum number is changed to the bottom (that is, the decimal number rises and the large number sinks);
- 3. Except for the last number, the other n-1 numbers sink the next largest number according to the method of step:;
- 4. Repeat step n-1 times, and finally form an increasing sequence.
- Sorting process diagram
- example
#include <stdio.h>
#define N 10
main(){
int a[10];
int i,j,t;
printf("Enter ten integers:\n");
for (i = 0; i<N; i++) {
scanf_s("%d", &a[i]);
}
for (j = 0;j < N-1; j++) {
for (i = 0; i < N -1-j; i++) {
if (a[i] > a[i + 1])
{
t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
}
}
}
for (i = 0; i < N; i++) {
printf("%d，", a[i]);
}
}
Insertion and deletion of elements in an array
Algorithm for inserting sorting subprocess (based on ordered array):
- Suppose the number of inputs is a;
- Find the position of a in the array;
- Starting from this position, move it and the number behind it back in turn to vacate the position;
- Put a in this position.
- for example
#include <stdio.h>
main(){
int a[11] = {1,3,6,9,14,16,21,33,40,50};
int i,j,x=0;
for (i = 0; i<10; i++) {
printf("%d ", a[i]);
}
printf("\n");
printf("Enter an integer to insert:");
scanf_s("%d", &x);
for (i = 0; i <= 10; i++) {
if (a[i] > x) {
for (j = 10; j > i; j--) {
a[j] = a[j - 1];
}
a[i] = x;
break;
}
}
for (i = 0; i <=10; i++) {
printf("%d ", a[i]);
}
}
Algorithm for deleting sorting process:
- Suppose the number of deleted is num
- Find the position of num in the array;
- From this position, move the numbers behind it forward in turn
- For example:
#include <stdio.h>
main(){
int a[11] = {1,3,6,9,14,16,21,33,40,50};
int i,j,num=0;
for (i = 0; i<10; i++) {
printf("%d ", a[i]);
}
printf("\n");
printf("Enter an integer to delete:");
scanf_s("%d", &num);
for (i = 0; i < 10; i++) {
if (a[i] == num) {
break;
}
}
for (j = i; j <10; j++) {
a[j] = a[j + 1];
}
for (i = 0; i <9; i++) {
printf("%d ", a[i]);
}
}
lookup
Sequential search ideas:
- Compare the search key values with the elements in the array one by one, If it is the same, the search is successful; otherwise, the search fails.
- for example
#include <stdio.h>
main() {
int a[11] = { 1,3,6,9,14,16,21,33,40,50 };
int i, j, x = 0,y = 0;
for (i = 0; i < 10; i++) {
printf("%d ", a[i]);
}
printf("\n");
printf("Enter an integer to find:");
scanf_s("%d", &x);
for (i = 0; i <11; i++) {
if (a[i] == x) {
y = 1;
printf("Find number%d,Its subscript is%d", x, i);
break;
}
}
if (y == 0) printf("The number you entered was not found!");
}
Dichotomy search (half search)
- It can greatly improve the speed of search. It must be an ordered array.
- Find process diagram
- for example
#include <stdio.h>
main() {
int a[] = { 1,3,6,9,14,16,21,33,40,50,100};
int i,find=0, mid,x=0, top = 0,bot = 10;
for (i = 0; i <=10; i++) {
printf("%d ", a[i]);
}
printf("\n");
printf("Enter an integer to find:");
scanf_s("%d", &x);
do {
mid = (top + bot) / 2;
if (x > a[mid]) top = mid + 1;
if (x == a[mid]) find = 1;
if (x < a[mid]) bot = mid - 1;
printf("%d,%d,%d\n", top, mid, bot);
} while (top <= bot && find == 0);
if (find == 1)
printf("Find number%d\n", x);
else
printf("The number you entered was not found!\n");
}
Saddle point of two-dimensional array
- If an element is the largest in the row and the smallest in the column, it is called the saddle point of the array
- Idea:
- Find the largest element position of each row by row
- The largest element in a row is compared with all elements in the column where the element is located, Judge whether it is the smallest element. If yes, it is the saddle point, otherwise it is not the saddle point.
- For example:
#include<stdio.h>
#define N 3
#define M 3
main(){
int i, j, k, a[N][M], max, maxj, flag;
printf("Please enter an array:\n");
for (i = 0; i < N; i++){
for (j = 0; j < M; j++){
scanf_s("%d", &a[i][j]);
}
}
printf("\n");
for (i = 0; i < N; i++){
max = a[i][0]; // Assume a[i][0] maximum at the beginning
maxj = 0; //Assign column number 0 to maxj to save
for (j = 0; j < M; j++){ // Find the maximum number in line i
if (a[i][j] > max){
max = a[i][j]; // Put the maximum number of lines in max
maxj = j; // Store the column number of the maximum number in maxj
}
}
flag = 1; // Let's assume the saddle point, represented by flag as 1
for (k = 0; k < N; k++){
if (max > a[k][maxj]){ // Compare the maximum number with its column elements
flag = 0; // If max is not the smallest in the same column, it indicates that it is not a saddle point
continue;
}
}
if (flag){
printf("a[%d][%d]=%d\n", i, maxj, max); //Output the value of saddle point and the row and column number
break;
}
}
if (!flag){
printf("Saddle point does not exist!\n");
}
}
- Improved version (the above algorithm cannot judge some special array matrices)
#include<stdio.h>
#define N 3
#define M 3
main() {
int i, j, k,p, a[N][M], max, maxj, flag=0;
printf("Please enter an array:\n");
for (i = 0; i < N; i++) {
for (j = 0; j < M; j++) {
scanf_s("%d", &a[i][j]);
}
}
printf("\n");
for (i = 0; i < N; i++) {
max = a[i][0]; // Assume a[i][0] maximum at the beginning
maxj = 0; //Assign column number 0 to maxj to save
for (j = 0; j < M; j++) { // Find the maximum number in line i
if (a[i][j] > max) {
max = a[i][j]; // Put the maximum number of lines in max
}
}
for (j = 0; j < M; j++) { // Check whether the maximum value is the saddle point
if (a[i][j] == max) {
k = j;
p = 0;
while (p < N && max <= a[p][k]) {
p++;
}
if (p == N) {
printf("a[%d][%d]=%d\n", i, k, max);
flag = 1;
}
}
}
if (flag == 0) {
printf("Saddle point does not exist!\n");
}
}
}
Array considerations
- Input data char a[20] to the character array with scanf function;
- scanf("%s",&a); error
- scanf(%s",a); correct
- Input data int a[20] to numerical array with scanf function;
- scanf("%d",a); error
- Scanf (% d ", & A); correct
- Reference array elements with [].
- int i, a(10); For (I = 0; I < 10; I + +) scanf (% d ", & A (I)); error
- int i, a(10); For (I = 0; I < 10; I + +) scanf (% d ", &a [i]); correct
- The maximum subscript that an array element can use
- int i,a[10]={1}; For (I = 1; I < = 10; I + +) printf (% d ", a [i]); error
- int i,a[10]={1}; For (I = 1; I < = 9; I + +) printf (% d ", a [i]); or for (I = 1; I < 10; I + +) printf (% d", a [i]); correct
- Definition and reference of two-dimensional data or multi-dimensional array
- int a[4,5]; a[1+2,2+2]=5; error
- int[10]; correct
- Mistakenly assume that the array name represents all elements of the array
- int a[4]={1,3,5,7},b[4]; b=a; char str[4]; str="computer"; error
- Confusing the representation of character strings
- char sex; sex="M"; error
- char sex; sex= ' M '; correct