Сортировка выбором

Дата добавления: 2015-08-31; просмотров: 1172; Нарушение авторских прав

Проведем аналогию сортировки массива по методу выбору с сортировкой игральных карт. Имеются набор игральных карт и их необходимо разложить по возрастанию из приоритета. Сначала необходимо найти минимальную карту и поменять ее местами с первой картой в наборе. Имеем следующую картину: неотсортированный набор карт уменьшился на 1 карту, а отсортированный содержит 1 карту. Дальше необходимо продолжать сортировку карт, начиная со второй карты. Так следует продолжать, пока не останется две карты. Если необходимо меняем их местами и сортировка набора карт закончена.

Принцип метода:

Состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке.

Пусть n – количество элементов в массиве, i – минимальный индекс элемента в неотсортированной части массива.

1. Поиск минимального элемента, начиная с элемента с индексом i и до конца массива (i<n). При первом поиске i=0.

2. Найденный минимальный элемент меняется местами с i-тым элементом массива.

3. Уменьшаем размер неотсортированной части массива (увеличиваем i на 1).

4. Выполняем пункты 1 – 3 для всех элементов массива от 0 до n-2.

Пример 2. Выполним сортировку массива по возрастанию элементов по методу выбора.

Проход	0	1	2	3	4	5	6	7
		-4		-12	-7
	i=0			imin=3


	-12	-4			-7
		i=1			imin=4


	-12	-7			-4
			i=2		imin=4


	-12	-7	-4
				i=3				imin=7


	-12	-7	-4
					i=4, imin=4


	-12	-7	-4
						i=5	imin=6


	-12	-7	-4
							i=6	imin=7


	-12	-7	-4

Блок-схема алгоритма сортировки выбором

#include <iostream>

using namespace std;

#include <stdlib.h>

#include <time.h>

<== предыдущая лекция | следующая лекция ==>

Сортировка обменом («пузырьковая» сортировка) | Сортировка вставками