Simple sorting

Take a[5] as an example

a[5] = {9,6,15,4,2};

1. Simple Selection Sorting

Traversing through the array finds the minimum (or maximum) value of the array and places it at position 0. Then scratch off position 0, traverse through the remaining numbers to find the best value, and put it on position 1 of the array, and so on

Selecting the smallest record from i records requires comparing i-1 times
I(i=0~n-2) Trip Selecting the smallest record from n-i records requires comparing n-i-1 times
Simple selection sort for n records, number of comparisons: n*(n-1)/2
Number of moves, positive order minimum 0, reverse order maximum 3(n-1)

Simple selection ranks best, with O(n^2) for worst and average time complexity
The time complexity of a simple selection sort is independent of the order of the initial sequence

The code snippet is as follows

for(i=0;i<5;i++){
	min = a[i];
	k_min = i;
	for(j=i+1;j<5;j++){
		if(min>a[j]){
			min = a[j];
			k_min = j;
		}
	}
	if(k_min != i){
		a[k_min] = a[i];
		a[i] = min;
	}
}

2. Sorting by bubble method

The name of this algorithm comes from the fact that the larger (or smallest) elements float slowly to the top of the series (ascending or descending) by exchange, just as the bubbles of carbon dioxide in carbonated drinks eventually float to the top, hence the name Bubble Sort.

Select a direction to scan, comparing the values of the two adjacent elements of the array one by one, placing smaller numbers (sorted from smallest to largest) before larger ones

The illustration is as follows

Best case - the keywords are ordered in the record sequence:
Only one bubble is needed
Number of comparisons = n-1
Number of moves = 0;
Worst case - keywords are in reverse order in the record sequence:
n-1 bubbles are required
Number of comparisons = n(n-1)/2
Move times = 3n*(n-1)/2

So the best time complexity for bubble sorting is O(n) and the worst time complexity is O(n^2);

The improved bubble sort code snippet is as follows

	for( int i = 1; i < size; i++ ){				//Outer loop 1~size-1
		bool exchange = false;
		for( int j = size - 1; j >= i; j-- ){	//Inner loop i~size-1
			if( a[j] < a[j-1] ){
				exchange = true;				//If no keywords are exchanged after a bubble, the sequence is arranged
				swaq( a[j], a[j-1] );			//Swap Two Numbers
			}
		}
		if( exchange == false ){
			break;
		}
	}

3. Exchange Sorting

The difference between bubble sort and bubble sort is that
Bubble sorting is a process of comparing edges and moving edges, comparing adjacent elements one by one. Exchange ordering is to select a location and compare relative sizes one by one and exchange with fixed locations
The illustration is as follows

The code snippet is as follows:

for(i=0;i<size;i++){
	for(j=i+1;j<size;j++){
		if(a[j]>a[j-1]){
			swap(a[j],a[j-1]);
		}
	}
}

4. Direct insert sorting

The basic idea is to divide the initial sequence into ordered and disordered regions, and insert the elements of the disordered regions into ordered regions one by one until the ordered regions contain all the data. Note that ordered areas are not necessarily ordered.
Initially, an ordered region has only one element (only one element can be considered ordered), and it contains an unordered region n-1 Elements are inserted into an ordered area.

for(i=1;i<size;i++){
		if(a[i]<a[i-1]){ //Enter the sorting process only if the order is reversed
			tmp = a[i];
			j = i-1;
			do{					//Find the insertion location of a[i]
				a[j+1] = a[j];	//Move records with keywords greater than a[i] backwards
				j--;
			}while((j>=0) && (a[j]>tmp));
			a[j+1] = tmp;		//Insert in j+1
		}
	}

In the best case - keywords are positively ordered in the record sequence

Number of comparisons = n-1; Number of element moves = 0;

In the best case, the time complexity is O(n)

Worst case - keywords are in reverse order in the record sequence

Number of comparisons = n(n-1)/2; Number of element moves = (n-1)(n+4)/2;

Worst case time complexity is O(n^2)

Average time complexity is O(n^2)

Sort and find <stdlib. H>

qsort

void
qsort( void *base, size_t n_elements, size_t el_size, int ( *compare )( void const *, void const * ) ) ;

The last parameter is a function pointer

bsearch

void
bsearch( void const *key, void const *base, size_t n_elements, size_t el_size, int ( *compare )( void const *, void const * ) );

bsearch works by dichotomizing and arrays need to be pre-sorted

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

int
compare( void const *a, void const *b )
{
	return ( *( int* )a ) > ( *( int* )b ) ? 1 : 0;
}
int
main( int argc, char *argv[] )
{
	int i;
	int key = 110;
	int *ans;
	int a[] = { 0, 110, 222, 55 };

	qsort( a, sizeof(a) / sizeof( int ), sizeof( int ), compare );
	for( i = 0; i < sizeof( a ) / sizeof( int ); i++ ){
		printf("%d ", a[i]);
	}

	ans = ( int* )bsearch( &key, a, sizeof( a ) / sizeof( int ), sizeof( int ), compare );

	if( ans != NULL ){
		printf("\n%d", *ans);
	}else{
		printf("\nNot Found");
	}

	return 0;
}

Keywords: data structure

Added by galafura on Tue, 28 Dec 2021 01:52:43 +0200