Is what I'm doing an Insertion sort, I think the logic is correct but unconventional?-CodePudding

This code is supposed to be an Insertion sort but is it implemented as such? I'm lost. The first loop goes through the array and checks if the next element is smaller than the current element. The nested loop inserts the next element(j) correctly in its place in the sorted portion of the array.

#include <iostream>

using namespace std;

// Print array
void printArray(int array[], int arraySize)
{
    for (int i = 0; i < arraySize; i  )
    {
        cout << array[i] << " ";
    }
    cout << endl;
}

int main()
{
    int array1[] ={5, 3, 1, 9, 8, 2, 4, 7};
    int array1Size = sizeof(array1)/sizeof(int);

    printArray(array1, array1Size);

    for (int i = 0; i < array1Size - 1; i  )
    {
        int oldNum = array1[i];
        if (array1[i] > array1[i   1])
        {
            array1[i] = array1[i   1];
            array1[i   1] = oldNum;
        }

        int newI = array1[i];
        // Check if arranged correctly
        if ( i > 0)
        {
            // Swap bigger number and newI
            for (int j = i - 1; newI < array1[j]; j--)
            {
                if (j < 0)
                {
                    break;
                }
            
                array1[j   1] = array1[j];
                array1[j] = newI;
            }
        }
        printArray(array1, array1Size);

    }

    return 0;
}

CodePudding user response：

The key to insertion sort is to maintain a "sorted zone" and expand it in loop. In the beginning the zone is only one element, and finally it's all the list. We take an element outside the sorted zone and decide which position in sorted zone that it should be placed in.

BTW, loop invariant is easy to understand but powerful and awesome. Recommended.

int main() {
  int array1[] ={5, 3, 1, 9, 8, 2, 4, 7};
  int array1Size = sizeof(array1)/sizeof(int);
  
  // loop invariant: array1[0..i-1] is sorted
  // array1[i] is the element to be inserted
  for (size_t i = 1; i < array1Size; i  ) {
    int temp = array1[i];
    // find the right place to insert array1[i]. Can be replaced by binary search(but moving elements is more expensive than comparing)
    size_t j = i; // j is used to save the right place
    for (; j > 0 && array1[j-1] > temp; j--) {
      array1[j] = array1[j-1];
    }
    array1[j] = temp;
  }
  return 0;
}

CodePudding user response：

This for loop

    for (int j = i - 1; newI < array1[j]; j--)
    {
        if (j < 0)
        {
            break;
        }
    
        array1[j   1] = array1[j];
        array1[j] = newI;
    }

can invoke undefined behavior when j is equal to -1 due to this expression in the condition of the for loop

newI < array1[j]

And the code is too complicated. For example this code snippet

    if (array1[i] > array1[i   1])
    {
        array1[i] = array1[i   1];
        array1[i   1] = oldNum;
    }

where two elements are swapped is redundant. And this if statement

    if ( i > 0)
    {

also is redundant. It is enough to start the outer loop from 1 instead of from 0.

It is better to define a separate function. It can look for example the following way

void InsertionSort( int a[], size_t n )
{
    for (size_t i = 1; i < n; i  )
    {
        if (a[i] < a[i - 1])
        {
            int tmp = a[i];

            size_t j = i;
            for ( ; j != 0 && tmp < a[j - 1]; --j )
            {
                a[j] = a[j - 1];
            }

            a[j] = tmp;
        }
    }
}

Pay attention to that the operator sizeof yields a value of the type size_t. You should use this type size_t for the variable that will be store the number of elements in the array. In general the type int is not large enough to store sizes of arrays.

If your compiler supports C 17 then instead of using the expression with the sizeof operator

int array1Size = sizeof(array1)/sizeof(int);

you could write at least

#include <iterator>

//...

int array1Size = std::size( array1 );

Also as the function printArray does not change the passed array then it first parameter should be declared with the qualifier const.

void printArray(const int array[], int arraySize);

Here is a demonstration program that shows usage of a separate function that sorts arrays using the insertion sort method..

#include <iostream>
#include <iterator>

void InsertionSort( int a[], size_t n )
{
    for (size_t i = 1; i < n; i  )
    {
        if (a[i] < a[i - 1])
        {
            int tmp = a[i];

            size_t j = i;
            for ( ; j != 0 && tmp < a[j - 1]; --j )
            {
                a[j] = a[j - 1];
            }

            a[j] = tmp;
        }
    }
}

int main() 
{

    int array1[] ={5, 3, 1, 9, 8, 2, 4, 7};

    for ( const auto &item : array1 )
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';

    InsertionSort( array1, std::size( array1 ) ); 

    for ( const auto &item : array1 )
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';
}

The program output is

5 3 1 9 8 2 4 7 
1 2 3 4 5 7 8 9