Is there any way to make this sorting algorithm have a linear time complexity?

Question

I am doing this homework assignment in my data structures & algorithms class that asks me to make an array of random numbers, an array of counters, and make our own sorting algorithm using both arrays in C++.

The array of counters would basically contain the index of where each element is supposed to go when the array of numbers is sorted, such that the value of counters[i] would be the index where array[i] would go after it's sorted. It uses this code, and it was given by our professor:

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

            else
                counters[i]++;
        }

I thought that using both of the arrays, we would be able to design a sorting algorithm that would have a O(n) time complexity, so I tried to think of a way to do this, and I came up with this:

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

For every iteration, I am swapping array[i] with array[counters[i]] because counters[i] determines the index for array[i], and then I am also swapping the values in the counters to make sure that the counters stay in the same index as their corresponding value.

For some reason, this is not achieving the sorting correctly, but I don't understand why.

I'm thinking to use another sorting algorithm, but I wanted to try this one first because it would be O(n).

Anyone could help?

Thanks.

You realize the loop computing these "counters" is O(N^2), right? — paddy
– paddy, Commented Mar 12, 2020 at 4:01
As @paddy notes, this is not anywhere close to O(n). Are you supposed to be implementing a counting sort? With a restricted range of inputs, that can get down to O(n + k) (on both time and space) where n is the input size, and k is the range of values, so a relatively restrictive range would be effectively O(n). — ShadowRanger
– ShadowRanger, Commented Mar 12, 2020 at 4:05
Yes, but I was focusing on the sorting algorithm itself because the other loop was given by our professor. @paddy — MoisesYacila
– MoisesYacila, Commented Mar 12, 2020 at 4:06
@ShadowRanger right, but I was talking about the sorting algorithm itself, the other loop was given by our professor — MoisesYacila
– MoisesYacila, Commented Mar 12, 2020 at 4:08
@JaMiT It would be {0, 1, 2, 3} right? If I'm not wrong, which is what it's supposed to do. — MoisesYacila
– MoisesYacila, Commented Mar 12, 2020 at 4:37

Kelly Bundy · Accepted Answer · 2020-03-12 16:24:53Z

Since the professor gave you the counting (which btw even handles duplicates correctly), I agree that you should use it to finish the sorting in additional O(n).

To do that, keep swapping what's at array[i] to where it belongs until array[i] contains what belongs there. Only then go to i+1. This way you know array[0..i] all contain what belongs there (and thus in the everything is where it belongs).

  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];
    }
  }

This is O(n), since every iteration of the inner loop puts one (or two) more value to where it belongs, and overall you can't put more than n values to where they belong, so overall you can't have more than n inner loop iterations.

Let's take {20, 50, 60, 70, 10, 40, 30} as an example and see what the array looks like at the end of each iteration of the for-loop:

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

Let's see an example where yours goes wrong: {1, 2, 3, 0}. You'll first swap the 1 to where it belongs: {2, 1, 3, 0}. This still leaves 2 not where it belongs! You rely on it hopefully getting fixed later on. But that never happens, as you then swap 1 with itself, then 3 with 0, and then 3 with itself. But if at i=0 you keep going until array[i] contains what belongs there, then you don't leave that 2 there dangerously out-of-place but fix it right away.

Full code, also at repl.it (this produced the above output):

#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;
  }
}

Austin Jiang · Accepted Answer · 2020-03-12 16:53:31Z

If you want to achieve linear time, the input array must be comes with some kind of the assumption, ie, input array is integer and within some kind of the range for counting sort and radix sort.

In the bottom solution, counterSort assume the input array is from 0-9, and insert the number to a pair,

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

the pair will keep tracking of the vector and its' counter.

#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;
}

Collectives™ on Stack Overflow

Is there any way to make this sorting algorithm have a linear time complexity?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related