About

⛄ Currently frozen ⛄

If you want to learn something, try to teach it

This repository has been created to store all the tutorial projects I've written. I will try to place each tutorial project in C and C++. All these projects consist of search and sorting algorithms, which are the basis for other more complex projects. Also, these projects consist Data Structures.

It's a great opportunity to learn Git, Make for build automation and Markdown for readme and just help beginners learn C/C++.

Note: Use Table of content in Readme

Note: Use make in ./ to make

make	Content
make c_search	searching algorithms in C
make cpp_search	searching algrotithms in C++
make search	searching algorithms in C and C++
make c_sort	sorting algorithms in C (currently not working)
make cpp_sort	sorting algorithms in C++ (currently not working)
make sort	sorting algorithms in C and C++ (currently not working)
make all	searching and sorting algorithms in C and C++ (currently not working)
make clean	delete created executable and objective files

In progress

• ncurses
• sorting algorithms
• data structures
• style check
• testing
• in-place merge sort testing

Content

1. Searching algorithms

• Linear search
• Binary search

2. Sorting algorithms

• Quicksort
• Merge sort
• In-place merge sort
• Introsort
• Heapsort
• Insertion sort
• Block sort
• Timsort
• Selection sort
• Cubesort
• Shellsort
• Bubble sort
• Exchange sort
• Tree sort
• Cycle sort
• Library sort
• Patience sorting
• Smoothsort
• Strand sort
• Tournament sort
• Cocktail shaker sort
• Comb sort
• Gnome sort
• Odd-even sort

3. Data Structures

• Array
• String
• List
• Vector
• Queue
• Stack
• Set
• Binary Tree
• Graph

1. Searching algorithms

Linear search

A linear search sequentially checks each element of the list until it finds an element that matches the target value. If the algorithm reaches the end of the list, the search terminates unsuccessfully.

Perfromance	Big O
Worst-case	$O(n)$
Best-case	$O(1)$
Average	$O(n)$

Algorithm

1. Start at the beginning.
2. Compare the first element with the target.
3. If the current element matches the target value, the search is successful.
4. If the current element does not match the target value, move to the next element.
5. Repeat steps 3 and 4.
6. If you reach the end of the list without finding a match, the target value is not present in the list or array.

⬆️Back to top

---

Binary search

Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.

Perfromance	Big O
Worst-case	$O(log (n))$
Best-case	$O(1)$
Average	$O(log (n))$

Algorithm

1. Start with a sorted array of elements. Binary search works efficiently on sorted arrays.
2. Set two pointers, "low" and "high," to mark the lower and upper bounds of the search space. Initially, "low" points to the first element, and "high" points to the last element of the array.
3. Calculate the middle index of the search space by taking the average of "low" and "high": $middle = \frac{low + high}{2}$
4. Compare the target value you're searching for with the element at the middle index:

• If the target value matches the element at the middle index, the search is successful, and you can return the index or any desired output.
• If the target value is less than the element at the middle index, it means the target must be in the lower half of the search space. Update "high" to be one less than the middle index: $high = middle - 1$
• If the target value is greater than the element at the middle index, it means the target must be in the upper half of the search space. Update "low" to be one more than the middle index: $low = middle + 1$

5. Repeat steps 3-4 until either the target value is found or the search space is empty. An empty search space occurs when "low" becomes greater than "high".
6. If the search space is empty and the target value has not been found, it means the target is not present in the array.

⬆️Back to top

---

2. Sorting algorithms

Quicksort

Quicksort (Tony Hoare) is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

Perfromance	Big O
Worst-case	$O(n^2)$
Best-case	$O(n \times log (n))$
Average	$O(n \times log (n)$

Algorithm

1. Choose a pivot element from the array. This pivot element will be used to partition the array into two halves.
2. Reorder the array so that all elements smaller than the pivot come before the pivot, and all elements greater than the pivot come after it. This process is called partitioning. After this step, the pivot element will be in its final sorted position.
3. Recursively apply the above steps to the sub-array of elements that are smaller than the pivot and the sub-array of elements that are greater than the pivot.
4. Repeat steps 1 to 3 until the entire array is sorted. This means recursively applying the algorithm to the smaller sub-arrays until they contain only one element (which is already considered sorted).

⬆️Back to top

---

Merge sort

Merge Sort is a popular sorting algorithm that follows the divide-and-conquer principle. It works by dividing the input array into smaller sub-arrays, sorting them separately, and then merging them back together to obtain a sorted array.

Perfromance	Big O
Worst-case	$O(n \times log (n))$
Best-case	$O(n \times log (n))$
Average	$O(n \times log (n))$

Algorithm

1. Divide. The input array is recursively divided into two halves until we reach the base case, which is when the array contains only one element or is empty.
2. Conquer. Once the array is divided into individual elements, the merging process begins. The two sub-arrays are merged by comparing the elements at corresponding positions and placing them in the correct order. This is done recursively until all sub-arrays are merged.
3. Merge. To merge the sub-arrays, we create an auxiliary array to store the sorted elements. We maintain three pointers: i for the left sub-array, j for the right sub-array, and k for the auxiliary array. At each step, we compare the elements at positions i and j. The smaller element is placed in the auxiliary array at position k, and the corresponding pointer is incremented. This process continues until all elements have been merged.
4. Copy. After merging all the sub-arrays, the sorted elements are stored in the auxiliary array. We copy these elements back into the original input array, replacing the unsorted elements with the sorted ones.

⬆️Back to top

---

In-place merge sort

In-place merge sort is an efficient sorting algorithm that works by repeatedly dividing the input array into smaller subarrays, sorting them, and then merging them back together in-place. It is called "in-place" because it does not require extra memory to perform the sorting process. The main idea behind the in-place merge sort is to use a combination of merging techniques and recursion to sort the array. Here are the key steps involved in the algorithm:

1. Divide the input array into two halves by finding the middle index.
2. Recursively apply the merge sort algorithm to both halves.
3. Merge the two sorted subarrays back into the original array using an in-place merging technique.

Perfromance	Big O
Worst-case	$O(n \times log (n))$
Best-case	$O(n \times log (n))$
Average	$O(n \times log (n))$

Algorithm

1. If the input array has only one element or is empty, it is already considered sorted.
2. Divide the array into two halves by finding the middle index.
3. Recursively apply the in-place merge sort algorithm to the first half of the array.
4. Recursively apply the in-place merge sort algorithm to the second half of the array.
5. Merge the two sorted halves back into the original array using the in-place merging technique.
6. Repeat steps 2-5 until the entire array is sorted.

⬆️Back to top

---

Introsort

In progress...

Algorithm

In progress...

⬆️Back to top

---

Heapsort

In progress...

Algorithm

In progress...

⬆️Back to top

---

Insertion sort

In progress...

Algorithm

In progress...

⬆️Back to top

---

Block sort

In progress...

Algorithm

In progress...

⬆️Back to top

---

Timsort

In progress...

Algorithm

In progress...

⬆️Back to top

---

Selection sort

In progress...

Algorithm

In progress...

⬆️Back to top

---

Cubesort

In progress...

Algorithm

In progress...

⬆️Back to top

---

Shellsort

In progress...

Algorithm

In progress...

⬆️Back to top

---

Bubble sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass-throughs continue until the list is sorted.

Perfromance	Big O comprasions
Worst-case	$O(n^2)$
Best-case	$O(n)$
Average	$O(n^2)$

Perfromance	Big O swaps
Worst-case	$O(n^2)$
Best-case	$O(1)$
Average	$O(n^2)$

Algorithm

1. Start at the begin of the list
2. Compare element and next from it
3. If the current element is greater than the next element, swap them.
4. Go to next element and repeat third step.
5. If th current element - last element of the list, list is sorted.

⬆️Back to top

---

Exchange sort

In progress...

Algorithm

In progress...

⬆️Back to top

---

Tree sort

In progress...

Algorithm

In progress...

⬆️Back to top

---

Cycle sort

In progress...

Algorithm

In progress...

⬆️Back to top

---

Library sort

In progress...

Algorithm

In progress...

⬆️Back to top

---

Patience sorting

In progress...

Algorithm

In progress...

⬆️Back to top

---

Smoothsort

In progress...

Algorithm

In progress...

⬆️Back to top

---

Strand sort

In progress...

Algorithm

In progress...

⬆️Back to top

---

Tournament sort

In progress...

Algorithm

In progress...

⬆️Back to top

---

Cocktail shaker sort

In progress...

Algorithm

In progress...

⬆️Back to top

---

Comb sort

In progress...

Algorithm

In progress...

⬆️Back to top

---

Gnome sort

In progress...

Algorithm

In progress...

⬆️Back to top

---

Odd-even sort

In progress...

Algorithm

In progress...

⬆️Back to top

---

3. Data Structures

Array

Array - collection of elements. All elements of the array have the same memory size. They have at least one array index or key .

Example (One-dimensional array of 10 ints):

void foo{
 int N = 10; // Size of array
 int Array_A[N] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // elements of array
 int Array_B[10]; // empty array (size 10)
}

Also, array elements can be arrays themselves. This allows for creating a two-dimensional array. This structure resembles a chessboard or a table. Moreover, the size of the array and the size of the array-elements can differ. However, the size of all array-elements must match by definition of an array.

Example (Two-dimensional array of 10x10 ints):

void foo{
 int N = 10; // Size of array
 int M = 10; // Size of array-elements
 int Array_A[N][M]; // Two-dimensional array
}

Of course, it is evident that both three-dimensional and n-dimensional arrays can be created. Are arrays in C++ same as C?

⬆️Back to top

---

String

In progress...

⬆️Back to top

---

List

In progress...

⬆️Back to top

---

Vector

In progress...

⬆️Back to top

---

Queue

In progress...

⬆️Back to top

---

Stack

In progress...

⬆️Back to top

---

Set

In progress...

⬆️Back to top

---

Binary Tree

In progress...

⬆️Back to top

---

Graph

In progress...

⬆️Back to top

---