Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Сортировки методом простого обмена.
Этот метод также называют методом пузырька. Его называют так потому, что в процессе выполнения сортировки более «лёгкие» элементы (элементы с заданным свойством, например максимальные) мало-помалу всплывают на «поверхность» (оказываются на своём месте). Суть метода: организация упорядоченного списка элементов, в который на соответствующие им места добавляются один за другим неотсортированные элементы. Для реализации этого метода элементы массива просматриваются в направлении от меньших значений индекса к большим, сравниваются очередные два элементы, индексы которых отличаются на 1. Если эти элементы между собой не упорядочены, то производится их взаимный обмен. На следующем шаге рассматривается меньшее количество элементов массива. И так до тех пор, пока не будут проанализированы все элементы массива.
Упорядочим массив {2, 4,10,11,0,9}. Первый просмотр: рассматривается весь массив. 2, 4, 10, 11, 0, 9 i=0 2<4 2, 4, 10, 11, 0, 9 i=1 4<10 2, 4, 10, 11, 0, 9 i=2 10<11 2, 4, 10, 11, 0, 9 i=3 11>0 2, 4, 10, 0, 11, 9 i=4 11>9 2, 4, 10, 0, 9, 11 результат просмотра – максимальный элемент на своём месте. Второй просмотр: рассматривается часть массива с нулевого до предпоследнего элемента. 2, 4, 10, 0, 9, 11 i=0 2<4 2, 4, 10, 0, 9, 11 i=1 4<10 2, 4, 10, 0, 9, 11 i=2 10>0 2, 4, 0, 10, 9, 11 i=3 10>9 2, 4, 0, 9, 10, 11 10- на своём месте.
Третий просмотр: рассматривается часть массива с нулевого до третьего элемента. 2, 4, 0, 9, 10, 11 i=0 2<4 2, 4, 0, 9, 10, 11 i=1 4>0 2, 0, 4, 9, 10, 11 i=2 4<9 2, 0, 4, 9, 10, 11 9- на своём месте. Четвёртый просмотр: рассматриваемая часть массива содержит три первых элемента. 2, 0, 4, 9, 10, 11 i=0 2>0 0, 2, 4, 9, 10, 11 i=1 2<4 0, 2, 4, 9, 10, 11 4- на своём месте. Пятый просмотр: рассматриваем последнюю пару элементов. 0, 2, 4, 9, 10, 11 i=0 0<2 0, 2, 4, 9, 10, 11 При сортировке методом пузырька выполняется N-1 просмотров, причём i –ом просмотре производится N – i сравнений. Общее количество сравнений: C= N*(N-1)/2. // переменные: a- исходный массив; // i,k- параметры циклов; // n- количество обрабатываемых элементов массива; // x-вспомогательная переменная; #include <stdio.h> #include <conio.h> void main() { int i,n,k; float x,a[100]; clrscr();
printf("введите количество элементов массива "); scanf("%d",&n); printf("введите %d чисел\n ",n);
for (i=0; i<n; i++) scanf("%f",&a[i]); printf(" исходный массив: "); for (i=0; i<n; i++) printf("%8.2f",a[i]); // сортировка массива for (i=0; i<n-1; i++) for (k=0; k<n-i; k++) if(a[k]>a[k+1]) { x=a[k]; a[k]=a[k+1]; a[k+1]=x; } // вывод результата for (i=0; i<n; i++) { if (i%5==0) printf("\n"); printf(" %8.2f",a[i]); } getch(); }
Сортировки методом простых вставок (метод прямого включения). Сортировка этим методом производится последовательно шаг за шагом. На i -ом шаге считается, что часть массива, содержащая первые i -1 элементов, уже упорядочена, то есть А[0]£ A[1]£... £A[i-1].Далее берётся i -й элемент, и для него подбирается место в отсортированной части массива, такое, что после вставки упорядоченность не нарушается, то есть требуется найти такое j (0£ j £ i-1), что А[j]£ A[i]<A[j+1] (при j=0 элемент ставится на первое место, а при j=i-1 он остаётся на своём месте). Затем выполняется вставка элемента A[i] на место j. На каждом шаге отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить N-1 шаг. Рассмотрим этот процесс на примере. Пусть требуется отсортировать по возрастанию массив, состоящий из 9 элементов. 6 8 13- рассматриваемая часть массива; 6 13 - место вставки; 8 - вставляемый элемент. 1-й шаг. 13 6 8 11 1 5 9 15 7 Рассматриваем часть массива из одного элемента 13. Вставляем 1-ый элемент массива 6так, чтобы упорядоченность сохранилась. Так как 6<13, записываем 6 на 0-е место. Отсортированная часть массива содержит два элемента (6,13). 2-й шаг. 6 13 8 11 1 5 9 15 7 Для второго элемента 8 подберём место в упорядоченном массиве. 8>6 и 8<13, следовательно его место 1-е. 3-й шаг. 6 8 13 11 1 5 9 15 7 11>8, 11<13, следовательно, его место 2-е. 4-й шаг. 6 8 11 13 1 5 9 15 7 1<6, следовательно, его место 0-е. 5-й шаг. 16 8 11 13 5 9 15 7 1<5, 5<6, следовательно, его место 1-е. 6-й шаг. 1 5 6 8 11 13 9 15 7 8<9, 9<11, следовательно, его место 4-е. 7-й шаг. 1 5 6 8 9 11 13 15 7 Этот элемент массива уже находится на своём месте. 8-й шаг. 1 5 6 8 9 11 13 15 7 6<7, 7<8, следовательно, его место 3-е.
|
|||||
Последнее изменение этой страницы: 2020-12-09; просмотров: 71; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.134.81.206 (0.007 с.) |