Линейный выбор

Для сортировки исходного вектора A, содержащего n элементов, необходимо n раз просмотреть элементы исходного вектора и сформировать полученный упорядоченный вектор B. При каждом просмотре находится минимальный элемент вектора и помещается в упорядоченный список.

При первом просмотре находим минимальный элемент вектора A и помещает его в первую позицию вектора B. В исходном векторе минимальный элемент заменяется фиктивной величиной, заведомо большей всех элементов вектора.

При втором просмотре опять находим минимальный элемент вектора A и помещаем его во вторую позицию вектора B. В исходном векторе A минимальный элемент снова заменяется фиктивной величиной, заведомо большей всех элементов вектора.

После n просмотров исходный вектор A будет состоять из фиктивных величин, а вектор B – из упорядоченных элементов исходного вектора A.

Просмотр	Исходный вектор А	Полученный вектор B
1-ый	2 4 8 5 6 1 2 4 8 5 6 99	1
2-ой	2 4 8 5 6 99 99 4 8 5 6 99	1 2
3-ий	99 4 8 5 6 99 99 99 8 5 6 99	1 2 4
4-ый	99 99 8 5 6 99 99 99 8 99 6 99	1 2 4 5
5-ый	99 99 8 99 6 99 99 99 8 99 99 99	1 2 4 5 6
6-ой	99 99 8 99 99 99 99 99 99 99 99 99	1 2 4 5 6 8

{Исходный вектор А}

{Полученный вектор B}

For i:=1 to n do

Begin

min:=A[i];

i_min:=i;

For j:=1 to n do

If A[j]<min then

Begin

min:=A[j];

i_min:=j;

end;

B[i]:=min;

A[i_min]:=99;

end;

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

Date: 2015-10-19; view: 280; Нарушение авторских прав