Сортировка методом выбора C++
Есть два массива одинакового размера, один заполнен числами, второй пустой. Нужно методом выбора отсортировать первый массив во второй, не изменяя первый. При этом, не копировать первый массив во второй.
Ответы (1 шт):
Автор решения: Zhihar
→ Ссылка
Вот есть же википедия, есть ссылка
Раз требуется не менять первый массив, то почему бы не хранить во втором индексы по первому массиву и переставлять не элементы первого массива, а индексы второго массива?
void studip_sort(int* src, int* dst, const int size) {
// поставить каждому элементу dst его индекс
for (int i = 0; i < size; i++) {
dst[i] = i;
}
// отсортировать массив
for (int i = 0; i < size - 1; i++)
{
int min_index = i;
for (int j = i + 1; j < size; j++)
{
if (src[dst[j]] < src[dst[min_index]])
{
min_index = j;
}
}
if (min_index != i)
{
const int tmp = dst[min_index];
dst[min_index] = dst[i];
dst[i] = tmp;
}
}
// поставить каждому элементу dst значение из src
for (int i = 0; i < size; i++) {
dst[i] = src[dst[i]];
}
}
int main() {
int src[20] = { 1, 6, 9, 11, 0, -3, 4, 5, 11, 6, 7, 7, -8, 11, 20, -11, 0, -3, 1, 5 };
int dst[20];
studip_sort(src, dst, 20);
for (int i = 0; i < 20; i++) {
std::cout << dst[i] << " ";
}
_getch();
return 0;
}