[Data Structure] Week 15 – Sorting

Inline, Hill, Quick, Select, Heap

Directory

quick sort

insertion sort

direct insertion sort

Hill sort

selection sort

heap sort

Quick Sort

[Problem description] Input a set of data, with 0 as the end of the input, use bubble sorting, selection sorting, and quick sorting methods to sort them from small to large, and give the sorted results.

[Input form] A set of data, with 0 as the end of the input

[Output form] Three kinds of sorted results

【Sample input】

9 8 4 5 7 2 10 6 0
【Sample output】

2 4 5 6 7 8 9 10

//quick sort
#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {
int num = arr[low];
while(low < high) {
while(low < high & amp; & amp; arr[high] > num) {
high--;
}
arr[low] = arr[high];
while(low < high & amp; & amp; arr[low] <=num) {
low + + ;
}
arr[high] = arr[low];
}
arr[low] = num;
return low;
}

void QuickSort(int arr[],int L,int R)
{
if(L<R){
int mid=partition(arr,L,R);
QuickSort(arr,L,mid-1);
QuickSort(arr, mid + 1, R);
}
}
void BubbleSort(int arr[],int n)
{
for(int i=0;i<n-1;i ++ )
{
for(int j=i + 1;j<n;j++)
{
if(arr[i]>arr[j])
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
}
void ChooseSort(int arr[],int n)
{
int minnum;
for(int i=0;i<n-1;i ++ )
{
minnum=i;
for(int j=i + 1;j<n;j++)
{
if(arr[minnum]>arr[j])
minnum=j;
}
int temp=arr[i];
arr[i]=arr[minnum];
arr[minnum]=temp;
}
\t
}
void travel(int arr[],int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
\t
cout<<endl;
\t
}
int main()
{
int x;
int a[100],b[100],c[100];
int n=0;
cin>>x;
while(x!=0)
{
a[n]=x;
b[n]=x;
c[n]=x;
cin>>x;
n + + ;
}
// travel(a,n);
BubbleSort(a,n);
ChooseSort(b,n);
QuickSort(c,0,n-1);
travel(a,n);
travel(b,n);
travel(c,n);
}

Insertion sort

Direct Insertion Sort

void DirecInsSort(int* a, int n)//direct insertion sort function
{
    int i, j, temp;
 
    for (i = 1; i < n; i ++ ) {//The first number is sorted by default, and its subscript is 0, so it starts from 1
        if (a[i] < a[i - 1])//If it is greater than it, just add it directly, which is equivalent to arranging
        {
            temp = a[i];
            for (j = i - 1; j >= 0 & amp; & amp; temp < a[j]; j--)//From the sequence that has been arranged, check from the back to the front
            {
                a[j + 1] = a[j];//Move one position backward
            }
            a[j + 1] = temp;
        }
    }
}

? Hill Sort

[Problem Description]Given a set of data, please use Hill sort to arrange it in ascending order.

【Input form】Original data, with 0 as the end of the input; the second line is the incremental value, only 3.

[Output format] The results after each incremental sort

【Sample input】

8 3 6 1 68 12 19 3 1 0

5 3 1

【Sample output】

8 3 3 1 68 12 19 6 1
1 3 1 8 6 3 19 68 12
1 1 3 3 6 8 12 19 68

【Sample input】

5 3 9 8 2 4 1 7 10 6 0

4 2 1

【Sample output】

2 3 1 7 5 4 9 8 10 6
1 3 2 4 5 6 9 7 10 8
1 2 3 4 5 6 7 8 9 10

// Hill sort
//8 3 6 1 68 12 19 3 1 0
#include <iostream>
using namespace std;

void Shell(int a[],int n,int incr)
{
int j;
for(int i=0;i + incr<n;i + + )
{
int x=a[i + incr];
for(j=i;j>=0;j-=incr)
{
if(x<a[j]) //18<10
{
a[j + incr]=a[j];
}
else break;
}
a[j + incr]=x;
}
}
void ShellSort(int a[],int n,int d[])
{
for(int i=0;i<3;i++)
{
Shell(a,n,d[i]);
for(int j=0;j<n;j++)
cout<<a[j]<<" ";
\t\t
cout<<endl;
}
}
int main()
{
int a[100],n,i=0;
while(cin>>a[i] & amp; & amp;a[i])//input data
i + + ;
n=i;
// Shell(a,n);
// for(int i=0;i<n;i + + )
// cout<<a[i]<<" ";
int d[10];
cin>>d[0]>>d[1]>>d[2];
ShellSort(a,n,d);
 }

Select Sort

Heap Sort

[Problem description] Please sort a set of data by heap sorting method, and give the results of building a heap and each heap sorting.
[Input form] A set of data, with 0 as the end of the input.
[Output form] The result of building the big root heap, and the result of each heap sorting.
【Sample input】

8 3 6 1 68 12 0

【Sample output】

68 8 12 1 3 6
12 8 6 1 3 68
8 3 6 1 12 68
6 3 1 8 12 68
3 1 6 8 12 68
1 3 6 8 12 68

【Sample input】

12 9 26 11 38 52 99 27 66 15 32 0

【Sample output】

99 66 52 27 38 12 26 9 11 15 32
66 38 52 27 32 12 26 9 11 15 99
52 38 26 27 32 12 15 9 11 66 99
38 32 26 27 11 12 15 9 52 66 99
32 27 26 9 11 12 15 38 52 66 99
27 15 26 9 11 12 32 38 52 66 99
26 15 12 9 11 27 32 38 52 66 99
15 11 12 9 26 27 32 38 52 66 99
12 11 9 15 26 27 32 38 52 66 99
11 9 12 15 26 27 32 38 52 66 99
9 11 12 15 26 27 32 38 52 66 99

Sorting Algorithm: Heap Sort [Illustration + Code]_哔哩哔哩_bilibili

//heap sort
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void SiftAdjust(int a[],int n,int i)
{
//n is the range of effective data in the a array, it gradually becomes smaller
//i is the number of the node to be adjusted
int f, left;//f is used to memorize parents left to calculate i's left child number
for(f=i,left=2*i + 1;left<=n-1;)//calculate the new child
{//f write down the node i to be adjusted, and keft becomes the subscript of the right child
if(left + 1<=n-1 & amp; & amp; a[left]<a[left + 1] )//the right child exists, and the value on the right is greater
left=left + 1;//left + + left becomes the subscript of the right child
if(a[left]>a[f])//The maximum value of the child is compared with the parent f, if the child is bigger, exchange
{
int t=a[left];
a[left]=a[f];
a[f]=t;
}
else break; // If the value of the child is small, it ends return
f=left; //Continue to adjust downwards, the child just now becomes the new parent, and then go up to calculate the new child
left=2*f + 1; //Calculate the new child, this sentence can also be put in for expression 3
}
\t
}
void HeapSort(int a[],int n)
{
//8 3 6 1 68 12 19 3 1
//k=0 1 2 3 4 5 6 7 8
//Adjust the middle node
for(int i=(n-2)/2;i>=0;i--)
{
SiftAdjust(a,n,i);
}
//Adjust the root node
for(int j=0;j<n;j++)
cout<<a[j]<<" ";
cout<<endl;
for(int i=0;i<n-1;i ++ )
{
int t=a[n-1-i];// n-1 n-2 n-3 n-4
a[n-1-i]=a[0];
a[0]=t;//exchange the first and last number
SiftAdjust(a,n-1-i,0);//adjust the remaining n-1-i maintenance root
for(int j=0;j<n;j++)
cout<<a[j]<<" ";
\t\t\t
cout<<endl;
}
}
int main()
{
int a[100],i=0;
     while(cin>>a[i] & &a[i])
     {
     i + + ;
}
int n=i;
HeapSort(a,n);
return 0;
 }

Maintain heap functions

void heapify(int arr[],int n,int i)
{
int largest=i;
int lson=i*2 + 1;
int rson=i*2 + 2;
\t
if(lson<n & amp; & amp; arr[largest]<arr[lson])
largest=lson;
if(rson<n & amp; & amp; arr[largest]<arr[rson])
largest=rson;
// Find the largest node among the three nodes
if(largest!=i)
{
swap( &arr[largest], &arr[i]);
heapify(arr,n,largest);
}
 }

4. Sort synthesis

[Title Description] Randomly generate 10,000, 20,000, 40,000, 80,000, and 160,000 plastic data, monitor the time required by the three sorting methods of bubble sort, selection sort, and quick sort, and display the sorting time. Other sorting methods that have been done before can be added for comparison.

[Description] This question is only submitted, not evaluated, and not scored.

// Hill sort
//8 3 6 1 68 12 19 3 1 0
#include <iostream>
#include <ctime>
#include <bits/stdc++.h>
using namespace std;

void InsSort(int a[],int n)
{
int j;
for(int i=0;i<n-1;i ++ )
{
int x=a[i + 1];
for(j=i;j>=0;j--)
{
if(x<a[j])
{
a[j + 1]=a[j];
}
else break;
}
a[j + 1]=x;
\t\t
}
}


void Shell(int a[],int n,int incr)
{
int j;
for(int i=0;i + incr<n;i + + )
{
int x=a[i + incr];
for(j=i;j>=0;j-=incr)
{
if(x<a[j]) //18<10
{
a[j + incr]=a[j];
}
else break;
}
a[j + incr]=x;
}
}
void ShellSort(int a[],int n,int d[])
{
for(int i=0;i<7;i++)
{
Shell(a,n,d[i]);
// for(int j=0;j<n;j++)
// cout<<a[j]<<" ";
\t\t
}
}
int main()
{
int a[200000],n=200000,i=0;
int b[200000];
srand(time(NULL));
for(i=0;i<n;i ++ )
b[i]=a[i]=rand();
\t\t

clock_t start, end;
start=clock();
int d[10]={79,11,7,5,3,1};//more and faster
\t
ShellSort(a,n,d);
end=clock();
cout<<(double)(end-start)/CLOCKS_PER_SEC;
\t
start=clock();
InsSort(b,n);
end=clock();
cout<<(double)(end-start)/CLOCKS_PER_SEC;
 }