1. Select Sort (bubble sort)
Ascending order
Compare the first element with other elements. If the element is more than other elements, exchange it to ensure that the element is the smallest. Then use the second element to compare the others afterwards to ensure that the second element is the smallest except the first one. Loop in turn until the entire array.
/// <summary>
/// Select Sort /// </summary>
public class Selection:BaseSort
{
public static long usedTimes = 0;
public Selection()
{
}
public static void Sort(IComparable[] a)
{
Stopwatch timer = new Stopwatch();
();
for (var i = 0; i < ; i++)
{
int minIndex = i;
for (var j = i + 1; j < ; j++)
{
if (Less(a[j], a[minIndex]))
{
Exch(a, j, minIndex);
//minIndex = j;
}
}
}
//The number of exchanges is smaller, the internal loop only exchanges the index, and finally exchanges the value //for (var i = 0; i < ; i++)
//{
// int minIndex = i;
// for (var j = i + 1; j < ; j++)
// {
// if (Less(a[j], a[minIndex]))
// minIndex = j;
// }
// Exch(a, minIndex, i);
//}
();
usedTimes = ;
}
}The inner loop of this algorithm is to compare the current element with other elements. The code of the swap element is written outside the inner loop. Each exchange can arrange an element, so the total number of swaps is N. Therefore, the time efficiency of the algorithm depends on the number of comparisons.
From the code, we can see that any i between 0 and N-1 will undergo an exchange and N-1-i comparison, so there are a total of N exchanges and (N-1)+ (N-2)+ ...+2+1 = N(N-1)/2 ~ N^2 / 2 comparisons.
shortcoming
To find out the smallest element, it needs to scan the array, but this does not provide any information for the next scan of the array. Sorting an ordered array or an array with all the same primary keys also requires the same time as sorting a random array.
advantage
Less data movement. The number of swaps and array size are linear.
2. Insert sort
Insert an element into an ordered array, the right element needs to be moved one by one.
Like the selection sort, all elements to the left of the current index are ordered, but their final position is still uncertain, and to make room for smaller elements they may be moved. When the index reaches the rightmost end, the array sorting is complete. At the beginning, it can be considered that the first element is an ordered array.
Unlike select sorting, the time required for insertion sorting depends on the initial order of the elements. An array that is ordered partially is much faster than a random array.
public class Insertion : BaseSort
{
public static long usedTimes = 0;
public static void Sort(IComparable[] a)
{
Stopwatch timer = new Stopwatch();
();
/*
* Compare the value of the current position with the previous one, if it is small, swap it,
* Then continue with the value of the previous position,
* Until a value larger than it is encountered, stop the inner loop,
* It is equivalent to comparing the current value with the ordered array on the left in sequence. If the current value is small, exchange it. If an element larger than the current value is encountered, it will jump out of the inner loop, which means that the appropriate position has been found.
*/
for (var i = 0; i < ; i++)
{
for (var j = i; j > 0 && Less(a[j], a[j - 1]); j--)
{
Exch(a, j, j - 1);
}
}
/*
* temp stores the current value
* Then compare temp with the value on the left one by one
* If temp is small, move the comparison value one by one to the right until it encounters a number larger than temp or ends
* Put temp to the current position +1
*/
//int N = ;
//for (int i = 1; i < N; i++)
//{
// IComparable temp = a[i];
// int j;
// for (j = i - 1; j >= 0 && Less(temp, a[j]); j--)
// {
// a[j + 1] = a[j];
// }
// a[j + 1] = temp;
//}
();
usedTimes = ;
}
}For worst-case (reverse order), insertion sort requires ~ N^2 / 2 comparisons and ~ N^2 / 2 exchanges. Because each loop requires i comparison and exchange (1+2...+N-1)*N.
For the best case (all ordered), insertion sort requires N-1 comparisons and 0 exchanges. Because it is ordered, there is no need to exchange, just compare each loop.
For randomly arranged arrays, insertion sorting requires ~ N^2 / 4 comparisons and ~ N^2 / 4 exchanges on average. Random arrays On average, each element has the potential to move half the length of the array.
The number of times the insert sort comparison is the number of times the swap is plus an additional term, which is N minus the number of times the inserted element is exactly the smallest element known. In the best case (all ordered), each element is the smallest element known, so this item is N-1.
Insertion sorting works well for non-random arrays (partially ordered). For example, an ordered array or an array with all the same primary keys has a linear run time.
Now consider the general situation, partially ordered arrays. Inversion refers to two elements in an array that are inverted in sequence. For example, there are 11 pairs of inverted in E X A M P L E: E-A, X-A, X-M, X-P, X-L, X-E, M-L, M-E, P-L, P-E, L-E. If the number of inverted in an array is less than a multiple of the array size, the array is partially ordered.
Here is a typical partially ordered array:
Each element in the array is not far from its final position;
An ordered large array followed by a small array;
The location of only a few elements in the array is uncertain;
When the number of inverted is small, insert sorting may be faster than any sorting algorithm.
The number of swaps required for insertion sorting is the same as the number of inverted in the array, and each swap is equivalent to reducing a pair of inverts. The number of times that need to be compared is greater than or equal to the inverted number, and the number less than or equal to the inverted plus the size of the array is reduced by one. Because each i between 1 and N-1 requires a comparison, and then each exchange corresponds to a comparison, there may be a cross between these two comparisons, so it is less than or equal to.
The above insert sorting algorithm code is exchanged as long as it encounters a larger element than the current element. This section can be optimized, and the code commented above can reduce the number of array accesses.
The insert sort run time is about half the time you choose sort.
This is all about this article on C# implementing bubble sorting and insertion sorting algorithms. I hope it will be helpful to everyone's learning and I hope everyone will support me more.