Calculation method for vector



  • I'm going to have to perform the counting method in the function of the vector. The concept of grading was understood, and implementation was not very good. I found the code online and redecorated the vector:

        void couting_max(vector<int>& array)
    {
        int max = INT_MIN, min = INT_MAX;
        for (int i = 0; i < array.size(); i++)
        {
            if (array[i] > max)
                max = array[i];
            if (array[i] < min)
                min = array[i];
        }
        vector<int>vec;
        int size_ = max + 1 - min;
        for (int i = 0; i < size_; i++)
        {
            vec.push_back(0);
        }
        for (int i = 0; i < array.size(); i++)
        {
            int size_ = array[i] - min;
            vec[size_] = vec[size_] + 1;
        }
        int i = 0;
        for (int j = min; j < max + 1; j++)
        {
            while (vec.at(j - min) != 0)
            {
                array.at(i) = j;
                vec.at(j - min)--;
                i++;
            }
        }
        system("cls");
        cout << "Сортировка выполнена успешно!" << endl;
        output(array);
        system("pause");
    }
    

    I think it's all right, it's coming down, it's all right, it's working, it's been traced through the palm, but it's not quite clear. It's a growing grade function, but I still need a depreciation function. It's kind of like doing the same thing, but it's still not working! I've tried a lot, I'm always out of the vector. I don't understand why such huge masses are created and how the maximum element becomes the size of the vector, how does it work? In brief, the task is to write the same function, but it's already sorted by decommissioning and a few explanations how it works. Thank you!



  • It's easy.

    void couting_sort(vector<int>& array)
    {
        if (array.size() == 0) return;
        auto p = minmax_element(array.begin(),array.end());
        int min = *p.first;
        int dist = *p.second - min + 1;
        vector<int> t(dist,0);
    
    for(auto i: array) t[i-min]++;
    
    for(int i = 0, idx = 0; i &lt; t.size(); ++i)
        for(int j = 0; j &lt; t[i]; ++j)
            array[idx++] = i+min;
    

    };

    We simply believe how many elements of each species are available, inscribed to the auxiliary mass their number, and then recorded in the adhesive mass the number of elements corresponding to the auxiliary index.

    To be sorted from a bigger to a smaller one, you just have to go backwards to the mass:

    for(int i = t.size()-1, idx = 0; i >= 0; --i)
    for(int j = 0; j < t[i]; ++j)
    array[idx++] = i+min;

    Create huge masses... this sorting is not appropriate for very dispersed elements. It is clear that in general, 16 memory gigabytes are required: this is good when the range is small. ♪

    Here. https://ideone.com/pxvnqR Full program.




Suggested Topics

  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2