数组桶排序用C [英] array bucket sort in C

问题描述

我想读txt文件号码列表，然后将它们与桶排序排序。
所以这里是我的code：

I am trying to read list of numbers from txt file and then sort them with Bucket sort. so here is my code:

void bucketSort(int array[],int *n)
{
    int i, j;  
    int count[*n]; 
    for (i = 0; i < *n; i++)
        count[i] = 0;

    for (i = 0; i < *n; i++)
        (count[array[i]])++;

    for (i = 0, j = 0; i < *n; i++)  
        for(; count[i] > 0; (count[i])--)
            array[j++] = i; 
}   

int main(int brArg,char *arg[])
{

    FILE *ulaz;
    ulaz = fopen(arg[1], "r");

    int array[100];
    int i=0,j,k,n;


      while(fscanf(ulaz, "%d", &array[i])!=EOF)i++;

    fclose(ulaz);    
    n=i;
    for (j = 0; j<i; j++)
    {
        printf("Broj: %d\n", array[j]);
    }

    BucketSort(array,&n); 
    for (k = 0; k<i; k++)
        printf("%d \n", array[i]);   


    return 0;
}

有在code没有错误，但是当我把我的函数，而不是排序后的数组，我得到数组长度的随机数字（例如：2 3 5 4，排序后我得到124520 124520 124520 124520或其他一些随机数），因为我是一个初学者，可能有人帮助我与我的code和我做错了什么？ （抱歉坏英文）

There are no errors in code,but when i call my function instead of sorted array i get array length random numbers(example: 2 3 5 4,after sorting i get 124520 124520 124520 124520 or some other random number) since i am a beginner,could someone help me with my code and what i did wrong? (sorry for bad english)

推荐答案

由于很酷的家伙正确地指出，你有问题的内存访问，但在它上面的code不排序任何东西。首先，你应该怎样读桶排序的实际工作。

As Cool Guy correctly pointed out you have issues with memory access but on top of it the code does not sort anything. First you should read how Bucket Sort actually works.

在一般：

• 您一些，保证标准划分桶中输入数据桶不会弄乱的输入顺序


• 使用排序斗其它分类方法或递归排序或者每个桶


• 并置排列的数据（这就是为什么第一点还没有搞乱了输入顺序的限制）

下面是你原来的code的例子，我试图调整尽可能少你很容易让你明白。这code。通过一系列分3桶之间predefined输入数组：

Here is an example of your original code, I tried to adjust it as little as possible you it is easier for you to understand. This code divides a predefined input array among 3 buckets by range:

• [ - 无限远] [ - 1] - >第一桶


• [0; 10 - >二斗


• [11;无限] - >第三桶

然后在每个桶进行快速排序和并置的结果。我希望这有助于理解这个算法如何工作的。

then performs Quicksort on each bucket and concatenates the result. I hope this helps to understand how this algorithm works.

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

struct bucket 
{
    int count;
    int* values;
};

int compareIntegers(const void* first, const void* second)
{
    int a = *((int*)first), b =  *((int*)second);
    if (a == b)
    {
        return 0;
    }
    else if (a < b)
    {
        return -1;
    }
    else
    {
        return 1;
    }
}

void bucketSort(int array[],int n)
{
    struct bucket buckets[3];
    int i, j, k;
    for (i = 0; i < 3; i++)
    {
        buckets[i].count = 0;
        buckets[i].values = (int*)malloc(sizeof(int) * n);
    }
    // Divide the unsorted elements among 3 buckets
    // < 0    : first
    // 0 - 10 : second
    // > 10   : third
    for (i = 0; i < n; i++)
    {
        if (array[i] < 0)
        {
            buckets[0].values[buckets[0].count++] = array[i];
        }
        else if (array[i] > 10)
        {
            buckets[2].values[buckets[2].count++] = array[i];
        }
        else
        {
            buckets[1].values[buckets[1].count++] = array[i];
        }
    }
    for (k = 0, i = 0; i < 3; i++)
    {
        // Use Quicksort to sort each bucket individually
        qsort(buckets[i].values, buckets[i].count, sizeof(int), &compareIntegers);
        for (j = 0; j < buckets[i].count; j++)
        {
            array[k + j] = buckets[i].values[j];
        }
        k += buckets[i].count;
        free(buckets[i].values);
    }
}

int main(int brArg,char *arg[]) {

    int array[100] = { -5, -9, 1000, 1, -10, 0, 2, 3, 5, 4, 1234, 7 };
    int i = 12,j,k,n;

    n=i;
    for (j = 0; j<i; j++)
    {
        printf("Broj: %d\n", array[j]);
    }

    bucketSort(array, n); 
    for (k = 0; k<i; k++)
        printf("%d \n", array[k]);   


    return 0;
}

这篇关于数组桶排序用C的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！