Дан массив A размера N. Упорядочить его по возрастанию методом сортировки простыми вставками: сравнить элементы A1 и A2, при необходимости меняя их местами, добиться того, чтобы они оказались упорядоченными по возрастанию; затем обратиться к элементу A3 переместить его в левую (уже упорядоченную) часть массива, сохранив ее упорядоченность; повторить этот процесс для остальных элементов, выводя содержимое массива после обработки каждого элемента (от 2-го до N-го). При выполнении описанных действий удобно использовать прием «барьера», записывая очередной элемент перед его обработкой в дополнительный элемент массива A0.
У меня, кстати, очень и очень криво получилось написать код на С (но это прям фиаско):
CODE (htmlphp):
скопировать код в буфер обмена
скопировать код в буфер обмена
- #include <stdio.h>
- #include <iostream>
- #include <stdlib.h>
- #define board 20
- using namespace std;
- void Sort(int* arr,int n){ //ф-я сортировки, в нее передается указатель на массив(имя без квадратных скобок) и кол-во эл-в не совсем рационально, но зато наглядно
- int counter=0; //общее количество перестановок
- for(int i=1;i<n;i++){ //перебирается массив от начала до конца
- for(int j=i; j>0 && arr[j-1]>arr[j];j--){ //собственно, сама суть сортировки, начиная с текущей позиции (i), текущий эл-т (j-й) сравнивается с предыдущим (j-1)
- counter++; //если предыдущий больше текущего, наращивается счетчик перестановок (это не обязательная величина. да и сам шаг тоже не важен принципиально)
- int tmp=arr[j-1]; //типичный
- arr[j-1]=arr[j]; //обмен
- arr[j]=tmp; //двух величин
- cout<<arr[j]<<" ";
- }
- cout<<counter<<"-th iteration"<<endl; //выводится номер операции обмена. понятно, что, если на протяжении 2-х или 3-х шагов э-л ты стоят по-порядку, будет выводится одно и то же значение
- }
- cout<<counter<<"iterations total"<<endl; //сообщение об общем количестве обменов
- }
- int main()
- {
- int A[board]; //массив, размерность задана глобальной константой
- int i;
- for (i = 0; i < board; i++) {
- A[i] = rand()% 10;
- cout << A[i]<< " "; //выводится несортированный массив
- }
- cout<<endl;
- Sort (A, board); //вызов ф-ии сортировки
- for (i = 0; i < board; i++)
- cout << A[i]<< " "; //сортированный массив
- return 0;
- }
)
