Выборочная сортировка
Хотя пузырьковая сортировка вполне работоспособна, она производит гораздо больше действий, чем это необходимо — даже для простого метода. Слабым местом ее, очевидно, является количество выполняемых перестановок, — вместо того, чтобы ставить каждый элемент сразу на его конечное место, она перемещает элементы каждый раз всего на одну позицию. Выборочная сортировка основана на том же основном принципе, что и пузырьковая, но решает эту ключевую проблему.
Если подвергнуть выборочной сортировке массив из предыдущего пункта, то алгоритм
сортировки также будет просматривать подмассивы, отыскивая каждый раз минимальное значение. Однако вместо обмена пар соседних значений, стоящих не в том порядке, алгоритм просто записывает индекс минимального значения и затем производит единственный обмен его со значением, которое занимает в данный момент верхнюю позицию в подмассиве. Первый проход по массиву находит, что минимальное значение, равное 1, занимает 4-й элемент. Как только это определено, элементы нулевой и четвертый обмениваются значениями. Затем выборочная сортировка сканирует все меньшие и меньшие подмассивы, аналогично пузырьковой сортировке.
Задание 5. Выполнить выборочную сортировку
#include <iostream.h>
#include <conio.h>
#include <vcl.h>
inline void swap(int array[], int pos1, int pos2)
{
int temp;
temp = array[pos1];
array[pos1] = 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;
}
// Get_min_index( ) возвращает индекс массива, соответствующий
// минимальному значению подмассива, определяемому
// left и right.
inline int get_min_index(int array[], int left, int right)
{
int min_index = left;
int i;
for (i = left; i <= right; ++i) {
if (array[i] < array[min_index]) min_index = i;
}
return min_index;
}
inline void selection_sort(int array[], int size)
{
int i;
int min_index;
for (i=0; i < size-1; ++i) {
min_index = get_min_index(array, i, size-1);
if (min_index != i) swap(array, i, min_index) ;
}
}
int main( )
{
int array_1[] = {7, 3, 8, 2, 1, 5, 4};
print(array_1, 7);
selection_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);
selection_sort(array_2, 10);
print(array_2, 10);
cout << endl;
int array_3[] = {1, 2, 3};
print(array_3, 3);
selection_sort(array_3, 3);
print(array_3, 3) ;
cout << endl;
int array_4[] = {3, 2, 1};
print(array_4, 3);
selection_sort(array_4, 3);
print(array_4, 3);
cout << endl;
int array_5[] = {5, 2, 1, 3};
print(array_5, 4);
selection_sort(array_5, 4) ;
print(array_5, 4);
cout << endl;
int array_6[] = {3, 3, 3};
print(array_6, 3);
selection_sort(array_6, 3);
print(array_6, 3);
cout << endl;
getch();
return 0;
}
Список
Список (list) – это контейнер, предназначенный для оптимального выполнения частых вставок и удалений элементов.
Класс-контейнер list определён в файле заголовка <list> в пространстве имён std. Класс list реализован как двунаправленный список, в котором каждый блок содержит указатели как на предыдущий, так и на последующий блок списка. Список можно пройти, следуя по связям между блоками, реализуемых обычно с помощью указателей. Для этой же цели стандартный класс контейнера списка использует механизм, называемый итератором.
Итератор – это обобщение указателя. На итератор можно ссылаться, чтобы перейти к блоку, на который он указывает.
Задание 3. Демонстрация использование итератора для доступа к блокам в списке.
#include <vcl.h>
#include <iostream.h>
#include <conio.h>
#include <list>
using namespace std;
typedef list<int> IntegerList;
int main(int argc, char* argv[])
{
IntegerList intList; // intList определён как список целых чисел
// С помощью функции push_back в список добавляются первые 10 положительных
// чётных чисел
for (int i=1; i<=10; ++i)
intList.push_back(i*2);
// С помощью итератора const_iterator осуществляется доступ к каждому блоку списка
for (IntegerList::const_iterator ci = intList.begin(); // Функция begin() возвращает итератор к
ci !=intList.end(); ++ci) // к первому блоку списка
cout << *ci << " ";
getch();
return 0;
}
Класс списка обладает ещё двумя функциями – push_front() (добавить в начало) и pop_ front() (удалить первый), которые работают аналогично функциям push_back() и pop_back(). Но вместо добавления и удаления элементов в конце, они добавляют и удаляют элементы в начале списка.