Вставить элементы в массив в отсортированном порядке

Question

Что я хотел бы сделать, так это когда я беру ввод от пользователя, вставляю этот ввод в массив в отсортированном порядке, например. пользовательские вводы 22,3,9,10,33
вывод будет: 3,9,10,22,33.

Работающий ниже код работает, за исключением того факта, что последний добавленный элемент имеет неправильный индекс. Это был тест для школы (именно поэтому массив состоит из 50 элементов большого размера и существует целый класс с геттерами и сеттерами и отсутствием проверки ошибок), и я пытаюсь понять, в чем проблема, я попробовал оба вставка и выборка, которые оба дают этот результат. Насколько я понимаю, это должно быть сорок пять последовательных нулей, а затем мои элементы в порядке возрастания.

например) Это вывод, который я получаю (если я использую выбор или вставку сортировки после вызова моего метода печати

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 * ​​1008 *

 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++;
        }}

Answer 1

Я обнаружил две проблемы с вашим кодом, и они были незначительными.

1. Обновление addItem функции для перемещения selectionSort ниже операции назначения.

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

и в методе selectionSort измените две вещи.

а. для l oop для j должно go вплоть до n и

b. перерыв, когда 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;
    }

Это должно решить ваши проблемы.

Answer 2

Я думаю, что вы ищете сортировку вставки, вот пример.

   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() + "  ");
        }
     }