Отсортировать случайным образом cгенерированный массив используя следу

1
2
3
4
5
6
7
Отсортировать случайным образом cгенерированный массив, используя следующие ал-горитмы.
1. Усовершенствованная пузырьковая сортировка. Используется принцип пузырьковой сортировки, но массив просматривается не от начала до конца, а от начала до последнего перемещенного элемента (после которого все элементы уже упорядочены). Вначале этим «последним» элементом выбирается последний элемент массива.
2. Простой выбор. Выбрать наибольший элемент массива и поменять его места-ми с последним (n–ным) элементом массива. Затем из n–1 первых элементов опять выбрать наибольший и опять поменять его местами с (n–1)–м. И так далее, пока весь массив не будет упорядочен.
3. Простые вставки. Так обычно сортируют карты: из веера карт берут одну, стоящую не по старшинству и помещают между двумя уже упорядоченными картами. Мас-сив просматривают с начала до конца. Рассматривается i–тый элемент массива и вставляется на нужную позицию в ряду первых (i–1) уже упорядоченных элементов. (Первоначально “упорядочен” только первый элемент массива). Если i–тый элемент перемещается в j–тую позицию, то все элементы с j–того по (i–1)–ый элемент должны быть сдвинуты на одну по-зицию вправо.
4. Метод подсчета. Если для какого–то элемента массива известно, что если он больше, чем i других элементов этого массива, то он должен стоять на (i+1)–ом месте после упорядочивания. Для каждого i–го элемента массива считают, сколько чисел меньше его, и результат заносят в массив индексов с[i]. Это делается следующим образом. Сравнивают по-парно все элементы массива: i–тый и j–тый. (Одна пара чисел может сравниваться только один раз.) Если i–тый больше, то с[i] увеличивают на единицу, иначе c[j] увеличивают на единицу. После формирования массива индексов с, формируют результирующий массив.
5. Метод распределяющего подсчета. Используется, если в массиве много оди-наковых элементов. Создается массив индексов d[i]. Размерность массива – число различных между собой элементов исходного массива. Затем в элемент массива d[i] заносят количество элементов массива, равных i, и в результирующий массив записывают по d[i] элементов i–того типа. Например, исходный массив 0010101031; d[0]=5, d[1]=4, d[2]=0, d[3]=1. Результи-рующий массив 0000011113.