C language bubble sort hill sort and other algorithm examples
- 2020-04-02 02:17:46
- OfStack
Implement the following sort
Insertion sort order n^2.
Bubble sort order n^2.
Choose sort order n^2.
Quick sort order n log n.
Heap sort order n log n.
Merge sort order n log n.
Hill sort order n to the 1.25.
1. Insertion sort O(n^2)
Generally, insertion sort is implemented on an array using in-place. The specific algorithm is described as follows:
A starts with the first element, which can be considered sorted
B. takes the next element and scans backwards and forwards through the sorted sequence of elements
If the element (sorted) is greater than the new element, move the element to the next location
Repeat step 3 until you find the position where the sorted element is less than or equal to the new element
⒌ insert the new element to the next location
Picture repeat steps 2~5
If the comparison operation is more expensive than the swap operation, binary search can be used to reduce the number of comparison operations. The algorithm can be considered as a variant of insertion sort, called binary search sort.
void insert_sort(int* array,unsignedint n){
int i,j;
int temp;
for(i=1;i<n;i++){
temp=*(array+i);
for(j=i;j>0&&*(array+j-1)>temp;j--){
*(array+j)=*(array+j-1);
}
*(array+j)=temp;
}
}
2. Bubble sort O(n^2)
The bubble sort algorithm works as follows:
Compare adjacent elements. If the first one is bigger than the second, you swap them.
Do the same for each pair of adjacent elements, starting with the first pair and ending with the last pair. At this point, the last element should be the largest number.
Repeat the above steps for all elements except the last one.
Keep repeating the above steps for fewer and fewer elements at a time until there are no pairs of Numbers to compare.
#include<stdio.h>
#defineSIZE8
void bublle_sort(int a[],int n){//N is the number of elements in array a
int i,j,temp;
for(j=0;j<n-1;j++)
for(i=0;i<n-1-j;i++)
if(a[i]>a[i+1]){//The array element sizes are arranged in ascending order
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
}
int main(){
int number[SIZE]={95,45,15,78,84,51,24,12};
int i;
bublle_sort(number,SIZE);
for(i=0;i<SIZE;i++){
printf("%d",number[i]);
}
printf("n");
}
3. Choose sort O(n^2)
void select_sort(int * a, int n){
register int i, j, min, t;
for( i =0; i < n -1; i ++) {
min = i; //Find minimum
for( j = i +1; j < n; j ++)
if( a[min] > a[j])
min = j; //exchange
if(min != i) {
t = a[min];
a[min] = a[i];
a[i] = t;
}
}
}
4. Quicksort order n log n.
void QuickSort(int a[],int numsize){//A is an array of integers, and numsize is the number of elements
int i=0,j=numsize-1;
int val=a[0];//Specifies the reference value val size
if(numsize>1){//Make sure the array length is at least 2, otherwise you don't need to sort
while(i<j{//Loop end condition
for(;j>i;j--)//Search backward for elements smaller than val, fill in a[I] and jump out of the loop
if(a[j]<val){
a[i]=a[j];break;
}
for(;i<j;i++)//Search from front to back for elements larger than val, fill in a[j] and jump out of the loop
if(a[i]>val){
a[j]=a[i];break;
}
}
a[i]=val;//Put the number saved in val into a[I]
QuickSort(a,i);//Recursively, sort the first I's
QuickSort(a+i+1,numsize-1-i);//I +1 to numsize the numsize minus 1 minus I
}
}
5. Heap sort order (n log n)
N keyword sequence Kl, K2... , Kn is called (Heap) if and only if the sequence satisfies the following property (Heap property for short) :
(1) ki
<
= k (2 I) and ki
<
Is equal to k of 2i plus 1 times 1 less than or equal to I less than or equal to n
>
The = sign. //k(I) is equivalent to the non-leaf node of the binary tree, k(2i) is the left child node, and k(2i+1) is the right child node.
If the vector R[1..n] stored in this sequence is regarded as the storage structure of a complete binary tree, then the heap is essentially a complete binary tree satisfying the property that the keyword of any non-leaf node in the tree is not greater than (or less than) the keyword of its left and right children (if any) node.
//Array is the heap array to be adjusted, I is the position of the array elements to be adjusted, and nlength is the length of the array
//This function builds a large root heap from an array
void HeapAdjust(int array[], int i, int nLength)
{
int nChild;
int nTemp;
for (nTemp = array[i]; 2 * i + 1 < nLength; i = nChild)
{
//The position of the child is equal to 2* (parent position) + 1
nChild = 2 * i + 1;
//You get the larger of the children
if ( nChild < nLength-1 && array[nChild + 1] > array[nChild])
++nChild;
//If the larger child is greater than the parent then move the larger child up and replace its parent
if (nTemp < array[nChild])
{
array[i] = array[nChild];
array[nChild]= nTemp;
}
else
//Otherwise exit the loop
break;
}
}
//Heap sort algorithm
void HeapSort(int array[],int length)
{
int tmp;
//Adjust the first element of the sequence, after which the first element is the largest element of the sequence
//Length /2-1 is the first non-leaf node, where "/" is divisible
for (int i = floor(length -1)/ 2 ; i >= 0; --i)
HeapAdjust(array, i, length);
//Adjust the sequence from the last element, narrowing the scope of the adjustment until the first element
for (int i = length - 1; i > 0; --i)
{
//Swap the first element with the current last element,
//Ensure that the current last element is the largest in the current sequence
/// Swap(&array[0], &array[i]);
tmp = array[i];
array[i] = array[0];
array[0] = tmp;
//Continually reduce the size of the adjustment heap, making sure that the first element is the maximum value of the current sequence after each adjustment
HeapAdjust(array, 0, i);
}
}
6. Merge sort order n log n.
By combining the ordered subsequences, a completely ordered sequence is obtained. That is, make each subsequence ordered first, and then make the subsequence ordered between segments. If the two of them An ordered table is merged into an ordered table, called a two-way merge.
//Merge operation
void Merge(int sourceArr[], int targetArr[], int startIndex, int midIndex, int endIndex)
{
int i, j, k;
for(i = midIndex+1, j = startIndex; startIndex <= midIndex && i <= endIndex; j++)
{
if(sourceArr[startIndex] < sourceArr[i])
{
targetArr[j] = sourceArr[startIndex++];
}
else
{
targetArr[j] = sourceArr[i++];
}
}
if(startIndex <= midIndex)
{
for(k = 0; k <= midIndex-startIndex; k++)
{
targetArr[j+k] = sourceArr[startIndex+k];
}
}
if(i <= endIndex)
{
for(k = 0; k <= endIndex- i; k++)
{
targetArr[j+k] = sourceArr[i+k];
}
}
}
//Recursion is used internally, and the space complexity is n+logn
void MergeSort(int sourceArr[], int targetArr[], int startIndex, int endIndex)
{
int midIndex;
int tempArr[100]; //Here the size changes as required
if(startIndex == endIndex)
{
targetArr[startIndex] = sourceArr[startIndex];
}
else
{
midIndex = (startIndex + endIndex)/2;
MergeSort(sourceArr, tempArr, startIndex, midIndex);
MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
Merge(tempArr, targetArr,startIndex, midIndex, endIndex);
}
}
//call
int _tmain(int argc, _TCHAR* argv[])
{
int a[8]={50,10,20,30,70,40,80,60};
int b[8];
MergeSort(a, b, 0, 7);
for(int i = 0; i < sizeof(a) / sizeof(*a); i++)
cout << b[i] << ' ';
cout << endl;
system("pause");
return 0;
}
7. Hill sort O (n ^ 1.25)
Take an integer less than n, d1, as the first increment, and divide all the records in the file into d1 groups. All records of distance multiples of d1 are placed in the same group. First, direct insertion sort is performed in each group. And then you take the second increment, d2
<
D1 repeat the above grouping and sorting until the increment dt=1(dt)
<
Dt l.
<
...
<
d2
<
D1), that is, until all records are placed in the same group for direct insertion sort.
void ShellSort(int a[], int n){
int d, i, j, temp;
for(d = n/2;d >= 1;d = d/2){
for(i = d; i < n;i++){
temp = a[i];
for(j = i - d;(j >= 0) && (a[j] > temp);j = j-d){
a[j + d] = a[j];
}
a[j + d] = temp;
}
}
}