мусор при

После сортировки в массиве NxN появляется мусор, с каждым разом мусор в разных местах

Ваши условия не покрывают случай, когда i или j равно n, а стало быть в ячейках с этими индексами остаются неинициализированные данныеПросто добавьте предварительно обнуление в цикл установки значений: