# Sorting and searching

Sorting - selection, bubbling

Search - sequential, binary search

1. Select Sorting

Starting from the first number, find the maximum value by comparing with the following numbers each time, put the maximum value in the current position, and the value of the number in the current position in the position of the maximum value, and cycle successively until it reaches the last number.

Example: input a positive integer n (1 < n < = 9), input n positive numbers, sort them from small to large by selection method, and then output.

```#include<stdio.h>
#define MAXN 10
int main()
{
int i,index,k,n,temp;
int a[MAXN];
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}
//yes n Number sorting
for(k=0;k<n-1;k++){
index=k;                //index Used to store the subscript of the minimum value
for(i=k+1;i<n;i++){     //Find minimum subscript
if(a[i]<a[index]) index=i;
}
temp=a[index];            //Minimum and a[k] Element exchange,Change the minimum value to the current position, and put the number of the current position on the original position of the minimum value
a[index]=a[k];
a[i]=temp;
}
//Output sorted array
for(i=1;i<n;i++){
printf("%d",a[i]);
}
printf("\n");
return 0;
} ```

2. Bubble sorting

Carry out multiple cycles, and compare two adjacent numbers each time. In ascending order, put the large number behind.   Like bubbles, larger numbers sink and smaller numbers rise.

Example:

```#include <stdio.h>
int main(void)
{
int a[1001];
int n,i,j,t;
scanf("%d",&n);//n Number of to sort
//Enter the number to sort
for(i=0;i<n;++i)
scanf("%d",a+i);

//Next, sort
for(i=0;i<n-1;++i)//n number,A total of n-1 second
{                 //n-1 The number is finished,The first number must have returned
//Each time the maximum(Ascending order)Or minimum(Descending order)Put it at the back
for(j=0;j<n-i-1;++j)
{
if(a[j]>a[j+1])//Every bubble,Exchange
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
for(j=0;j<n;++j)
printf("%-5d ",a[j]);
printf("\n\n");
}

return 0;
}```

Optimization: in the sorting process, after the final sorting, although the data has been sorted completely, the program cannot judge whether the sorting is completed. In order to solve this problem, set a flag bit flag and set its initial value to non-0, indicating that the sorted table is an unordered table. Set the flag value to 0 before each sorting. During data exchange, Modify the flag to be non-0. Check this flag at the beginning of a new round of sorting. If this flag is 1, it means that no data exchange has been done last time, indicating that it is orderly; if the sequence has become orderly during the sorting process, it will not bubble, otherwise it will be sorted.

The code is as follows:

```for(i=0;i<n-1;++i)//n number,A total of n-1 second
{                 //n-1 The number is finished,The first number must have returned
//Each time the maximum(Ascending order)Or minimum(Descending order)Put it at the back
int f=1;//Set a switch variable here
for(j=0;j<n-i-1;++j)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
f=0;
}
}
if(1==f)//f 1 indicates that bubbling has not been carried out,Description sequence order
break;//If the sequence is ordered,Then you can jump out of sorting
}```

1. Sequential search

Sequential search refers to searching one by one from beginning to end.

Example code:

```#include<stdio.h>
int main()
{
int n,x,flag,i;
int a[10];
scanf("%d%d",&n,&x);
for( i=0;i<n;i++){
scanf("%d",&a[i]);
}
//lookup
flag=0;                                //set up flag Make a sign
for(i=0;i<n;i++){
if(a[i]==x){
printf("Idex is %d\n",i);    //find x，Then the subscript is output
flag=1;                        //Set flag A value of 1 indicates that it is found x
}
}
if(flag==0){
printf("No Found");                //flag Is 0, indicating that it was not found x
}
return 0;
}```

2. Binary search

The table as a binary lookup object must be an ordered table stored sequentially. The lookup process is to first take the midpoint element A[mid] (mid = (0 + n -1) / 2) of the entire ordered table A[0] ~ A[n - 1] If the keyword of is equal to the given value K, the search is successful. If K is small, the same operation is performed on the remaining left half. If K is large, the same operation is performed on the remaining right half.

There are two kinds: non recursive and recursive

Code 1: non recursive function part

```int Binary_search(int low,int high,int n)
{
int mid;
while(low<=high){
mid=(low+high)/2;
if(n==a[mid]){
breajk;
}else if(n<a[mid]){
high=mid-1;
}else if(n>a[mid]){
low=mid+1;
}
}
if(low<=high) return mid;    //Returns the subscript of the lookup number
else return -1;                    //Can't find```

Code 2: recursive function part

```int Binary_search_recursive(int *s,int length,int key,int L,int H)
{
int  M=(L+H)/2;
if(L>H)
return -1;　　　　//Can't find
if(key<s[M])
{
return (Binary_search_recursive(s,length,key,L,M-1));
}
else if(key>s[M])
{
return (Binary_search_recursive(s,length,key,M+1,H));
}
else
return (M);　　　　//M is the number of lookups
}```

Advantages: fewer cycles and higher program efficiency.

Added by DwarV on Sat, 06 Nov 2021 13:41:38 +0200