Сортировка массивов
Цель работы: изучение приёмов сортировки одномерных массивов данных, выработка умений алгоритмизации и программирования задач сортировки массивов, отладки и тестирования программ с массивами.
/* Программа 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.