Есть ли способ заставить этот алгоритм сортировки иметь линейную сложность по времени?

Question

Я делаю это домашнее задание в своем классе структур данных и алгоритмов, который просит меня создать массив случайных чисел, массив счетчиков и создать наш собственный алгоритм сортировки, используя оба массива в C ++.

Массив счетчиков будет в основном содержать индекс, где каждый элемент должен go при сортировке массива чисел, так что значение counters [i] будет индексом, где массив [i] будет go после это отсортировано. Он использует этот код, и он был дан нашим профессором:

for (int i = 1; i < arraySize; i++)
        for (int j = 0; j < i; j++)
        {
            if (array[i] < array[j])
                counters[j]++;

            else
                counters[i]++;
        }

Я думал, что используя оба массива, мы сможем разработать алгоритм сортировки, который будет иметь O (n) сложность по времени , поэтому я попытался придумать способ сделать это, и я придумал следующее:

for (int i = 0; i < arraySize; i++)
    {
       int index = counters[i];
       swap(array[i], array[counters[i]]);
       swap(counters[i], counters[index]);
    }

Для каждой итерации я заменяю массив [i] массивом [counters [i]], потому что счетчики [i] определяет индекс для массива [i], а затем я также меняю значения в счетчиках, чтобы убедиться, что счетчики остаются в том же индексе, что и их соответствующее значение.

По какой-то причине это неправильно выполняет сортировку, но я не понимаю, почему.

Я думаю использовать другой алгоритм сортировки, но сначала я хотел попробовать его, потому что это будет O (n).

Кто-нибудь может помочь?

Спасибо.

Answer 1

Поскольку профессор дал вам счет (который, кстати, даже правильно обрабатывает дубликаты), я согласен, что вы должны использовать его, чтобы завершить sh сортировку в дополнительном O (n).

Чтобы сделать это, продолжайте обменивать то, что находится в array[i] туда, где оно принадлежит, пока array[i] не содержит то, что принадлежит там. Только , затем go до i+1. Таким образом, вы знаете, array[0..i] все содержат то, что принадлежит там (и, следовательно, в все находится там, где оно принадлежит).

  for (int i = 0; i < arraySize; i++) {
    int belongs_at = counters[i];
    while (belongs_at != i) {
      swap(array[i], array[belongs_at]);
      swap(counters[i], counters[belongs_at]);
      belongs_at = counters[i];
    }
  }

Это O (n), так как каждая итерация внутренний l oop помещает одно (или два) большее значение туда, где он принадлежит, и в целом вы не можете поместить больше n значений туда, где они принадлежат, поэтому в целом вы не можете иметь более n внутренних l oop итерации.

Давайте возьмем {20, 50, 60, 70, 10, 40, 30} в качестве примера и посмотрим, как выглядит массив в конце каждой итерации for -l oop:

10 20 60 70 50 40 30   # The while-loop fixed the cycle 20->50->10
10 20 60 70 50 40 30   # 20 was already where it belongs, so nothing happened
10 20 30 40 50 60 70   # The while-loop fixed the cycle 60->40->70->30
10 20 30 40 50 60 70   # 40 was already where it belongs, so nothing happened
10 20 30 40 50 60 70   # 50 was already where it belongs, so nothing happened
10 20 30 40 50 60 70   # 60 was already where it belongs, so nothing happened
10 20 30 40 50 60 70   # 70 was already where it belongs, so nothing happened

Давайте посмотрите пример, где у вас что-то не так: {1, 2, 3, 0}. Сначала вы поменяете 1 на то, к чему он относится: {2, 1, 3, 0}. Это по-прежнему оставляет 2 не , где он принадлежит! Вы надеетесь, что это будет исправлено позже. Но этого никогда не произойдет, так как вы потом поменяете 1 на себя, затем 3 на 0, а затем 3 на себя. Но если в i=0 вы продолжаете, пока array[i] не содержит того, что там находится, тогда вы не оставите это 2 там опасно неуместным, но исправите это сразу.

Полный код, также в repl.it (это привело к вышеприведенному выводу):

#include <iostream>
using namespace std;

int main() {

  // Sample array
  int arraySize = 7;
  int array[7] = {20, 50, 60, 70, 10, 40, 30};

  // Count
  int counters[7] = {};
  for (int i = 1; i < arraySize; i++)
    for (int j = 0; j < i; j++)
      if (array[i] < array[j])
        counters[j]++;
      else
        counters[i]++;

  // Sort
  for (int i = 0; i < arraySize; i++) {
    int belongs_at = counters[i];
    while (belongs_at != i) {
      swap(array[i], array[belongs_at]);
      swap(counters[i], counters[belongs_at]);
      belongs_at = counters[i];
    }

    // Show
    for (int i = 0; i < arraySize; i++)
      cout << array[i] << ' ';
    cout << endl;
  }
}

Answer 2

Если вы хотите достичь линейного времени, входной массив должен иметь какое-то предположение, ie, входной массив целочисленный и находится в некотором диапазоне диапазона для подсчета сортировки и сортировки по основанию.

В нижнем решении counterSort предполагает, что входной массив равен 0-9, и вставляет число в пару:

vector< pair<vector<int>,int> >

пара будет отслеживать вектор и его 'счетчик.

#include <stdlib.h>
#include <iostream>
#include <vector>

using namespace std;
// counterSort 
void counterSort(int sze, int* arrp, vector<pair< vector<int>,int> >& v)
{
    // pair will store a map between list and counter, 
    for(int i = 0; i < sze; i++)
    {
        int numb = arrp[i];
        v[numb].first.push_back(numb);
        v[numb].second++;
    }
}

// method for print out
void printOut(vector< pair<vector<int>,int> >& v)
{
    for(auto& item: v)
    {
        cout << "counter:" << item.second << "| ";
        for(auto& i:item.first)
        {
            cout << i << " ";
        }
        cout << endl;
    }
}
int main()
{
    int* arrp = new int[50];
    for(int i = 0; i < 50; i++)
    {
        int r = rand() % 10;
        arrp[i] = r;
        cout << arrp[i] << " ";
    }
    cout << endl;
    int sze = 50;
    vector<pair<vector<int>,int> > v( sze,make_pair(vector<int>(0),0) );
    counterSort(sze,arrp, v);
    printOut(v);
    delete [] arrp; 
    return 0;
}