From c9e3d1dd8c76da82db677570bbbd555405686a78 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Fri, 11 Oct 2024 02:24:47 -0400 Subject: Add seminar01 --- .../src/searching-algorithms/binary-search.cpp | 33 +++++++++++++++++++++ Seminar01/src/sorting-algorithms/bubble-sort.cpp | 34 ++++++++++++++++++++++ .../src/sorting-algorithms/insertion-sort.cpp | 28 ++++++++++++++++++ .../src/sorting-algorithms/selection-sort.cpp | 33 +++++++++++++++++++++ 4 files changed, 128 insertions(+) create mode 100644 Seminar01/src/searching-algorithms/binary-search.cpp create mode 100644 Seminar01/src/sorting-algorithms/bubble-sort.cpp create mode 100644 Seminar01/src/sorting-algorithms/insertion-sort.cpp create mode 100644 Seminar01/src/sorting-algorithms/selection-sort.cpp (limited to 'Seminar01/src') diff --git a/Seminar01/src/searching-algorithms/binary-search.cpp b/Seminar01/src/searching-algorithms/binary-search.cpp new file mode 100644 index 0000000..b5befb0 --- /dev/null +++ b/Seminar01/src/searching-algorithms/binary-search.cpp @@ -0,0 +1,33 @@ +#include + +template +int binarySearch(const T* arr, size_t size, T elem) +{ + int left = 0; + int right = size - 1; + + while (right - left >= 0) + { + int mid = left + (right - left) / 2; + + if(arr[mid] == elem) + { + return mid; + } + else if (arr[mid] > elem) + { + right = mid - 1; + } + else + { + left = mid + 1; + } + } + + return -1; +} + +int main() +{ + +} \ No newline at end of file diff --git a/Seminar01/src/sorting-algorithms/bubble-sort.cpp b/Seminar01/src/sorting-algorithms/bubble-sort.cpp new file mode 100644 index 0000000..ac730ca --- /dev/null +++ b/Seminar01/src/sorting-algorithms/bubble-sort.cpp @@ -0,0 +1,34 @@ +#include + +template +void bubbleSort(T* arr, unsigned length) +{ + size_t lastSwappedIndex = length - 1; + + for (size_t i = 0; i < length; i++) + { + unsigned lastSwappedIndexTemp = lastSwappedIndex; + for (size_t j = 0; j < lastSwappedIndex; j++) + { + if(arr[j] > arr[j + 1]) + { + std::swap(arr[j], arr[j + 1]); + lastSwappedIndexTemp = j; + } + } + + if(lastSwappedIndex == lastSwappedIndexTemp) { break; } + lastSwappedIndex = lastSwappedIndexTemp; + } +} + +int main() +{ + int arr[] = {5, 2, 3, 1, 4}; + bubbleSort(arr, 5); + + for(int element : arr) + { + std::cout << element << " "; + } +} \ No newline at end of file diff --git a/Seminar01/src/sorting-algorithms/insertion-sort.cpp b/Seminar01/src/sorting-algorithms/insertion-sort.cpp new file mode 100644 index 0000000..00e823e --- /dev/null +++ b/Seminar01/src/sorting-algorithms/insertion-sort.cpp @@ -0,0 +1,28 @@ +#include + +template +void insertionSort(T* arr, unsigned length) +{ + for (size_t i = 1; i < length; i++) + { + int elementToInsert = arr[i]; + int j = i - 1; + while (j >= 0 && arr[j] > elementToInsert) + { + arr[j + 1] = arr[j]; + --j; + } + arr[j + 1] = elementToInsert; + } +} + +int main() +{ + int arr[] = {4, 3, 1, 5, 2, 6}; + insertionSort(arr, 6); + + for(int element : arr) + { + std::cout << element << " "; + } +} \ No newline at end of file diff --git a/Seminar01/src/sorting-algorithms/selection-sort.cpp b/Seminar01/src/sorting-algorithms/selection-sort.cpp new file mode 100644 index 0000000..5ace579 --- /dev/null +++ b/Seminar01/src/sorting-algorithms/selection-sort.cpp @@ -0,0 +1,33 @@ +#include + +template +void selectionSort(T* arr, unsigned lenght) +{ + for (size_t i = 0; i < lenght; i++) + { + size_t minElementIndex = i; + for (size_t j = i + 1; j < lenght; j++) + { + if(arr[j] < arr[minElementIndex]) + { + minElementIndex = j; + } + } + + if(i != minElementIndex) + { + std::swap(arr[i], arr[minElementIndex]); + } + } +} + +int main() +{ + int arr[] = {1, 5, 4, 2, 3, 6}; + selectionSort(arr, 6); + + for(int element : arr) + { + std::cout << element << " "; + } +} \ No newline at end of file -- cgit v1.3.1-26-gb76a