Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Ижевский государственный технический университет
имени М.Т. Калашникова»
Факультет «Математика и естественные науки»
Кафедра «Прикладная математика и информатика»
Лабораторная работа № 1 по курсу «Программирование для ЭВМ 3»
Тема: «Алгоритмы поиска»
Выполнил
студент гр. Б03-183-1 Загребин И.В.
Принял
ст. преподаватель Степанова Т.М.
Ижевск 2013
Постановка задачи.
1.Реализовать метод сортировки с помощью прямого обмена («пузырьковая» сортировка)
2.Реализовать метод сортировки с помощью включений с уменьшающимися расстояниями (сортировка Шелла)
Теоретическая часть.
Задача 1.
Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает – массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).
Задача 2.
При использовании сортировки Шелла массив делится на n частей. Первая часть массива содержит элементы 0,n,2n,3n и т.д., вторая часть 1,n+1,2n+1,3n+1 и т.д. Каждая часть последовательности сортируется независимо при помощи сортировки вставками с шагом n. Далее уменьшаем шаг в 2 раза (n=n/2) и повторим алгоритм. Повторяя итерационный процесс, пока шаг не станет равным 1. На выходе мы получим отсортированный массив.
Результаты работы программы и выводы.
Задача 1.
Задача 2.
Приложение А.
Задача 1.
#include <iostream>
#include <iostream>
#include <stdio.h>
using namespace std;
const int N = 5;
int k=0;
void bubble(int*a, int n)
{
int i;
for (i=N-1;i>0;i--)
{
for (int j=0;j<i;j++)
{
if(a[j]>a[j+1])
{
int tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
k++;
}
}
}
}
int main ()
{
int i;
int *a = new int[N];
cout«"Enter elements of massive: "«endl;
for (i=0;i<N;i++){
cin»a[i];
}
cout«"Your massive is:";
for (i=0;i<N;i++){
cout«a[i]«" ";}
cout«endl;
bubble(a, N);
cout«"Massive after sort:";
for (i=0;i<N;i++){
cout«a[i]«" ";}
cout«"\nSteps:"«k«endl;
system("pause");
return 0;
}
Задача 2.
#include <iostream>
using namespace std;
int main()
{
int k=0;
int p=0;
int size=0;
cout«"Enter size of massive:";
cin » size;
int *a = new int[size];
cout«"\nEnter elements of massive:"«endl;
for (int i = 0; i < size; i++)
{
cin » a[i];
}
cout«"Your massive :"«endl;
for (int i = 0; i < size; i++)
{
cout « a[i]«' ';
}
int step = size / 2;
while (step > 0)
{
for (int i = 0; i < (size - step); i++)
{
int j = i;
while (j >= 0 && a[j] > a[j + step])
{
int temp = a[j];
a[j] = a[j + step];
a[j + step] = temp;
j--;
cout«"\nSorting:"«endl;
k++;
for (int u=0;u<size;u++){
cout«a[u]«' ';
}
}
}
step = step / 2;
p++;
}
cout«"\nSorted massive:"«endl;
for (int i = 0; i < size; i++)
{
cout « a[i] « ' ';
}
cout«"\nNumber of steps:"«p;
cout«"\nNumber of permutations:"«k«endl;
system("pause");
return 0;
}
Список литературы.
1.Сортировка пузырьком: http://ru.wikipedia.org/wiki/Сортировка_пузырьком
2. Сортировка Шелла: http://algorithmlib.org/sort_shella
3. Никлаус Вирт. Алгоритмы и структуры данных: Мир,1989. 360с.