Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Функция сортировки прямым выбором





94 67

ЕЯ94

061 142

И 67

Начальные ключи

Сортировка с помощью прямого выбора

Функция сортировки с помощью метода прямого включения

Сортировка с помощью прямого включения

Элементы массива условно разделяются на готовую последовательность ах2, ..., а{.\ и входную последовательность аи а2, ..., апЛ [1, 3, 9, 10, 13]. На каждом шаге z-й элемент помещается на подходящее место в готовую последовательность (рис. 3.2).


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Начальные ключи i = 1 i = 2 i = 3 i=4 i = 5 i = 6 i = 7  
44^12 42 94 18 06 67
44| 14294 18 06 67
 
t
12|44 55^94 18 06 67
 
t
12|42|44 55g]18 06 67
T
12 42 44 55|94[Ц0667
^^^F
^f
12|ia|4244 55 94ГЯ67
г---------------- "---------- ~
0б|12 18 42 44 55 94 ГЯ
^^
06 12 18 42 44 55|67|94

Рис. З.2. Пример сортировки Алгоритм сортировки

 

for( i=l; i<n; i++ )
{  
x=a [ i ] ;  
включение х на соответствующее место
среди a0, . . i Si
}  

В реальном процессе поиска подходящего места удобно, чередуя сравнения и движения по последовательности, как бы просеивать х, т. е. х сравнивается с очередным элементом о,-, а затем либо х вставляется на свободное место, либо щ сдвигается (передаётся) вправо и процесс «уходит» влево. Процесс просеивания закончится при выполнении одного из двух следующих условий:

1. Найден элемент о,- с ключом, меньшим, чем ключ у х.

2. Достигнут левый конец готовой последовательности.


void insertionSort(int numbers[], int array_size)

{

int i, j , index;

for (i=l; i < array_size; i++)

{

index = numbers[i];

j = i;

while ((j > 0) && (numbers[j-1] > index))



{

numbers[j] = numbers[j-1];

j = j - i; }

numbers[j] = index; } }

Анализ алгоритма.Число сравнений ключей Сг при г-м просеивании составляет самое большое /-1, самое меньшее 1. Если предположить, что все перестановки из п ключей равновероятны, то среднее число сравнений — г/2. Число пересылок Mt равно Сг+2. Поэтому общее число сравнений и пересылок таковы [3]:

Ccp = {n2 + n- 2)1 A; Mcp = (n2+9n-\0)/4; Cmax = (n2 + n- 4)/4; Mmin = (n2 + Ъп- 4)/2.

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

Резюме: сортировка методом прямого включения — не очень подходящий метод для ЭВМ, так как включение элемента с последующим сдвигом на одну позицию целой группы элементов неэффективно.

Метод сортировки основан на следующих правилах [1, 3, 9, 10, 13]:

1. Выбирается элемент с наименьшим ключом.

2. Он меняется местами с первым элементом а0.

3. Затем эти операции повторяются с оставшимися п-\ элементами, п-2 элементами и так далее до тех пор, пока не останется один, самый большой элемент.

На рис. 3.3 приведен процесс сортировки этим методом.



и







 







 


94 ЕЯ 44

Ш42"Э41Я



 




 

т




 



42 Ш 55 ЕЛ 67



 






 

441*194



 








 


 

I I

Рис. 3.3. Пример сортировки Алгоритм формулируется следующим образом

for(i=0; i<n-l; i++) {

присвоить к индекс наименьшего элемента из a[i] ..а[п-1] ; поменять местами a[i] и а[к];

}

Сортировка прямым выбором в некотором смысле противоположена сортировке прямыми включениями. При прямом включении на каждом шаге рассматривается только один очередной элемент входной последовательности и все элементы готовой последовательности для нахождения места включения. При прямом выборе для поиска одного элемента с наименьшим ключом просматриваются все элементы входной последовательности и найденный элемент помещается как очередной элемент в конец готовой последовательности.


void selectionSort(int numbers[], int array_size)

{

int i, j;

int min, temp;

for( i = 0; i < array_size-l; i++ )

{

min = i;

for( j = i+1; j < array_size; j++ )

{

if (numbers[j] < numbers[min]) min = j; }

temp = numbers[i]; numbers[i] = numbers[min]; numbers[min] = temp; } }

Анализ алгоритма[З]. Число сравнений ключей С не зависит от порядка ключей:

С=У(2п2-2п). Число перестановок минимально

Mmin = 3(n-l) в случае изначально упорядоченных ключей и максимально

Мтах = п21А + Ъ(п-\\ если первоначально ключи располагаются в обратном порядке. Среднее число пересылок

Мер ~ «(1П П + g),

где g = 0,577216... — константа Эйлера.

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

Поможем в написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой




Дата добавления: 2014-11-29; Просмотров: 501; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:
studopedia.su - Студопедия (2013 - 2022) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.03 сек.