1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
#include <iostream>
using namespace std;
// Алгоритми върху масиви.
// Пример за алгормитъм.
// Функция, която търси елемент в масив.
// Search arr, el ->
// -1 ako go nqma, + ako go ima -> indeksa
int linearSearch(const int* arr, int len, int searched)
{
for (int i = 0; i < len; i++)
{
if (arr[i] == searched)
return i;//връщаме индекса.
}
return -1;//елементът го няма
}
// Анализ - кога тези алгоритми са "бързи" и кога са "бавни".
// Сложност на алгоритъм - колко стъпки ще направи алгоритъма.
// Приемаме, че масивът е с n елемента.
// best-case: 1 стъпка O(1)
// average-case: n/2 стъпки. O(n)
// worst-case: n стъпки. O(n)
// зад 2) Търсене в масив. Масивът е сортиран.
// Двоично търсене (binary search).
//
int binarySearch(const int* arr, int len, int searched)
{
int leftIndex = 0;
int rightIndex = len - 1;
while (leftIndex <= rightIndex)
{
int midIndex = (leftIndex + rightIndex) / 2;
if (arr[midIndex] == searched)
return midIndex;
if (arr[midIndex] > searched)
rightIndex = midIndex - 1;
else
leftIndex = midIndex + 1;
}
return -1;
}
// best-case: 1 стъпка O(1)
// average-case: O(log(n))
// worst-case: O(log(n))
// Сортиран масив с 70000 елемента -> линейно търсене (70000 стъпки)
// -> двоично търсене (16 стъпки)
//Сортиране на масив.
// Пример: 9 6 3 7 -> 3 6 7 9
// Bubble sort (Сортиране по метода на мехурчето)
// "Разходка по масива"
//
void swap(int* arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//След една разходка най-големият елемент ще отиде на мястото си.
// след разходка 2-> 2-та най-големи елемента ще са на мясотот си
// след разходка 3-> 3-те ...
//Ако след една разходка, не направим нито един swap, то следва че масивът вече е сортиран.
void bubbleSort(int* arr, int len)
{
for (int j = 0; j < len - 1; j++)
{
bool isSwapped = false;
for (int i = 0; i < len - 1 - j; i++)
{
if (arr[i] > arr[i + 1])
{
swap(arr, i, i + 1);
isSwapped = true;
}
}
if (!isSwapped)
return;
}
}
//Сложност:
// best-case: O(n)
// average-case: O(n^2)
// worst-case: n*(n-1) /2 = (n^2 + n )/2 O(n^2)
// Стабилност: (следващият път)
// Selection sort (сортиране чрез пряка селекция).
// 5 8 1 4 9
void selectionSort(int* arr, int len)
{
for (int pos = 0; pos < len - 1; pos++)
{
int minIndex = pos;
for (int i = pos; i < len; i++)
{
if (arr[i] < arr[minIndex])
minIndex = i;
}
if (pos != minIndex)
swap(arr, pos, minIndex);
}
}
// Сложност:
// best-case: O(n^2)
// average-case: O(n^2)
// worst-case: О(n^2)
// Selection sort прави минимален брой swap-ове.
int main()
{
int arr[] = {5,3,2,6,1,4};
selectionSort(arr, 6);
for (int i = 0; i < 6; i++)
cout << arr[i] << " ";
//cout << binarySearch(arr, 10, 500);
}
|
