Insert elements into an array in sorted order

Question

What I would like to do is as I take input from user, insert that input into the array in a sorted order, eg. user inputs 22,3,9,10,33
output would be: 3,9,10,22,33.

The code I have below is working except for the fact that for the last element being added is at the wrong index. This was a test for school(which is why the array is 50 elements big and theres a whole class with getters and setters & lack of error checking) and I'm trying to see where I'm going wrong, I've tried both insertion and selection sort which both produce this result. From my understanding, it should be forty five consecutive zeros and then my elements in ascending order.

eg) This is the output I get(wether i use selection or insertion sort after calling my print method

Sorted Array: 0 0 0 0 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 9 10 22

 public class test
{
    private int [] arr;
    private int maxSize;
    private int numItems;
    public test(int maxSize)
    {
        this.maxSize = maxSize;
        numItems = 0;
        arr = new int[maxSize];
    }

    public bool addItem(int key)
    {
        if (numItems < maxSize)
        {
            selectionSort(key);
            arr[numItems] = key;
            numItems++;
            return true;
        }
        return false;
    }

    public bool insertionSort(int key)
    {
        int n = arr.Length - 1;
        for (int i = 1; i < n; i++)
        {
            key = arr[i];
            int j = i - 1;
            while(j>=0 && arr[j] > key)
            {
                arr[j+1] = arr[j];
                j --;
            }
            arr[j + 1] = key;
        }
        return true;
    }

    public bool selectionSort(int key)
    {
        int  n = arr.Length - 1;
        for (int i = 0; i < n; i++)
        {
            key = i;
            for(int j = i + 1; j < n; j++)
            {
                if (arr[j] < arr[key])
                {
                    key = j;
                }
            }
            int temp = arr[key];
            arr[key] = arr[i];
            arr[i] = temp;

        }
        return true;
    }    

         static void Main(string[] args)
    {

        test x = new test(50);

        int count = 0;
        int element;
        while (count < 5)
        {
            Console.WriteLine("Enter an element to add into the array");
            element = Convert.ToInt32(Console.ReadLine());
            x.addItem(element);
            count++;
        }}

possible duplicate: https://stackoverflow.com/questions/1344500/efficient-way-to-insert-a-number-into-a-sorted-array-of-numbers — Rahul R., Jan 28 '20 at 06:14

score 0 · Answer 1 · answered Jan 28 '20 at 06:24

i think you are looking for insertion sort here is an example.

   static void Main(string[] args)
    {
        int[] numbers = new int[10] {22,1,34,20,12,10,5,33,11,5};
        Console.WriteLine("\nOriginal Array Elements :");
        Show(numbers);
        Console.WriteLine("\nSorted Array Elements :");
        Show(InsertionSort(numbers));
        Console.ReadKey();
        }

    static int[] InsertionSort(int[] inputArray)
    {
        for (int i = 0; i < inputArray.Length - 1; i++)
        {
            for (int j = i + 1; j > 0; j--)
            {
                if (inputArray[j - 1] > inputArray[j])
                {
                    int temp = inputArray[j - 1];
                    inputArray[j - 1] = inputArray[j];
                    inputArray[j] = temp;
                }
              }
        }
        return inputArray;         
    }
    public static void Show(int[] array)
    {
        foreach (int i in array)
        {
            Console.Write(i.ToString() + "  ");
        }
     }

score 0 · Accepted Answer · answered Jan 28 '20 at 06:29

I found two issues with your code and these were minor.

Update addItem function to move selectionSort below the assignment operation.

    public bool addItem(int key)
    {
        if (numItems < maxSize)
        {
            arr[numItems] = key;
            selectionSort(key);  // below the arr[numItems] assignment.
            numItems++;
            return true;
        }
        return false;
    }

and in the selectionSort method, change two things.

a. for loop for j should go all the way to n and

b. break when k=j;

        public bool selectionSort(int key)
    {
        int n = arr.Length - 1;
        for (int i = 0; i < n; i++)
        {
            key = i;
            for (int j = i + 1; j <= n; j++) // <= n instead of < n
            {
                if (arr[j] < arr[key])
                {
                    key = j;
                    break;             // break here once you have k = j.
                }
            }
            int temp = arr[key];
            arr[key] = arr[i];
            arr[i] = temp;

        }
        return true;
    }

This should take care of your issues.

This was the solution! Thank you, I had a feeling it had something to do with the assignment operation in the addItem method, but I had no idea about breaking out of the loop and going all the way to the end of the array. Thank you for pointing that out — hazey, Jan 28 '20 at 19:38

Insert elements into an array in sorted order

2 Answers2