組み込みアルゴリズムソートアルゴリズム

[[433624]]

1. バブルソート

バブルソートは、C 言語のシンプルな初級レベルのソートアルゴリズムです。ソートする要素の列を繰り返し訪問し、隣接する 2 つの要素を順番に比較し、順序が間違っている場合はそれらを交換します。交換する必要がある隣接する要素がなくなるまで、つまり要素列がソートされるまで、チェックと比較を繰り返します。このアルゴリズムの名前の由来は、水の泡が最終的に上に浮かぶように、小さい (大きい) 要素が交換を通じてゆっくりとシーケンスの上部 (昇順または降順) に「浮かぶ」ため、「バブルソート」という名前が付けられています。

アルゴリズムの説明

1. 隣接する要素を比較します。最初の値が2番目の値より大きい場合は、それらを交換します

2. 隣接する要素の各ペアに対して、最初のペアから最後のペアまで同じ操作を実行し、最後の要素が最大の数になるようにします。

3. 最後の要素を除くすべての要素に対して上記の手順を繰り返します。

4. ソートが完了するまで手順1～3を繰り返します。

ソースコード

#include <stdio.h> 
 
 #ARRAY_SIZE 15 を定義します
 
 void log( char *head, int *data, int len)
 {
    符号なしchar i; 
 
    printf( "%s:" , ヘッド); 
 
 (i = 0; i < len; i++)の場合
    {
        printf( "%02d " , データ[i]);
    }
    printf( "\r\n" );
 } 
 
 // 小さい順から大きい順に並べ替える
void bubble_sort( int *データ, int  サイズ）
 {
整数i、j、 temp ; 
 
 (i = 0; i <サイズ; i++)の場合
    {
 (j = 0; j <サイズ-i-1; j++)の場合
        {
            if(data[j] > data[j + 1]) // 隣接する要素をペアで比較する
            {
 temp = data[j + 1]; // 要素の交換
                データ[j + 1] = データ[j];
                データ[j] = temp ;
            }
        }
    }
 } 
 
 intメイン(void)
 {
 intデータ[ARRAY_SIZE] = {3、44、38、5、47、15、36、26、27、2、46、4、19、50、48}; 
 
    log( "ソース" 、データ、 ARRAY_SIZE);
    bubble_sort(データ、ARRAY_SIZE);
    log( "ソート" , データ, ARRAY_SIZE); 
 
 0を返します。
 }

運用結果

出典:03 44 38 05 47 15 36 26 27 02 46 04 19 50 48
並べ替え:02 03 04 05 15 19 26 27 36 38 44 46 47 48 50

2. 選択ソート

選択ソートは、シンプルで直感的なソートアルゴリズムです。まず、ソートされていないシーケンス内で最小 (最大) の要素を検索し、ソートされたシーケンスの先頭に格納します。次に、残りのソートされていない要素から最小 (最大) の要素を検索し続け、ソートされたシーケンスの末尾に配置します。すべての要素がソートされるまでこれを繰り返します。

アルゴリズムの説明

1. 初期状態では、すべてのデータは無秩序領域に属し、秩序領域は空である。

2. 順序付けされていない領域から最小の要素を選択し、順序付けされていない領域の最初の要素と交換します。

3. 順序なし領域が空になるまで、順序なし領域の次の要素から手順2を繰り返します。

ソースコード

void 選択ソート( int *データ, int  サイズ）
 {
整数i、j、 temp ;
整数 分; 
 
 (i = 0; i <サイズ- 1; i++)の場合
    {
最小値= i;
 (j = i + 1; j <サイズ; j++)の場合
        {
            if(data[j] < data[ min ]) // 最小の数値を見つける
            {
 min = j; // 最小値のインデックスを保存
            }
        } 
 
        if( min != i) // 対話が必要
        {
 temp = データ[i];
            データ[i] = データ[分];
            データ[分] =温度;
        }
    }
 }

前のアルゴリズムのbubble_sortの例はselection_sortに置き換えることができ、実行結果は同じです。

3. 挿入ソート

挿入ソートアルゴリズムは、順序付けられたシーケンスを構築することによって機能します。ソートされていないデータの場合、ソートされたシーケンス内で後ろから前へスキャンし、対応する位置を見つけて挿入します。

アルゴリズムの説明

1. 最初の要素から始めて、要素はソートされているとみなすことができます

2. 次の要素を取り出し、ソートされた要素の順序で後ろから前へスキャンします。

3. 要素（ソート済み）が新しい要素より大きい場合は、要素を次の位置に移動する

4. ソートされた要素が新しい要素以下になる位置が見つかるまで手順 3 を繰り返し、その位置に新しい要素を挿入します。

5. 手順2～4を繰り返します

ソースコード

void 挿入ソート( int *データ, int  サイズ）
 {
 int i、pre、 current ; 
 
 (i = 1; i <サイズ; i++)の場合
    {
        前 = i - 1;
現在のデータ[i]; 
 
        while(pre >= 0 && data[pre] > current ) //現在の要素を順序付けられた領域と1つずつ比較し、挿入します
        {
            データ[pre + 1] = データ[pre];
            前--;  
        }
        データ[pre + 1] =現在のデータ;
    }
 }

4. 標準ライブラリ関数 qsort

前の 3 つのソートアルゴリズムは、単一の要素のみをソートします。ただし、実際のアプリケーションでは、MAC、名前、暗号化情報、信号強度などの WiFi 情報構造の配列など、大きな構造が特定の値に基づいてソートされます。WiFi 情報は、情報強度に従ってソートされます。各データ交換は、2 つのメモリコピーを意味します。このシナリオでは、選択ソートの方がわずかに優れています。

車輪の再発明に比べると、C言語の標準ライブラリ関数の方が適切かもしれません。qsort関数はC言語に付属するソート関数で、真ん中。

関数プロトタイプ

void qsort(void *base, size_t nitems, size_t size , int (*compar)(const void *, const void*))

base - ソートする配列の最初の要素へのポインタ

nitems - 配列内の要素数

size - 配列内の各要素のサイズ（バイト単位）

compar - この関数に基づいて 2 つの要素を比較します

戻り値: 値値は返されません

デメリット: 複数の繰り返し値を持つ配列では効率が低く、不安定になる

例

//qsortはcompareと組み合わせて使用する必要があります
int比較(const void *値1、const void *値2)
 {
    //昇順または降順はここで調整されます
(*( int *)値1 - *( int *)値2を返します。)
 } 
 
 intメイン(void)
 {
 intデータ[ARRAY_SIZE] = {3、44、38、5、47、15、36、26、27、2、46、4、19、50、48}; 
 
    log( "ソース" 、データ、 ARRAY_SIZE);
    qsort(データ、ARRAY_SIZE、sizeof( int )、比較);
    log( "ソート" , データ, ARRAY_SIZE); 
 
 0を返します。
 }

その効果は前の 3 つのアルゴリズムと同じであり、特定の要素値に基づいて構造全体をソートするように拡張でき、信号強度によって Wi-Fi 情報をソートするという以前の要件を満たします。

 #include <stdio.h>
 #WIFI_AP_MAX 5 を定義します
 
 typedef unsigned char uint8_t;
 typedef 符号付きchar int8_t;
 typedef unsigned short uint16_t;
 typedef 符号付き short int16_t;
 typedef 符号なしint uint32_t; 
 
 typedef構造体
{
    uint32_t bssid_low; // MAC アドレスの下限
    uint16_t bssid_high; // MACアドレス高
    uint8_t チャネル; // チャネルID
    int8_t rssi; // 信号強度 <sort>
 }wifiApInfo_t; 
 
 //qsort は compare と組み合わせて使用し、信号強度 rssi の昇順で並べ替えます。
 int比較(const void *値1、const void *値2)
 {
    const wifiApInfo_t *ctx1 = (const wifiApInfo_t *)value1;
    const wifiApInfo_t *ctx2 = (const wifiApInfo_t *)value2;
戻り値(ctx1->rssi - ctx2->rssi);
 } 
 
静的wifiApInfo_t wifiApInfo[WIFI_AP_MAX] =
 {
    {0x5555, 0x55, 5, -55},
    {0x1111, 0x11, 1, -51},
    {0x3333, 0x33, 3, -53},
    {0x4444, 0x44, 4, -54},
    {0x2222, 0x22, 2, -52},
 }; 
 
 void wifi_log( char *head, void *data, int  サイズ）
 {
    符号なしchar i;
    const wifiApInfo_t *wifi = (wifiApInfo_t *)データ; 
 
    printf( "%s:\r\n" , ヘッド); 
 
 (i = 0; i <サイズ; i++)の場合
    {
        printf( "%X %X %d [%d] \r\n" 、wifi[i].bssid_low、wifi[i].bssid_high、wifi[i].channel、wifi[i].rssi);
    }
    printf( "\r\n\r\n" );
 } 
 
 intメイン(void)
 {
    wifi_log( "ソース" 、 wifiApInfo、 WIFI_AP_MAX);
    qsort(wifiApInfo、WIFI_AP_MAX、sizeof(wifiApInfo_t)、比較);
    wifi_log( "ソート" 、 wifiApInfo、 WIFI_AP_MAX); 
 
 0を返します。
 }

運用結果

ソース：
 5555 55 5 [-55]
 1111 11 1 [-51]
 3333 33 3 [-53]
 4444 44 4 [-54]
 2222 22 2 [-52] 
 
 //信号強度キーワードに基づいて、WiFi情報の全体的なデータ同期がソートされます
選別：
 5555 55 5 [-55]
 4444 44 4 [-54]
 3333 33 3 [-53]
 2222 22 2 [-52]
 1111 11 1 [-51]