for i = 1 to n - 1
x = a(i)
k = i
for j = i + 1 to n
if a(j)<x then
k = j
x = a(k)
endif
next j
a(k) = a(i)
a(i) = x
next i
return
Эффективность алгоритма:
§ Количество сравнений
§ Количество перемещений, когда массив упорядочен
§ Количество перемещений когда массив обратно отсортирован
В худшем случае сортировка прямым выбором дает порядок n2, как и для числа сравнений, так и для числа перемещений.
Контрольные вопросы по теории
Сортировка методом включения
1. Даны три условия окончания просеивания при сортировке прямым включением. Найдите среди них лишнее.
- найден элемент a(i) с ключом, меньшим чем ключ у x;
- найден элемент a(i) с ключом, большим чем ключ у x;
- достигнут левый конец готовой последовательности.
2. Какой из критериев эффективности сортировки определяется формулой M = 0,01* n * n + 10* n?
- число сравнений;
- время, затраченное на написание программы;
- количество перемещений;
- время, затраченное на сортировку.
3. Как называется сортировка, происходящая в оперативной памяти?
- сортировка таблицы адресов;
- полная сортировка;
- сортировка прямым включением;
- внутренняя сортировка;
- внешняя сортировка.
4. Как можно сократить затраты машинного времени при сортировке большого объёма данных?
- производить сортировку в таблице адресов ключей;
- производить сортировку на более мощном компьютере;
- разбить данные на более мелкие порции и сортировать их.
5. Существуют следующие методы сортировки. Найдите ошибку.
- строгие;
- улучшенные;
- динамические.
Сортировка методом выбора.
1. Метод сортировки называется устойчивым, если в процессе сортировки…
- относительное расположение элементов безразлично;
- относительное расположение элементов с равными ключами не меняется;
- относительное расположение элементов с равными ключами изменяется;
- относительное расположение элементов не определено.
2. Улучшенные методы имеют значительное преимущество:
- при большом количестве сортируемых элементов;
- когда массив обратно упорядочен;
- при малых количествах сортируемых элементов;
- во всех случаях.
3. Что из перечисленных ниже понятий является одним из типов сортировки?
- внутренняя сортировка;
- сортировка по убыванию;
- сортировка данных;
- сортировка по возрастанию.
4. Сколько сравнений требует улучшенный алгоритм сортировки?
- n * log ( n );
- en ;
- n * n /4.
5. К какому методу относится сортировка, требующая n*n сравнений ключей?
- прямому;
- бинарному;
- простейшему;
- обратному.
Примеры алгоритмов и приложений
Рассмотрим теперь реализацию функций вышеописанных сортировок на С++ и примеры сортировки конкретных числовых массивов.
/* ************************************************ */
/* СОРТИРОВКА МЕТОДОМ ПРЯМОГО ВКЛЮЧЕНИЯ */
#include <stdio.h>
#include <conio.h>
#define n 8
int A[n]={27,412,71,81,59,14,273,87};
/* ========================================= */
main()
{ void Sis(int A[],int nn);
int j;
printf("\n Сортировка методом прямого включения");
printf("\n Исходный массив: \n\t");
for (j=0; j<n; j++)
printf("%d\t",A[j]);
printf("\n");
Sis(A,n);
printf("\n Отсортированный массив :\n\t");
for (j=0; j<n; j++)
printf("%d\t",A[j]);
printf("\n");
getch(); return 0;
}
/* ======================================== */
/* ФУНКЦИЯ СОРТИРОВКИ ПРЯМЫМ ВКЛЮЧЕНИЕМ */
void Sis(int A[],int nn)
{ int i,j,k;
printf("\n Отладочная печать по шагам сортировки");
for ( j=1; j<nn; j++ )
{ k = A[j];
i = j -1;
while ( k < A[i] && i >= 0)
{ A[i+1] = A[i];
i -= 1; }
A[i+1] = k;
/* Отладочная печать */
printf("\n j = %d",j);
for (i=0; i<nn; i++)
printf("\t%d",A[i]);
}
}
/* *********************************************** */
Алгоритм с прямыми включениями можно легко улучшить с учетом того, что готовая последовательность, куда надо вставить новый элемент, уже упорядочена. Тогда место включения ищется методом двоичного (бинарного) поиска. Такой улучшенный алгоритм сортировки называется методом с двоичным включением (методом прямого включения с делением пополам). Однако применение этого алгоритма оправдано только тогда, когда число сортируемых элементов достаточно велико.
/* *************************************************** */
/* СОРТИРОВКА МЕТОДОМ ПРЯМОГО ВКЛЮЧЕНИЯ
С ДЕЛЕНИЕМ ПОПОЛАМ */
#include <stdio.h>
#include <conio.h>
#define n 8
int A[n] = {27,412,71,81,59,14,273,87};
/* ========================================== */
main()
{ void BinIns(int A[],int nn);
int j;
printf("\n Сортировка методом прямого включения с делением пополам");
printf("\n Исходный массив \n");
for (j=0; j<n; j++)
printf("\t%d",A[j]);
printf("\n");
BinIns(A,n);
printf("\n Отсортированный массив \n");
for (j=0; j<n; j++)
printf("\t%d",A[j]);
printf("\n");
getch(); return 0;
}
/* ======================================== */
/* ФУНКЦИЯ СОРТИРОВКИ ПРЯМЫМ ВЫБОРОМ С ДЕЛЕНИЕМ ПОПОЛАМ */
void BinIns(int A[],int nn)
{ int i,j,x,m,L,R;
printf("\n Отладочная печать по шагам сортировки ");
for ( i=1; i<nn; i++ )
{ x = A[i]; L = 0; R = i;
while (L < R)
{ m = (L+R)/2;
if (A[m] <= x)
L = m+1;
else
R = m;
}
for (j=i; j>=R; j--)
A [ j ] = A [ j -1];
A [ R ] = x ;
/* отладочная печать */
printf("\ni=%d",i);
for (j=0; j<nn;j++)
printf ("\ t % d ", A [ j ]);
}
}
/* ******************************************** */
Последний рассматриваемый в данной работе алгоритм – сортировка методом прямого выбора.
/* ************************************************** */
/* СОРТИРОВКА ПОСРЕДСТВОМ ПРЯМОГО ВЫБОРА */
#include <stdio.h>
#include <conio.h>
#define n 8
int A[n] = {27,412,71,81,59,14,273,87};
/* ======================================== */
int main()
{ void StrSel(int A[],int nn);
int j;
printf("\n Сортировка методом прямого выбора");
printf("\n Исходный массив \n");
for (j=0; j<n; j++)
printf("\t%d",A[j]);
printf("\n");
StrSel(A,n);
printf("\n Отсортированный массив \n");
for (j=0; j<n; j++)
printf("\t%d",A[j]);
printf("\n"); getch();
}
/* =========================================== */
/* ФУНКЦИЯ СОРТИРОВКИ ПРЯМЫМ ВЫБОРОМ */
void StrSel(int A[],int nn)
{ int i,j,x,k;
printf("\n Отладочная печать по шагам сортировки");
for ( i=0; i<nn-1; i++ )
{ x = A[i]; k = i;
for (j=i+1; j<nn; j++)
if (A[j] < x)
{ k = j; x = A[k]; }
A[k] = A[i]; A[i] = x;
printf("\n i=%d",i);
for (j=0; j<nn;j++)
printf("\t %d",A[j]);
}
}
/* *********************************************** */
Задания
Сортировка методом включения
В ремонтной мастерской находятся несколько (N) машин. О них имеются следующие сведения:
- номер,
- марка,
- имя владельца,
- дата последнего ремонта (число, месяц, год),
- день, к которому машина должна быть отремонтирована (число, месяц, год).
Требуется (согласно варианту):
1. Расположить по алфавиту имена владельцев и, соответственно, вывести информацию об их машинах.
2. Исходя из того, что машина, дата окончания ремонта которой раньше, должна ремонтироваться в первую очередь, вывести порядок ремонта автомобилей.
3. Вывести по убыванию количество всех предыдущих ремонтов машин марки "Жигули".
4. Вывести по убыванию номера тех машин, количество предыдущих ремонтов которых равно 2.
5. Вывести по возрастанию даты конца ремонта всех машин, которые ранее не ремонтировались.
6. Вывести по алфавиту в обратном порядке владельцев автомобилей марки "Мерседес"
7. Вывести по алфавиту марки машин, которые должны быть отремонтированы раньше всех (дата конца ремонта меньше 01.08.96).
8. Вывести по возрастанию номера машин марки "Жигули".
9. Вывести по алфавиту имена владельцев, чьи машины не ремонтировались с прошлого года.
10. Вывести машины, которые надо отремонтировать к следующему месяцу по возрастанию даты их последнего ремонта.
11. Вывести по алфавиту в обратном порядке имена владельцев, количество предыдущих ремонтов машин которых больше трех.
12. Вывести по убыванию номера машин марки "Мерседес".
Сортировка методом выбора
Создать группу из N студентов.
Ввести их:
- фамилии, имена, годы рождения,
- оценки по предметам:
структуры и алгоритмы данных, высшая математика, физика, программирование,
- общий балл сдачи сессии.
Разработать программу, которая осуществляет сортировку (согласно варианту) :
1. Фамилий студентов по алфавиту.
2. Фамилий студентов по алфавиту в обратном порядке.
3. Студентов по старшинству (начиная со старшего).
4. Студентов по старшинству (начиная с младшего).
5. Студентов по общему баллу (по возрастанию).
6. Студентов по общему баллу (по убыванию).
7. Студентов по результатам 1-го экзамена (по возрастанию).
8. Студентов по результатам 2-го экзамена (по убыванию).
9. Студентов по результатам 3-го экзамена (по возрастанию).
10. Студентов по результатам 4-го экзамена (по убыванию).
11. Имен в алфавитном порядке.
12. Имен в обратном алфавитном порядке.
Дата: 2019-12-10, просмотров: 466.
