Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Метод линейной вставки



 

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

Первый элемент вектора A помещается в первую позицию вектора B. Длина вектора становится равной 1.

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

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

 

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

B[1]:=A[1];

k:=1;

For i:=2 to n do

Begin

j:=1;

While (j<=k) and (a[i]>b[j]) do

j:=j+1;

If j=k+1 then

Begin

b[j]:=a[i];

k:=k+1;

End

Else

Begin

For l:=k+1 downto j+1 do

b[l]:=b[l-1];

b[j]:=a[i];

k:=k+1;

end;

end;

 

Сравнение методов по основным характеристикам

для вектора размерности n

Метод сортировки Минимальное и максимальное число сравнение Количество перемещений или обменов
Линейный выбор , n перемещений
Линейный выбор с обменом , n обменов
Линейны выбор с подсчетом , n перемещений и подсчетов
Парный обмен n, обменов
Метод стандартного обмена n, обменов
Метод просеивания n, обменов
Метод линейной вставки n, перемещений

 




Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.