Лабораторная работа № 7 Сортировка и списки
Цель – познакомиться с простейшими видами сортировки и кониейнеров, типами перечисления и объединения.
Перечисления
Иноrда появляется необходимость описать в проrрамме собственный тип, содержащий оrраниченное количество значений. Сделать это можно, используя ключевое слово еnum, например:
еnum days {su, то, tu, we, th, fr, sa};
Так как для внутреннего представления элементов перечисления используются целые значения, то можно определить тип
еnum modes {LASTMODE =1, BW40O, С40, BW80, С80, MONO= 7};
В котором значение LASTMODE равно 1, значения С40, BW80 и С80 соответственно будут равны 3, 4 и 5, а MONO равно 7. Использование этих типов настолько же легко, как и целочисленных..
Задание 1. Получить результат программы и проанализировать его.
#include <iostream.h>
#include <vcl.h>
#include <conio.h>
int main(int argc, char* argv[])
{
enum modes {LASTMODE=1, BW40O, C40, BW80, C80, MONO=7};
std::cout << "LASTMODE " << LASTMODE << endl;
std::cout << " BW40O " << BW40O << endl;
std::cout << " C80 " << C80 << endl;
std::cout << " MONO " << MONO << endl;
getch();
return 0;
}
Задание 2. Получить результат программы и проанализировать его
#include <iostream.h>
#include <vcl.h>
#include <conio.h>
int main(int argc, char* argv[])
{ enum Color {Red,Green,Yellow }rr;
struct ccc
{ char Color[6];
};
ccc mc[3];
strcpy(mc[0].Color,"Red");
strcpy(mc[1].Color,"Green");
strcpy(mc[2].Color,"Yellow");
for ( rr=Red; rr<= Yellow; rr=rr+1)
std::cout << "Color " << mc[rr].Color << endl;
getch();
return 0;
}
//---------------------------------------------------------------------------
Тип объединение union – определяет единственный адрес, по которому размещаются все его элементы.
Задание 3. Получить результат программы и проанализировать его
#include <iostream.h>
#include <vcl.h>
#include <conio.h>
int main(int argc, char* argv[])
{union ddd
{
char x[9];
char y[9];
} rr;
strcpy(rr.x ,"My string") ;
cout << "rr.x=" << rr.x << endl;
cout << "rr.y=" << rr.y << endl;
getch();
return 0;
}
Пузырьковая сортировка
Если представить массив, например, из пяти элементов (4 3 5 2 1), «поставленный» вертикально, с нулевым элементом наверху и четвертым — внизу, то пузырьковая сортировка проходит по массиву снизу вверх. Каждый элемент массива сравнивается с тем, что находится непосредственно над ним, и если последний больше, производится перестановка двух этих элементов. Например, нижний элемент (с индексом 4 – это 1) оказывается наименьшим. Алгоритм сортировки сравнивает его со значением элемента с индексом 3 (который равен 2) и решает поменять их местами. Затем он сравнивает элемент с элементом с индексом 2 и также обменивает их. Процесс продолжается до тех пор, пока наименьший элемент не «всплывает», подобно пузырьку воздуха, на самый верх. В данный момент элемент с индексом 0 имеет правильное значение, и при последующих проходах алгоритма его можно игнорировать. Затем пузырьковая сортировка применяет ту же самую процедуру к подмассиву, состоящему из элементов с индексами от 1 до 4, в результате чего в позиции 1 также оказывается правильное значение (в данном случае 2). Сортировка продолжается в том же духе, сканируя все меньшие подмассивы, пока они не будут исчерпаны. К этому моменту весь массив будет правильно сортирован.
Задание 4. Выполнить пузырьковую сортировку
#include <iostream.h>
#include <conio.h>
#include <vcl.h>
inline void swap(int array[], int posl, int pos2)
{
int temp;
temp = array[posl];
array[posl] = array[pos2];
array[pos2] = temp;
}
inline void print(int array[], int size)
{
int i;
for (i=0; i < size; ++i) {
cout << array[i] << " ";
}
cout << endl;
}
inline void bubble_sort(int array[], int size)
{
int i, j;
for (i=0; i < size-1; ++i) {
for (j=size-1; j > i; --j )
{
if (array[j-1] > array[j]) swap(array, j-1, j);
}
}
}
int main( )
{
int array_1[] = {7, 3, 8, 2, 1, 5, 4};
print(array_1, 7);
bubble_sort(array_1, 7);
print (array_1, 7) ;
cout << endl;
int array_2[] = {7, 3, 8, 2, 1, 5, 4, 9, 75, -5};
print(array_2, 10);
bubble_sort(array_2, 10);
print(array_2, 10);
cout << endl;
int array_3[] = {1, 2, 3};
print(array_3, 3);
bubble_sort(array_3, 3);
print(array_3, 3) ;
cout << endl;
int array_4[] = {3, 2, 1};
print(array_4, 3);
bubble_sort(array_4, 3);
print(array_4, 3);
cout << endl;
int array_5[] = {5, 2, 1, 3};
print(array_5, 4);
bubble_sort(array_5, 4) ;
print(array_5, 4);
cout << endl;
int array_6[] = {3, 3, 3};
print(array_6, 3);
bubble_sort(array_6, 3);
print(array_6, 3);
cout << endl;
getch();
return 0;
}