Common sorting algorithm C language version of the implementation of sample collation
- 2020-05-09 19:01:36
- OfStack
Sorting is the process of organizing the records in a file in ascending (or descending) order of keywords. Its exact definition is as follows:
Input: n records R1, R2... , Rn, and the corresponding keywords are K1, K2... , Kn.
Output: Ril, Ri2,... , Rin, so that Ki1≤Ki2≤... Kin or less. (or Ki1 acuity Ki2 p... Kin or higher).
The time cost of sort can be measured by the number of data comparisons in the execution of the algorithm and the number of data moves. The basic sorting algorithms are as follows: swap sort (bubble sort, quicksort), selection sort (direct selection sort, heap sort), insertion sort (direct insertion sort, hill sort), merge sort, allocation sort (radix sort, box sort, count sort). The code for each algorithm is listed below and analyzed briefly. The code for the allocation sort algorithm is not listed.
(1) the quick sort, quick sort is C R. A. Hoare in 1962 put forward a kind of exchange sort. It USES a divide-and-conquer strategy, commonly known as divide-and-conquer (Divide-and-ConquerMethod). At best, the average complexity is O(nlogn), and at worst, O(n^2).
void quick_sort1(int a[],int l,int r)
{
if(l >= r)
return;
int i, j, p;
i = l-1, j = l,p = a[r];
while(j < r)
{
if(a[j] < p)
swap(a[++i], a[j]);
j++;
}
swap(a[++i], a[r]);
quick_sort1(a, l, i-1);
quick_sort1(a, i+1, r);
}
The pseudo-code for this program is given in , introduction to algorithms 1. Calling this program causes stack overflow when array elements are equal, reverse, or in order. Because every division is the worst. I can improve it by 1. The standard partition elements selected by the above program are fixed each time. If they are randomly generated, the probability of worst-case partition can be greatly reduced.
void quick_sort2(int a[],int l,int r)
{
if(l >= r)
return;
int i,j,p;
i = l-1,j = l;
p=l + rand()%(r-l); // Randomly generated [l,r) Between the number of
swap(a[p], a[r]);
p = a[r];
while(j < r)
{
if(a[j] < p)
swap(a[++i], a[j]);
j++;
}
swap(a[++i], a[r]);
quick_sort2(a, l, i-1);
quick_sort2(a, i+1, r);
}
However, stack overflow still occurs when array elements are equal. You can make the following adjustments.
void quick_sort3(int a[],int l,int r)
{
if(l >= r)
return;
int i,j,p;
i = l-1, j = r, p = a[r];
while(1)
{
do { i++; } while(a[i] < p && i < r);
do { j--; } while(a[j] > p && j > l);
if(i >= j)
break;
swap(a[i], a[j]);
}
swap(a[i],a[r]);
quick_sort3(a, l, i-1);
quick_sort3(a, i+1, r);
}
However, stack overflow also occurs when the array elements are in reverse order. If you combine the two, you can avoid stack overflow as much as possible.
void quick_sort4(int a[],int l,int r)
{
if(l >= r)
return;
int i,j,p;
i = l-1, j = r;
p = l + rand()%(r-l);
swap(a[p],a[r]);
p = a[r];
while(1)
{
do { i++; } while(a[i] < p && i < r);
do { j--; } while(a[j] > p && j > l);
if(i >= j)
break;
swap(a[i], a[j]);
}
swap(a[i], a[r]);
quick_sort4(a, l, i-1);
quick_sort4(a, i+1, r);
}
Bubble sort: compare the keywords of the records to be sorted in pairs, and when the two records are found in opposite order, they are exchanged until there are no records in reverse order.
void bubble_sort1(int a[],int n)
{
int i,j;
for(i = 0; i < n-1; i++)
{
for(j = i+1; j < n; j++)
{
if(a[i] > a[j])
swap(a[i], a[j]);
}
}
}
can be slightly improved to O(n) when the array number elements are ordered. Add a variable, and if no swap occurs during the 1 scan, end the sorting because the array is sorted.
void bubble_sort2(int a[],int n)
{
int i,j;
for(i = 0; i < n-1; i++)
{
bool exchange = false;
for(j = i+1; j < n; j++)
{
if(a[i] > a[j])
{
exchange = true;
swap(a[i], a[j]);
}
}
if(exchange == false)
break;
}
}
has been pointed out by netizens that there is a problem with the bubble sorting above and the correct results cannot be obtained. Here's how to write it:
void bubble_sort2(int a[],int n)
{
int i,j;
for(i = 0;i < n-1; i++)
{
bool exchange = false;
for(j = n-1;j > i; j--)
{
if(a[j-1] > a[j])
{
exchange = true;
swap(a[j-1], a[j]);
}
}
if(exchange == false)
break;
}
}
(3) direct selection sort: the record with the smallest keyword is selected from the records to be sorted every time, and the order is placed at the end of the sorted sub-files until all the records are sorted.
void select_sort1(int a[],int n)
{
int i,j;
for(i = 0; i < n-1; i++)
{
int min = i;
for(j = i+1; j < n; j++)
{
if(a[j] < a[min])
min = j;
}
if(min != i)
swap(a[i], a[min]);
}
}
(4) heap sorting: according to the input data, the initial heap is formed by the adjustment algorithm of the heap, and then the root and tail elements are swapped, the total number of elements is reduced by 1, and then adjusted from the root down. Heap sort best, worst, average time complexity is O(nlogn)
void heap_siftdown(int a[],int n,int p) // Adjust algorithm
{
int i = p,j = i*2+1;
int tmp = a[i];
while(j < n)
{
if(j+1 < n && a[j] < a[j+1])
j++;
if(a[j] <= tmp)
break;
else
{
a[i] = a[j];
i = j;j = j*2+1;
}
}
a[i] = tmp;
}
void heap_sort1(int a[],int n)
{
int i;
for(i = (n-1)/2; i >= 0;i--)
heap_siftdown(a, n, i);
for(i = n-1;i >= 0; i--)
{
swap(a[i], a[0]);
heap_siftdown(a, i, 0);
}
}
(5) direct insertion sort: one record at a time to be sorted is inserted by its keyword size into the appropriate location in the previously sorted subfile until the insertion of all the records is complete. When the array is sorted, the time complexity of direct insertion sort is O(n)
void insert_sort1(int a[],int n)
{
int i,j;
for(i = 1; i < n; i++)
{
for(j = i; j > 0 && a[j]<a[j-1]; j--)
swap(a[j-1], a[j]);
}
}
sorts faster if you expand the swap function.
void quick_sort2(int a[],int l,int r)
{
if(l >= r)
return;
int i,j,p;
i = l-1,j = l;
p=l + rand()%(r-l); // Randomly generated [l,r) Between the number of
swap(a[p], a[r]);
p = a[r];
while(j < r)
{
if(a[j] < p)
swap(a[++i], a[j]);
j++;
}
swap(a[++i], a[r]);
quick_sort2(a, l, i-1);
quick_sort2(a, i+1, r);
}
can be further improved. The algorithm of insert_sort2 continuously assigns values to t, and the assignment statement can be moved out of the loop.
void quick_sort2(int a[],int l,int r)
{
if(l >= r)
return;
int i,j,p;
i = l-1,j = l;
p=l + rand()%(r-l); // Randomly generated [l,r) Between the number of
swap(a[p], a[r]);
p = a[r];
while(j < r)
{
if(a[j] < p)
swap(a[++i], a[j]);
j++;
}
swap(a[++i], a[r]);
quick_sort2(a, l, i-1);
quick_sort2(a, i+1, r);
}
(6) hill sort: first take an integer d1 less than n as the first increment, and divide all the records of the file into d1 groups. All records with distances that are multiples of dl are placed in the same group. First, directly insert people into each group; Then, take the second increment, d2
<
d1 repeats the above grouping and sorting until the increment dt=1(dt) is taken
<
dt-l
<
...
<
d2
<
d1), that is, until all records are placed in the same group for direct insertion sort.
The last increment of must be 1, which is just calling the direct insertion sort algorithm.
void quick_sort2(int a[],int l,int r)
{
if(l >= r)
return;
int i,j,p;
i = l-1,j = l;
p=l + rand()%(r-l); // Randomly generated [l,r) Between the number of
swap(a[p], a[r]);
p = a[r];
while(j < r)
{
if(a[j] < p)
swap(a[++i], a[j]);
j++;
}
swap(a[++i], a[r]);
quick_sort2(a, l, i-1);
quick_sort2(a, i+1, r);
}
(7) merge sort: sorts using the "merge" technique. Merge is the merging of several sorted subfiles into one ordered file. It can be used for external sorting.
void merge_sort1(int a[],int b[],int l,int r)
{
if(l >= r)
return;
int m = (l+r)/2;
merge_sort1(a, b, l, m);
merge_sort1(a, b, m+1, r);
merge1(a, b, l, m, r);
}
void merge1(int a[],int b[],int l,int m,int r)
{
int i,j,k;
for(i = l; i <= r; i++)
b[i] = a[i];
i = l; j = m+1; k = l;
while(i <= m && j <= r)
{
if(b[i] <= b[j]) a[k++] = b[i++];
else a[k++] = b[j++];
}
while(i <= m) a[k++] = b[i++];
while(j <= r) a[k++] = b[j++];
}
gives the test driver and two auxiliary programs for the program of the above algorithm. To test a sorting algorithm, simply remove the comment.
void quick_sort2(int a[],int l,int r)
{
if(l >= r)
return;
int i,j,p;
i = l-1,j = l;
p=l + rand()%(r-l); // Randomly generated [l,r) Between the number of
swap(a[p], a[r]);
p = a[r];
while(j < r)
{
if(a[j] < p)
swap(a[++i], a[j]);
j++;
}
swap(a[++i], a[r]);
quick_sort2(a, l, i-1);
quick_sort2(a, i+1, r);
}