How to make insertion sort print array at end of each iteration?

Question

My insertion sort code works properly and the user inputs array size then array elements then shows final sorted list, I want to make it show the sortd list at the end of each iteration.

My current code does this:

This is what I want my code to do:

Here's my code:

#include <iostream>
using namespace std;

void insertionsort(int A[], int n)
{
int value,hole,i;
 for(int i=1; i<n; i++)
 {
     value = A[i];
     hole = i;

     while(hole > 0 && A[hole-1] > value)
     {
         A[hole] = A[hole-1];
         hole = hole -1;
     }
     A[hole] = value;
 }
}

void displayarray(int A[], int n)
{
    for(int i=0; i<n; i++)
    cout << A[i] << ";";
}

int main()
{
    int n;
    cin >> n;
    int A[n];

    for(int i=0; i<n; i++)
    cin >> A[i];

    insertionsort(A,n);
    displayarray(A,n);

    return 0;
}

Just call `displayarray` at the end of the for loop inside `insertionsort`... — Aconcagua, Feb 05 '19 at 06:19
What @Aconcagua said, but don't forget to move the length you print. — user4581301, Feb 05 '19 at 06:20
About [using namespace std](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). — Aconcagua, Feb 05 '19 at 06:22
@91sixer: As you are a new contributor, just want to let you know that, it is necessary to mention what did you try to solve the question you are posting. Here, what did you try to print the intermediate output after each pass, should be mentioned. Some good links to go through are: https://stackoverflow.com/help/mcve and https://stackoverflow.com/help/someone-answers. — Shridhar R Kulkarni, Feb 05 '19 at 06:43

Shridhar R Kulkarni · Answer 1 · 2019-02-05T13:42:38.853

0

See the code added after A[hole] = value;

#include <iostream>
using namespace std;

void displayarray(int A[], int n)
{
    for(int i=0; i<n; i++)
    cout << A[i] << ";";
}

void insertionsort(int A[], int n)
{
int value,hole,i;
 for(int i=1; i<n; i++)
 {
     value = A[i];
     hole = i;

     while(hole > 0 && A[hole-1] > value)
     {
         A[hole] = A[hole-1];
         hole = hole -1;
     }
     A[hole] = value;


     // Call displayarray at end of each pass
     // Passing `i+1` as second parameter gives you desired result
     displayarray(A,i+1); 
     cout << endl;
 }
}

int main()
{
    int n;
    cin >> n;
    int A[n];

    for(int i=0; i<n; i++)
    cin >> A[i];

    insertionsort(A,n);
    //displayarray(A,n); //Commented this line

    return 0;
}

edited Feb 05 '19 at 13:42

answered Feb 05 '19 at 06:20

Shridhar R Kulkarni

6,653
3
37
57

Close. The final output will off by a bit. You fixed the other half of my comment. – user4581301 Feb 05 '19 at 06:22
Final output is a little bit off, not sure why but its done in a different order – Feb 05 '19 at 06:33
@91sixer On a humble note, Stack Overflow will help you with how to solve a problem. Please do not expect the community to solve the problem with every details. You will get answers with trivial things left for you as an exercise. This is how you learn. – Shridhar R Kulkarni Feb 05 '19 at 06:36
@ShridharRKulkarni Understood, May I please have a hint as to why the final output comes out differently? – Feb 05 '19 at 07:56
@91sixer: I had purposefully left the last piece of this puzzle for you. The only change needed was passing `i+1` instead of `i` to `displayarray` at the end of each iteration. Updated the code. This gives you the exact desired output. – Shridhar R Kulkarni Feb 05 '19 at 13:44

score 0 · Answer 2 · answered Feb 05 '19 at 08:39

0

If you add another simple for loop in your main() and add a single line of code in displayarray to add a new line, it should generate the Desired Result

#include <iostream>
using namespace std;

void insertionsort(int A[], int n)
{
    int value,hole  ;
    for(int i=1; i<n; i++)
    {
        value = A[i];
        hole = i;

        while(hole > 0 && A[hole-1] > value)
        {
            A[hole] = A[hole-1];
            hole = hole -1;
        }
        A[hole] = value;
    }
}

void displayarray(int A[], int n)
{
    for(int i=0; i<n; i++)
        cout << A[i] << ";";
    cout << "\n";
}

int main()
{
    int n;
    cin >> n;
    int A[n];

    for(int i=0; i<n; i++){
        cin >> A[i];
    }
    for(int i=0; i<n; i++){
        if(i > 0){
            insertionsort(A,i+1);
            displayarray(A, i+1);
        }
    }

    return 0;
}

answered Feb 05 '19 at 08:39

Ekin Karadağ

51
1
7

[Shridhar R Kulkarni](https://stackoverflow.com/users/5343790/shridhar-r-kulkarni)'s code will display after the whole array is provided. However, you should sort and display as the inputs arrive(before getting the whole array). – Ekin Karadağ Feb 05 '19 at 10:12
Ekin, I appreciate your try. What you tried is online style of insertion sort. But the worst case time complexity of insertion sort should remain O(n^2). Calling insertion sort on every input will make it O(n^3). For your learning, can you try modifying your above code to keep it O(n^2) while still calling insertion sort on every input? – Shridhar R Kulkarni Feb 05 '19 at 13:57
Thank you for your feedback. You are absolutely right but doesn’t Desired Result want insertion sort after every input? Though I’ll think harder for a better solution anyway. – Ekin Karadağ Feb 05 '19 at 14:09
You can see my updated answer for getting the desired result without calling insertion sort after every input. Even if OP has asked for offline insertion sort and you are trying for online insertion sort, via your method also it is possible to get the desired result with few more changes. Give it a try. – Shridhar R Kulkarni Feb 05 '19 at 14:15

score 0 · Answer 3 · answered Feb 05 '19 at 14:34

I have added code into allow it to display as it goes along. Trying to follow your desired output i have added a clear console function which clears the console before any text is written out to it. This allows for the effect of seeing the array being ordered as soon a new numbers entered.

I have also added a display function which calls the clearConsole(), displayArray() and another new function i've added called displaySize(). This function allows for easier readability stating the array size every time as any previous information would be deleted with the clearConsole().

#include <iostream>


void insertionsort(int A[], int n)
{
    int value, hole, i;
    for (int i = 1; i < n; i++)
    {
        value = A[i];
        hole = i;

        while (hole > 0 && A[hole - 1] > value)
        {
            A[hole] = A[hole - 1];
            hole = hole - 1;
        }
        A[hole] = value;
    }
}

void displayarray(int A[], int n)
{
    for (int i = 0; i < n; i++)
        std::cout << A[i] << ";";
}

void clearConsole()
{
    std::cout << std::flush;
    system("CLS");
}

void displaySize(int size)
{
    std::cout << "An array of size: " << size << "\n" << std::endl;
}

void display(int A[], int n, int size)
{
    clearConsole();
    displaySize(size);
    displayarray(A, n);
}

int main()
{
    int n;
    std::cin >> n;
    clearConsole();
    displaySize(n);

    int *A = new int[n];

    for (int i = 0; i < n; i++)
    {
        std::cin >> A[i];
        insertionsort(A, i+1);
        display(A, i+1, n);
    }


    insertionsort(A, n);
    displayarray(A, n);

    return 0;
}

Good efforts on improving the code ThomasBroughton. But there is another site https://codereview.stackexchange.com/ specifically intended to review and suggest improvement to the code. You can contribute there as well. I see you too have followed an approach similar to that followed by Ekin. Please read time complexity related discussion on Ekin's answer. — Shridhar R Kulkarni, Feb 05 '19 at 14:42

How to make insertion sort print array at end of each iteration?

3 Answers3