Data Structures and Algorithms - 7-12 Sorting (25 points) (summary of sorting methods)

7-12 Sort (25 points)

Given N integers (in the range of long integers), output the result sorted from smallest to largest.

This question is designed to test the performance of various sorting algorithms on various data situations. The characteristics of each group of test data are as follows:

data 1: only 1 element;
Data 2: 11 different integers, test the basic correctness;
Data 3: 103 random integers;
data 4: 104 random integers;
data5: 105 random integers;
data 6: 105 sequential integers;
Data 7: 105 integers in reverse order;
Data 8: 105 basically ordered integers;
Data 9: 105 random positive integers, no more than 1000 each.
Input format:
The first line of input gives a positive integer N (≤105 ), and the next line gives N integers (in the range of long integers), separated by spaces.

Output format:
Output the results sorted from small to large in one line. The numbers are separated by 1 space, and there must be no extra space at the end of the line.

Idea: just to summarize the sorting method

1. Directly use the library function quicksort

Lazy dog ​​method qsort()

#include<stdio.h>
#include<stdlib.h>

int cmp(const void *a,const void *b)
{
    return *(int*)a-*(int*)b;
}

int main()
{
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    qsort(a,n,sizeof(a[0]),cmp);
    printf("%d",a[0]);
    for(int i=1;i<n;i++)
    {
        printf(" %d",a[i]);
    }
}

2. Bubble sort

(But in this question, when the amount of data is large, it will time out) Here is just a summary of the sorting method

#include<stdio.h>
#include<stdlib.h>

void BubbleSort(int a[],int n)
{
    int i,j;
    int flag=1;
    int temp;
    for(i=0;i<n&&flag;i++)
    {
        flag=0;
        for(j=n-1;j>=i;j--)
        {
            if(a[j]>a[j+1])
            {
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
                flag=1;
            }
        }
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    BubbleSort(a,n);
    printf("%d",a[0]);
    for(int i=1;i<n;i++)
    {
        printf(" %d",a[i]);
    }
}

3. Selection sort

(will time out)

#include<stdio.h>
#include<stdlib.h>

void swap(int a[],int i,int j)
{
    int temp=a[i];
    a[i]=a[j];
    a[j]=temp;
}

void SelectSort(int a[],int n)
{
    int i,j,min;
    for(i=0;i<n;i++)
    {
        min=i;
        for(j=i+1;j<n;j++)
        {
            if(a[min]>a[j])
                min=j;
        }
        if(i!=min)
        {
        swap(a,i,min);
        }
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    SelectSort(a,n);
    printf("%d",a[0]);
    for(int i=1;i<n;i++)
    {
        printf(" %d",a[i]);
    }
}

4. Insertion sort

The idea is to insert a record into an already sorted ordered table, so as to get a new ordered table with the number of records added by 1

#include<stdio.h>
#include<stdlib.h>


void InsertSort(int r[],int n)
{
    int i,j,temp;
    for(i=1;i<n;i++)
    {
        temp=r[i];//draw the next card
        for(j=i;temp<r[j-1]&&j>0;j--)//Comparing from the back to the front, if the drawn card is smaller than the previous card, the previous card will move backward
        {                            //Compare until j=0
            r[j]=r[j-1];
        }
        r[j]=temp;//new card placement
    }
}



int main()
{
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    InsertSort(a,n);
    printf("%d",a[0]);
    for(int i=1;i<n;i++)
    {
        printf(" %d",a[i]);
    }
}

5. Hill sort

#include<stdio.h>
#include<stdlib.h>


void ShellSort(int r[],int n)
{
    int i,j,temp;
    int increment;
    for(increment=n/2;increment>0;increment/=2)//Incremental sequence
    {
        for(i=increment;i<n;i++)
        {
            temp=r[i];//draw the next card
            for(j=i;j>=increment&&temp<r[j-increment];j-=increment)
            {
                r[j]=r[j-increment];
            }
            r[j]=temp;//new card placement
        }
    }
}



int main()
{
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    ShellSort(a,n);
    printf("%d",a[0]);
    for(int i=1;i<n;i++)
    {
        printf(" %d",a[i]);
    }
}

6. Heap Sort

The basic idea is to construct the sequence to be sorted into a large top heap. At this time, the maximum value of the entire sequence is the root node of the top of the heap, and it is removed (in fact, it is exchanged with the end element of the heap array. At this time The last element is the maximum value), and then the remaining n-1 sequences are reconstructed into a heap, so that the next largest value of the n elements is obtained. Repeatedly execute in this way, you can get an ordered sequence

#include<stdio.h>
#include<stdlib.h>

typedef int ElementType;

void Swap( ElementType *a, ElementType *b )
{
     ElementType t = *a; *a = *b; *b = t;
}
  
void PercDown( ElementType A[], int p, int N )
{  /* Resize the sub-heap rooted at A[p] in an array of N elements to a max-heap */
    int Parent, Child;
    ElementType X;
 
    X = A[p]; /* Get the value stored in the root node */
    for( Parent=p; (Parent*2+1)<N; Parent=Child ) {
        Child = Parent * 2 + 1;//Sequence number starts from 0 Left child 2parent+1
        if( (Child!=N-1) && (A[Child]<A[Child+1]) )
            Child++;  /* Child points to the greater of the left and right child nodes */
        if( X >= A[Child] ) break; /* found the right place */
        else  /* Filter X */
            A[Parent] = A[Child];
    }
    A[Parent] = X;
}
 
void HeapSort( ElementType A[], int N ) 
{ /* heap sort */
     int i;
       
     for ( i=N/2-1; i>=0; i-- )/* build max heap */
         PercDown( A, i, N );//Build a max heap with A[i] as the root
      
     for ( i=N-1; i>0; i-- ) {
         /* remove max heap */
         Swap( &A[0], &A[i] ); //Swap the root node and the last element
         PercDown( A, 0, i );
     }
}



int main()
{
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    HeapSort(a,n);
    printf("%d",a[0]);
    for(int i=1;i<n;i++)
    {
        printf(" %d",a[i]);
    }
}

7. Merge Sort

It is a sorting method implemented by the idea of ​​​​merging. Assuming that the initial sequence contains n records, it can be regarded as n ordered subsequences, and the length of each subsequence is 1, and then merged in pairs to obtain ⌈n/2⌉ (⌈x⌉ represents the smallest integer not less than x) ordered subsequences of length 2 or 1, and then merged in pairs... Repeat this until an ordered subsequence of length n is obtained, which is a 2-way merge sort

#include<stdio.h>
#include<stdlib.h>

typedef int ElementType;

/* Merge Sort - Recursive Implementation */
 
/* L = Left start position, R = right start position, RightEnd = right end position*/
void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
{ /* Merge ordered A[L]~A[R-1] and A[R]~A[RightEnd] into an ordered sequence */
     int LeftEnd, NumElements, Tmp;
     int i;
      
     LeftEnd = R - 1; /* left end position */
     Tmp = L;         /* the starting position of the ordered sequence */
     NumElements = RightEnd - L + 1;
      
     while( L <= LeftEnd && R <= RightEnd ) {
         if ( A[L] <= A[R] )
             TmpA[Tmp++] = A[L++]; /* Copy the left element to TmpA */
         else
             TmpA[Tmp++] = A[R++]; /* Copy the right element to TmpA */
     }
 
     while( L <= LeftEnd )
         TmpA[Tmp++] = A[L++]; /* Copy the rest of the left */
     while( R <= RightEnd )
         TmpA[Tmp++] = A[R++]; /* Copy the rest of the right */
          
     for( i = 0; i < NumElements; i++, RightEnd -- )
         A[RightEnd] = TmpA[RightEnd]; /* Copy the ordered TmpA[] back to A[] */
}
 
void Msort( ElementType A[], ElementType TmpA[], int L, int RightEnd )
{ /* Core recursive sorting function */ 
     int Center;
      
     if ( L < RightEnd ) {
          Center = (L+RightEnd) / 2;
          Msort( A, TmpA, L, Center );              /* Solve the left side recursively */ 
          Msort( A, TmpA, Center+1, RightEnd );     /* Solve the right side recursively */  
          Merge( A, TmpA, L, Center+1, RightEnd );  /* Merge two ordered sequences */ 
     }
}
 
void MergeSort( ElementType A[], int N )
{ /* merge sort */
     ElementType *TmpA;
     TmpA = (ElementType *)malloc(N*sizeof(ElementType));
      
     if ( TmpA != NULL ) {
          Msort( A, TmpA, 0, N-1 );
          free( TmpA );
     }
     else printf( "not enough space" );
}



int main()
{
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    MergeSort(a,n);
    printf("%d",a[0]);
    for(int i=1;i<n;i++)
    {
        printf(" %d",a[i]);
    }
}

Tags: Algorithm data structure

Posted by AndyMoore on Mon, 30 May 2022 12:19:16 +0530