Цель работы: изучение приёмов сортировки одномерных массивов данных, выработка умений алгоритмизации и программирования задач сортировки массивов, отладки и тестирования программ с массивами.
/* Программа 11. Программа демонстрирует типовые процедуры сортировки массивов по заданным условиям: удаление элементов, сортировка по возрастанию значений чисел, перемещение элементов. Задачи решаются без использования дополнительных массивов. */
// Прототипы функций программы:
void in_arr(int *arr, int n); // Ввод n чисел массива arr
void out_arr(int *arr, int n); // Вывод n элементов массива arr
int array_del_0(int *arr, int &n); // Удаление из массива нулевых элементов
// Сортировка массива по возрастанию чисел методом пузырька
void sort_bubble(int *x, int n);
// перемещение "-"-ых элементов в массиве после первого "-"-го элемента
void move_negative_numbers(int *x, int n);
#include <stdio.h>
#include <conio.h>
main()
{ int i, j, k, n;
int x[50];
printf("\n Введите размер массива n: \n");
scanf("%d", &n);
in_arr(x, n);
printf(" \n Исходный массив размером %d: \n", n);
out_arr(x, n);
// Удаление из массива нулевых элементов
k = array_del_0(x, n);
printf("\n\n Массив после удаления k = %d нулевых элементов: \n", k);
out_arr(x, n);
// Сортировка массива по возрастанию чисел методом пузырька
n = 10;
randomize();
for(i = 0; i < n; i++)
x[i] = random(20);
printf("\n\n Исходный массив: \n");
out_arr(x, n);
printf("\n Массив после сортировки методом пузырька: \n");
sort_bubble(x, n);
out_arr(x, n);
// Перемещение элементов x[i] < 0 в массиве после первого элемента x[k] < 0
n = 10;
for(i = 0; i < n; i++)
x[i] = random(20) - 10;
printf("\n\n Исходный массив: \n");
out_arr(x, n);
printf("\n В массиве x[i] < 0 перемещены после 1-го элемента x[k] < 0: \n");
move_negative_numbers(x, n);
out_arr(x, n);
getch();
return 0;
}
// Ввод n чисел массива arr[ ]
void in_arr(int *arr, int n)
{ printf("\n Введите %d чисел массива: ", n);
for (int i = 0; i < n; i++)
scanf("%d", arr++); // ввод по указателю
}
// Вывод n элементов массива arr[ ]
void out_arr(int *arr, int n)
{ for (int i = 0; i < n; i++)
{ printf(" %d ", *arr++); // вывод по указателю и переход
// на следующий элемент массива
if ((i+1) % 10 == 0) // вывод по 10 чисел в строке:
printf("\n");
}
}
// Удаление из массива нулевых элементов
// ТЕСТ: n = 5, x = 1, 0, 3, 0, 4 ==> n = 3, x = 1, 3, 4
int array_del_0(int *arr, int &n)
{ int i, j, k;
for (i = 0, k = 0; i < n; i++)
if (arr[i] == 0) k++;
else { j = i - k;
arr[j] = arr[i];
}
n = n - k; // размер массива после удаления нулевых элементов
return k; // количество удалённых нулевых элементов
}
// Сортировка массива по возрастанию чисел методом пузырька
// ТЕСТ: n = 5, x = 6, 2, 1, 4, 3 ==> x = 1, 2, 3, 4, 6
void sort_bubble(int *x, int n)
{ int i, k, w;
for(k = 1; k < n; k++) // перебор всех неупорядоченных частей
// массива размером n-k+1
for(i = 0; i < n-k; i++) // перестановка максимального числа из
// неупорядоченной части массива размером n-k+1 в конец этой части
if(x[i] > x[i+1]) // перестановка большего числа вправо
{ w = x[i];
x[i] = x[i+1];
x[i+1] = w;
}
}
// перемещение "-"-ых элементов в массиве после первого "-"-го элемента
// ТЕСТ: n = 6, x = 1, -2, 3, -4, -5, 6 ==> x = 1, -2, -4, -5, 3, 6
void move_negative_numbers(int *x, int n)
{ int i, k = n, w;
for(i = 0; i < n - 2; i++) // поиск 1-го "-"го элемента
if(x[i] < 0) { k = i + 1; break; }
if(k == n) return; // "-"х чисел в массиве нет или перестановка
// не требуется
for(i = k; i < n; i++) // перемещение "-"-х элементов после 1-го
// "-"-го элемента
if(x[i] < 0)
{ w = x[i];
x[i] = x[k];
x[k] = w;
k++;
};
}
Вопросы и упражнения
1. На какой элемент массива указывает индекс k в функции move_negative_numbers()?
2. Составьте алгоритм удаления из массива элемента хi, заданного
индексом i.
3. Составьте алгоритм удаления из массива элемента, заданного значением этого элемента.
4. Составьте алгоритм, по которому можно поменять местами первый и последний положительные элементы в массиве.
5. Составьте алгоритм сортировки массива методом выбора: находится минимальный элемент массива и меняется местами с первым элементом, далее процедура повторяется для неупорядоченной части массива.
6. Напишите функции для алгоритмов упражнений 2-5.
