Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Реализация простейшего алгоритма сортировкиПостроим внешний цикл программы сортировки. На каждом шагу цикла мы будет находить один наименьший элемент и располагать его на нужной позиции. Обозначим t номер шага. После каждого шага мы будем иметь t отсортированных (расположенных на своих местах) элементов. Это можно обозначить так: { a 0 > a 1 > … > at – 1, at … an – 1}. В этой записи используются фигурные скобки. Такими скобками обычно отмечают условия выполнения (инвариант, предусловие, постусловие) в тексте программы. Предусловие этого цикла: t = 0. При этом нет ни одного отсортированного элемента. Если отсортированы все элементы кроме одного, то последний элемент автоматически располагается на последней позиции. Тогда условие окончания этого цикла таково: t = n – 1, при этом все элементы будут отсортированы, иначе цикл будет продолжаться, пока не будет достигнуто, что t < n – 1. В теле цикла необходимо увеличить t на единицу, при этом должен сохраниться инвариант – элементы от 0 до t’ – 1 должны находиться на нужных местах. Поскольку до этого на нужных местах были расположены элементы от 0 до t – 1 = t’ – 2, то достаточно найти наименьший элемент среди элементов от t’ – 1 до n – 1 и поменять его местами с элементом t’ – 1 или найти наименьший элемент от t до n – 1 и поменять его с элементом t. Использование старого значения t удобнее, поскольку не требует дополнительных вычитаний 1 и позволяет вычислить новое значение t в конце тела (записать вычисление t в шаг цикла оператора for). Построим цикл, который находит наименьший среди элементов от t до n – 1. На каждом шаге этого цикла будет добавляться по одному элементу к множеству элементов, для которых известен минимальный из них. Другими словами, инвариантом системы будет условие о том, что известен наименьший элемент среди элементов от t до j – 1, где j – переменная цикла. Обозначим mi индекс этого наименьшего элемента, а m – его значение. На первом этапе работы цикла множество будет состоять из одного элемента, который, поскольку он один, будет наименьшим элементом этого множества, т. е. j = t + 1, mi = t, m = at. Это предусловие цикла, его выполнения необходимо достичь при инициализации. Очевидно, что условием выполнения внутреннего цикла будет j < n. В теле цикла j должно увеличиться на единицу. Для того чтобы сохранился инвариант, достаточно проверить, меньше ли элемент переменной m, и если меньше, то изменить m и m – i. Осталось уточнить, как поменять элементы в конце внешнего цикла. С этим предлагается разобраться самостоятельно по приведенному ниже коду.
void print_mas(int* m, int n) { int i; for(i=0;i<n;i++) printf("%i ", m[i]); printf("\n"); }
int main() { int a[8]={1,2,4,3,8,7,5,6}; int j, t, m, mi, n=8;
print_mas(a, n); for(t=0; t<n-1; t++) { // Найти наименьший элемент m=a[t]; mi=t; for(j=t; j<n; j++) if(a[j]<m) { m=a[j]; mi=j; }; // Поместить наименьший элемент на первую позицию a[mi]=a[t]; a[t]=m; } print_mas(a, 8); }
|