11. Сортировка массивов

Цель работы: изучение приёмов сортировки одномерных массивов данных, выработка умений алгоритмизации и программирования задач сортировки массивов, отладки и тестирования программ с массивами.

/* Программа 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.