Insertion Sort - Part 1

Sorting
One common task for computers is to sort data. For example, people might want to see all their files on a computer sorted by size. Since sorting is a simple problem with many different possible solutions, it is often used to introduce the study of algorithms.

Insertion Sort
These challenges will cover Insertion Sort, a simple and intuitive sorting algorithm. We will first start with a nearly sorted list.

Example:

Input:  n=5, arr[]={2,4,6,8,3}

Output:

2 4 6 8 8 
2 4 6 6 8 
2 4 4 6 8 
2 3 4 6 8 

Approach:

Java

public class InsertionSortPart1 {
    public static void main(String[] args) {
        int n = 5;
        int[] arr = { 2, 4, 6, 8, 3 };

        insertionSort1(n, arr);
    }

    private static void insertionSort1(int n, int[] arr) {
        int temp = arr[n - 1];
        int i = n - 2;
        while (i >= 0) {
            if (temp < arr[i]) {
                arr[i + 1] = arr[i];
                for (int j = 0; j < n; j++)
                    System.out.print(arr[j] + " ");
                System.out.println();
                i = i - 1;
            } else {
                arr[i + 1] = temp;
                break;
            }
        }
        if (i < 0)
            arr[i + 1] = temp;
        for (int j = 0; j < n; j++)
            System.out.print(arr[j] + " ");

    }
}

C++

#include <bits/stdc++.h>
using namespace std;

void insertionSort1(int n, vector<int> arr)
{
    int temp = arr[n - 1];
    int i = n - 2;
    while (i >= 0)
    {
        if (temp < arr[i])
        {
            arr[i + 1] = arr[i];
            for (int j = 0; j < n; j++)
                cout << arr[j] << " ";
            cout << "\n";
            i = i - 1;
        }
        else
        {
            arr[i + 1] = temp;
            break;
        }
    }
    if (i < 0)
        arr[i + 1] = temp;
    for (int j = 0; j < n; j++)
        cout << arr[j] << " ";
}
int main()
{
    int n = 5;
    vector<int> arr = {2, 4, 6, 8, 3};

    insertionSort1(n, arr);
    return 0;
}