6

私は C を学んでいて、ソートの話題に出くわしました。comp()関数を に書き、qsortの配列を並べ替えるために使用しましたint。次のタスクでは、配列から重複を削除する必要があります。
並べ替えと重複の削除を同時に行うことはできますか?

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>    
int indexes[10] = { 0, 98, 45, 65, 45, 98, 78, 56, 65, 45 };

int comp(const void * elem1, const void * elem2) {

    int f = *((int*) elem1);
    int s = *((int*) elem2);

    if (f > s) {    
        return 1;
    }    
    if (f < s) {    
        return -1;
    }    
    return 0;
}

void printIndexArray() {    
    int i = 0;    
    for (i = 0; i < 10; i++) {    
        printf("i is %d\n", indexes[i]);    
    }
}

int main() {    
    qsort(indexes, sizeof(indexes) / sizeof(int), sizeof(int), comp);    
    printIndexArray();    
    return 0;
}
4

5 に答える 5

1

これは、マージソートを使用して重複を削除するコードです。このコード スニペットは削除作業を行います。

else if(a[p1] == a[p2])
{
    merged[p] = a[p1];
    p1++;
    p2++;
}

これは反復マージソートですが、再帰バージョンの方が簡単です。

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

#define min(a,b) (((a) < (b)) ? (a) : (b))

int indexes[10] = { 0, 98, 45, 65, 45, 98, 78, 56, 65, 45 };

void merge(int *a, int s, int m, int e)
{
    int p1 = s;
    int p2 = m + 1;
    int * merged = (int*)malloc(sizeof(int) * (e - s + 1));
    int p = 0;
    while(p1 < m + 1 && p2 < e + 1)
    {
        if(a[p1] > a[p2])
        {
            merged[p] = a[p2];
            p2++;
        }
        else if(a[p1] == a[p2])
        {
            merged[p] = a[p1];
            p1++;
            p2++;
        }
        else
        {
            merged[p] = a[p1];
            p1++;
        }
        p++;
    }

    while(p1 < m + 1)
    {
        merged[p++] = a[p1++];
    }

    while(p2 < e + 1)
        merged[p++] = a[p2++];

    int i;
    for(i = 0;i < (e -s+1); i++)
    {
        a[s + i] = merged[i];
    }

    free(merged);
}

void merge_sort(int *a, int n)
{
    int width;
    for(width = 1; width < n; width = 2 * width)
    {
        int i;
        for(i = 0; i < n; i = i + 2 * width)
        {
            merge(a, i, min(i + width - 1, n - 1), min(i + 2 * width - 1, n - 1) );
        }
    }
}

void printIndexArray()
{    
    int i = 0;    
    for(i = 0; i < 10; i++)
    {    
        printf("i is %d\n", indexes[i]);    
    }
}

int main()
{
    merge_sort(indexes, sizeof(indexes) / sizeof(int) );
    printIndexArray();
    return 0;
}
于 2013-09-21T00:06:23.700 に答える
0

簡単に言えば、はい。

長い答えは、いつでも可能ですが、それを行うための複雑さは、使用するアルゴリズムに大きく依存します。

クイック ソート、スロー ソート、バケット ソート、ストレート基数ソートなどのより複雑なアルゴリズムは、暗黙的に分割できる連続した配列にあるデータに依存しているため、このような拡張には適していません。サブアレイ。そのため、重複を検出すると、簡単には取り出せません。繰り返しますが、可能ですが、初心者にとっては問題ありません。

バブル ソート、挿入ソート、シェル ソートなどのそれほど複雑でないインプレース アルゴリズムを使用すると、比較的簡単に実行できます。上に上がる。その後、センチネル値のクリームをすくい取るだけで完了です。

重複の削除に実際に役立つアルゴリズムは、プロセスで拡大/縮小する中間配列を使用するアルゴリズムです。このような場合、重複を検出したときに、これらの中間配列の 1 つを縮小またはスキップすることができます。候補はマージソートとヒープソートです。

ただし、配列を並べ替えて、2 番目の別の手順で重複を排除する方が賢明であることに注意してください。なんで？重複を排除すると、ほとんどの場合 O(n*log(n)) であるソート アルゴリズムの内側のループが複雑になるためです。ただし、ソートされた配列から重複を排除するのは O(n) 操作であるため、分割操作は融合操作よりも高速になります。

于 2013-09-20T23:39:32.530 に答える