Is it possible to insert elements in an array sortedly (in ascendent order)? Or is it better to sort after all the elements are already in the array?

DumbProgrammer 0
Viewed 50

For example, being the input:

4 2 120 -2 3

Is it better (complexity time) to insert every element sortedly?

int array[n];
int val;
int pl = 0;

pl++;
int aux = 0;
for (int i = 0; i < pl; i++)
{
    if (array[i] > val)
    {
        aux++;
        for (int j = pl; j >= i; j--)
        {
            array[j] = array[j - 1];
            array[i] = val;
            break;
        }
    }
    if (aux == 0)
        array[pl - 1] = val;
}

print_array();

Output: -2 2 3 4 120

Or is it better to just fill the array in the given input order and then just sort the array?

int array[n];
int val;

for (int i = 0; i < n and cin >> val; ++i)
   array[i] = val;
 
print_array();

quicksort(array);

print_array();

Output:

4 2 120 -2 3 //array before quicksort
-2 2 3 4 120 //array after quicksort
insert buffer sorting arrays c++
1 Answers

Generally better to insert as received, then sort.

If you insert each item in order, each insertion is O(N), and you do it N times, so you end up with O(N2) overall complexity.

If you insert them in the order received, then use a QuickSort (or similar, such as IntroSort, which is how std::sort is often implemented) you end up with O(N log N) instead.

Jerry Coffin0
Related