1 of 13

Kent Beck

2 of 13

Сортировки

​

​

3 of 13

Класификация

  • Сложност
  • Памет - брой необходими елементи с изключение на списъка
  • Стабилност

4 of 13

Стабилност

struct human_t h1 = { 20, “Pesho” };

struct human_t h2 = { 20, “Gosho” };

struct human_t h3 = { 10, “Tosho” };

struct human_t people[3] = { h1, h2, h3 };

stable_sort(people); // h3, h1, h2

unstable_sort(people); // h3, h2, h1 или h3, h1, h2

5 of 13

Метод на мехурчето

  • Анализиран за пръв път през 1956та година
  • Памет - само един елемент в повече
  • Лесен за имплементиране
  • Стабилен
  • Но бавен

6 of 13

Quicksort

  • Създаден през 1960та година
  • Памет - Зависи от списъка с елементи
  • Лесен за имплементиране
  • Не е стабилен
  • Но е бърз

7 of 13

Insertion sort

  • Памет - само 1 елемент
  • Стабилен
  • Бърз за малки и почти сортирани масиви

8 of 13

Упражнение: Insertion sort

i ← 1�while i < length(A)� j ← i� while j > 0 and A[j-1] > A[j]� swap A[j] and A[j-1]� j ← j - 1� end while� i ← i + 1�end while�

​

9 of 13

Shell sort

  • Donald Shell, 1959
  • Разновидност на Insertion sort
  • Сортира масива през някаква “дупка” (gap), като намалява дупката до 1
  • Например: 3-sorted масив е такъв, че през 3 елемента масивът е сортиран

​

4

1

0

5

3

2

7

6

9

8

10 of 13

Shell sort

3-sorted

​

2-sorted

​

1-sorted

4

1

0

5

3

2

7

6

9

8

1

0

3

2

4

5

7

6

9

8

0

1

2

3

4

5

6

7

8

9

11 of 13

Shell sort

  • Изборът на gap-овете е важен и бързодействието му зависи от тях.

​

N - големина на масива�k - цяло число

12 of 13

Упражнение: Shell sort

  • Имплементирайте Shell sort, като използвате insertion sort за да сортирате масивът през “дупката”. За генериране на дупките използвайте

13 of 13

Въпроси?