Summarize and discuss three kinds of sorting methods commonly used in C
- 2020-04-01 23:30:05
- OfStack
Our statistics class student achievement, for example, so is usually carried out in accordance with the student id to the statistics, the result is arranged, it is not suitable for our query to the result, so we are commonly scores query before the first sort, such as sorted by high to low, so that you can quickly find out the highest and lowest points of class, and the front or back of the students.
There are many kinds of sorting methods, there are three commonly used: bubble sort, selection sort, insertion sort, and so on, we will do a little analysis and comparison of these three methods, so that we can better understand and application.
Bubble sort
1, the basic idea of bubble sort: for n number of sorting (assuming from big to small order now, all of the following are) according to this, the adjacent two Numbers in comparison, dispatch number before him: that is the first and second digits, tarsus put before and after the decimal, the second and third comparison, after large feed, decimal before, and so on... After the first round of comparison, we found a minimum number at the bottom. And then we do the next round of comparisons, so we don't have to do the last one, so we have one less round of comparisons.
Obviously, it is necessary to design this problem with double loop. The number of rounds of outer loop control and the number of times of comparison of each round of inner loop control, then how many rounds and how many times of each round are needed? Let's see through an example:
2. Examples of sorting process:
Outer loop 1 round 2 rounds Three rounds 4 wheels Inner loop Five Numbers are compared four times Four Numbers are compared three times Three Numbers are compared twice Two Numbers are compared one time 7 5 8 6 9 1 time 2 times 3 times 4 times 1 time 2 times 3 times 1 time 2 times 1 time 7 5 8 6 9 7 8 5 6 9 7 8 6 5 9 7 8 6 9 5 8 7 6 9 5 8 7 6 9 5 8 7 9 6 5 8 7 9 6 5 8 9 7 6 5 9 8 7 6 5 The smallest number, 5, sinks, and the remaining four Numbers continue to compare The decimal six sinks, and the other three Numbers 7 bottom, the other two Numbers comparison The last two Numbers are compared once
So by doing this sort process, we know how to sort, and then we can figure out who are the bubbles, and then we can sort from the big to the small, and the big Numbers are the bubbles. As the sorting goes on, the bubbles gradually rise.
From this kind of sorting, we can also see that 5 Numbers actually go through 4 rounds, and it has been proved by practice that n Numbers need at most n-1 rounds of sorting.
3. The bubble sort procedure is as follows:
for(i=0;i<10;i++)
for(j=0;j<10-i;j++)
if(a[j]<a[j+1])
{t=a[j];a[j]=a[j+1];a[j+1]=t;}
Add the input part to the top of the segment and the sorted output to the segment.
Program improvements:
4. Algorithm improvement:
From the above sorting process, we can see that if a group of Numbers has been sorted or after a few rounds can be sorted out, but the loop still needs to continue, so the design of the program wastes a lot of time, so we can redesign the algorithm.
The modified procedure is as follows:
for(i=0;i<10&&!swap;i++)
{
swap=1;
for(j=0;j<10-I;j++)
if(a[j]<a[j+1])
{t=a[j];a[j]=a[j+1];a[j+1]=t;swap=0;}
}
Second, selection sort
1: the basic idea of, sorting, since the first number first, compare the first number and the number of the other, if is bigger than the first number will swap places, otherwise not exchanged, so after the first round of the comparison we can find out the maximum in the first place, and then from the second position to find time, large Numbers in turn like this, and to the whole number of sorting, practice has proved that the n number up to n - 1 round sorting.
2. Examples of sorting process:
Outer loop
1 round
2 rounds
Three rounds
4 wheels
Inner loop
Five Numbers are compared four times
Four Numbers are compared three times
Three Numbers are compared twice
Two Numbers are compared one time
7
5
8
6
9
1 time
2 times
3 times
4 times
1 time
2 times
3 times
1 time
2 times
1 time
7
5
8
6
9
8
5
7
6
9
8
5
7
6
9
9
5
7
6
8
9
7
5
6
8
9
7
5
6
8
9
8
5
6
7
9
8
6
5
7
9
8
7
6
5
9
8
7
6
5
The largest number, 9, is found, and the remaining four are found
The next largest number is 8, and the other three
Seven is found, and the other two are found
The last two Numbers are compared once
Selection sort is easier to understand than bubbling and easier to program.
for(i=0;i<10;i++)
for(j=i+1;j<10;j++)
if(a[i]<a[j])
{t=a[i];a[i]=a[j];a[j]=t;}
For selection sort, we can also see a problem, such as the sorting of the first round, we are looking for is 9 is the maximum, so the other exchange completely is not necessary, there are other round, so we can figure out a way to cancel this kind of situation, that is to say we truly find the location of the maximum and then exchanged.
for(i=0;i<10;i++)
{ p=i;
for(j=i+1;j<10;j++)
if(a[p]<a[j])
p=j;
if(p!=i)
{t=a[i];a[i]=a[j];a[j]=t;}
}
After the algorithm is improved, the problem is solved well.
Insert sort
1, insertion sort, the basic idea: (assuming from big to small order), in turn, get a number from the back and front have sorted for comparison, the comparison process is already sorted in the number of the last a number, if more than this number, to continue to the front is, until I find number larger than it, and then put it behind, if has not been found, sure this number is compared to the first number, it is in the front of the first number.
In general, for a group of Numbers to be sorted by insertion sort, the first number can be selected as a group of Numbers that have been sorted. Then put the second one in the right place
2. The program is written as follows:
for(i=1;i<10;i++)//I could start at 0 or I could start at 1. Everything else is the same.
for(j=i;j>0;j--)
if(a[j]<a[j-1])
{t=a[j];a[j]=a[j-1];a[j-1]=t;}
For this program also has the need to repair the place, the above procedure of sorting is actually based on the exchange of ideas for sorting, also can undertake sorting in the true sense, i.e., to sort out the number of first, then find out the should insert position, find, after being inserted into the location of the data to back that row of original data has been removed in a temporary variable. This data is then inserted into the correct free location.
So for swap based insertion sort, we swap before we find the location, so we can improve the program as well. So the improvement of this procedure, certainly can not reduce the number of exchanges, because we know that if to find the location of the exchange, then must have found the original sorting results, so can only find the location, vacate the position, put the elements of a few procedures.
main()
{
int i,j,t,a[]={12,11,2,3,6,67,89,0,1,3};
for(i=1;i<10;i++)
{t=a[i];
j=i-1;
while(j>=0&&t>a[i])
{a[j+1]=a[j];
j--;
}
a[j+1]=t;
for(i=0;i<10;i++)
printf("%d ",a[i]);
printf("/n");
}
Above is for several kinds of sorting methods are discussed in this paper, on the issue of the sort, is a very important content of the program design, so in "data structure and algorithm" as an important content to do a thorough explanation, we only do a simple discussion here, for C language for beginners or are learning C language programming enthusiasts.