Sorting-Algorithms-Blender ========================== Sorting algorithms visualized using the Blender Python API. Table of contents ================= * [Introduction](https://github.com/ForeignGods/Sorting-Algorithms-Blender/raw/main/#introduction) * [Description](https://github.com/ForeignGods/Sorting-Algorithms-Blender/raw/main/#description) * [Getting Started](https://github.com/ForeignGods/Sorting-Algorithms-Blender/raw/main/#getting-started) * [Limitations](https://github.com/ForeignGods/Sorting-Algorithms-Blender/raw/main/#limitations) * [Possible Updates](https://github.com/ForeignGods/Sorting-Algorithms-Blender/raw/main/#possible-updates) * [Sorting Algorithms](https://github.com/ForeignGods/Sorting-Algorithms-Blender/raw/main/#sorting-algorithms) * [Bubble Sort](https://github.com/ForeignGods/Sorting-Algorithms-Blender/raw/main/#bubble-sort) * [Insertion Sort](https://github.com/ForeignGods/Sorting-Algorithms-Blender/raw/main/#insertion-sort) * [Selection Sort](https://github.com/ForeignGods/Sorting-Algorithms-Blender/raw/main/#selection-sort) * [Heap Sort](https://github.com/ForeignGods/Sorting-Algorithms-Blender/raw/main/#heap-sort) * [Shell Sort](https://github.com/ForeignGods/Sorting-Algorithms-Blender/raw/main/#shell-sort) * [Merge Sort](https://github.com/ForeignGods/Sorting-Algorithms-Blender/raw/main/#merge-sort) * [Quick Sort](https://github.com/ForeignGods/Sorting-Algorithms-Blender/raw/main/#quick-sort) * [Big O](https://github.com/ForeignGods/Sorting-Algorithms-Blender/raw/main/#big-o) * [What is Big O Notation?](https://github.com/ForeignGods/Sorting-Algorithms-Blender/raw/main/#what-is-big-o-notation) * [Time Complexity Notations](https://github.com/ForeignGods/Sorting-Algorithms-Blender/raw/main/#time-complexity-notations) * [Table of Sorting Algorithms](https://github.com/ForeignGods/Sorting-Algorithms-Blender/raw/main/#table-of-sorting-algorithms) * [Big O Complexity Chart](https://github.com/ForeignGods/Sorting-Algorithms-Blender/raw/main/#big-o-complexity-chart) Introduction ============ ## Description Running one of the scripts in this project generates primitive meshes in Blender, wich are animated to visualize various sorting algorithms.
Keyframes are incrementaly inserted according to the current position of the element in the array during the sorting.
The four folders (sort_circle, sort_color, sort_combined, sort_scale) contain four different types of visualization. |Type|Sorting Criteria|Representation of Index|Extras| |:--:|:--------------:|:---------------------:|:----:| |sort_circle|hsv of material|rotation of cuboid|hsv = 360°| |sort_color|red + green of material|location of plane|custom color gradient| |sort_combined|red + green of material|location of plane|multiple 2d arrays arranged into a cube| |sort_scale|scale of cubiod|location of cuboid|array access and comparison counter| ## Getting Started

Download, install and start Blender .

Open the .py file in the Text Editor.
Click the play button to run the script.

## Limitations These visualizations don't show the efficiency of the algorithms.
They only visualize movement of the elements within the array.
But the array access and comparison counters are indicators of the time complexity of the algorithms.
For more information about the time complexity, you can take a look at the [Big O Table](https://github.com/ForeignGods/Sorting-Algorithms-Blender/raw/main/#table-of-sorting-algorithms).
## Possible Updates Below I compiled a list of features that could be implemented in the future.

increase efficiency of the setup_array() function, to allow greater object count
adding audio "Audibilization"
adding more sorting algorithms
adding more types of visualization e.g. Sphere Agitation , Cube Amalgam , Dynamic Hoops

auto generate camera with correct transforms based on the count of sorted objects

create panel were you can choose different options like colors, sorting algorithms and count of objects

improve merge sort visualization so there are no gaps and overlapping objects

Contributions to this project with either ideas from the list or your own are welcome.

Sorting Algorithms ================== |combined_sort_cube.py| | ------------- | |![cube_sort_opti](https://user-images.githubusercontent.com/78089013/176444887-4d68b8df-cc91-4415-b3d4-8540303f284e.gif)|

## Bubble Sort

Bubble sort is one of the most straightforward sorting algorithms, it makes multiple passes through a list.

Starting with the first element, compare the current element with the next element of the array.
If the current element is greater than the next element of the array, swap them.
If the current element is less than the next element, move to the next element.

In essence, each item “bubbles” up to the location where it belongs.

| bubble_sort_scale.py|bubble_sort_color.py|bubble_sort_circle.py| | ------------- |-------------|------------| |![bubble_scale_opti](https://user-images.githubusercontent.com/78089013/176308250-e75134b8-177a-40bc-b984-5cfa13c09baa.gif)|![bubble_color_opti](https://user-images.githubusercontent.com/78089013/176433216-9b3b09c6-12ce-4713-bee9-ecbab979efbd.gif)|![bubble_circle_perf](https://user-images.githubusercontent.com/78089013/176554030-355ece1a-9560-4928-bbf2-40445f1fe33e.gif)| ## Insertion Sort

Like bubble sort, the insertion sort algorithm is straightforward to implement and understand.

Iterate from arr[1] to arr[n] over the array.
Compare the current element (key) to its predecessor.
If the key element is smaller than its predecessor, compare its elements before.
Move the greater elements one position up to make space for the swapped element.

It splits the given array into sorted and unsorted parts, then the values from the unsorted parts are picked and placed at the correct position in the sorted part.

| insertion_sort_scale.py|insertion_sort_color.py| | ------------- |:-------------:| |![insertion_scale_opti](https://user-images.githubusercontent.com/78089013/176308303-c76e5296-d91e-4c83-badc-bdb9546c230b.gif)|![insertion_color_opti](https://user-images.githubusercontent.com/78089013/176433668-28088cc9-5d98-4ba5-971f-0cb9b02348a5.gif)| ## Selection Sort The algorithm maintains two subarrays in a given array.

The subarray which is already sorted.
Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

|selection_sort_scale.py|selection_sort_color.py|selection_sort_circle.py| | ------------- |:-------------:|-------| |![selection_sort_opti](https://user-images.githubusercontent.com/78089013/176308368-bdf31895-fae2-49ef-b9ad-8845a7fcba7a.gif)|![selection_color_opti](https://user-images.githubusercontent.com/78089013/176435219-96aa4818-4ae5-411e-916c-69a3285e6f14.gif)|![selection_circle_perf](https://user-images.githubusercontent.com/78089013/176554628-3c754a53-aca4-46ff-a015-0b8a6dac2999.gif)| ## Heap Sort Based on the binary heap data structure, heap sort is mainly considered as a comparison-based sorting algorithm.
In this sorting technique, at first, the minimum element is found out and then the minimum element gets placed at its right position at the beginning of the array.
For the rest of the elements, the same process gets repeated.
So, we can say that heap sort is quite similar to the selection sort technique.
Heap sort basically recursively performs two main operations:

Build a heap H, using the elements of array.
Repeatedly delete the root element of the heap formed in 1st phase.

|heap_sort_scale.py|heap_sort_color.py| | ------------- |:-------------:| |![heap_scale_opti](https://user-images.githubusercontent.com/78089013/176308418-ca1bdf07-9266-429f-a240-2b5484de6f51.gif)|![heap_color_opti](https://user-images.githubusercontent.com/78089013/176433372-e74c2fce-f4b1-4b6e-98b1-ea3fe5c80b48.gif)| ## Shell Sort

The shell sort algorithm extends the insertion sort algorithm and is very efficient in sorting widely unsorted arrays.
The array is divided into sub-arrays and then insertion sort is applied.
The algorithm is:

Calculate the value of the gap.
Divide the array into these sub-arrays.
Apply the insertion sort.
Repeat this process until the complete list is sorted.

This sorting technique works by sorting elements in pairs, far away from each other and subsequently reduces their gap.
The gap is known as the interval. We can calculate this gap/interval with the help of Knuth’s formula.

|shell_sort_scale.py|shell_sort_color.py| | ------------- |:-------------:| |![shell_scale_opti](https://user-images.githubusercontent.com/78089013/176308477-b31cd21f-e7b7-43ca-b663-ecd991f1f5dd.gif)|![shell_color_opti](https://user-images.githubusercontent.com/78089013/176433418-ab39374e-0783-453d-8a9c-d4a4441e2440.gif)| ## Merge Sort Merge sort uses the divide and conquer approach to sort the elements.
It is one of the most popular and efficient sorting algorithms.
The sub-lists are divided again and again into halves until the list cannot be divided further.
Then we combine the pair of one element lists into two-element lists, sorting them in the process.
The sorted two-element pairs is merged into the four-element lists, and so on until we get the sorted list. | merge_sort_scale.py|merge_sort_color.py|merge_sort_circle.py| | ------------- |:-------------:|------------| |![merge_scale_opti](https://user-images.githubusercontent.com/78089013/176308527-78abf018-f756-475d-bae9-32b93b47fb17.gif)|![merge_color_opti](https://user-images.githubusercontent.com/78089013/176433465-66af0062-7425-4a60-8a4d-b49095d6c0cb.gif)|![merge_circle_perf](https://user-images.githubusercontent.com/78089013/176554327-0ed04372-5aa5-4236-b8bb-47d5d31d54a1.gif)| ## Quick Sort Like Merge Sort, Quick Sort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of Quick Sort that pick pivot in different ways.

Always pick first element as pivot.
Always pick last element as pivot.
Pick a random element as pivot.
Pick median as pivot. (implemented below)

The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x.
All this should be done in linear time. | quick_sort_scale.py|quick_sort_color.py|quick_sort_circle.py| | ------------- |:-------------:|--------| |![quick_scale_opti](https://user-images.githubusercontent.com/78089013/176308577-3c13996b-7443-4b67-838c-7de3dc36311f.gif)|![quick_color_opti](https://user-images.githubusercontent.com/78089013/176433517-cc0cc985-c60d-42e9-a5b0-ecbe8c2621bf.gif)|![quick_circle_perf](https://user-images.githubusercontent.com/78089013/176554458-2d7b97ad-8c00-4ab6-b988-4d74fa466994.gif)| Big O ===== ### What is Big O Notation? Big O notation is the language we use for talking about how long an algorithm takes to run.
It's how we compare the efficiency of different approaches to a problem.
With Big O notation we express the runtime in terms of **how quickly it grows relative to the input, as the input gets arbitrarily large.** Let's break that down:

how quickly the runtime grows It's hard to pin down the exact runtime of an algorithm.
It depends on the speed of the processor, what else the computer is running, etc. So instead of talking about the runtime directly, we use big O notation to talk about how quickly the runtime grows.
relative to the input If we were measuring our runtime directly, we could express our speed in seconds.
Since we're measuring how quickly our runtime grows, we need to express our speed in terms of...something else.
With Big O notation, we use the size of the input, which we call "n".
So we can say things like the runtime grows "on the order of the size of the input" (O(n)) or "on the order of the square of the size of the input" (O(n^2)).
as the input gets arbitrarily Our algorithm may have steps that seem expensive when "n" is small but are eclipsed eventually by other steps as "n" gets huge.
For big O analysis, we care most about the stuff that grows fastest as the input grows, because everything else is quickly eclipsed as "n" gets very large.

### Time Complexity Notations These are the asymptotic notations that are used for calculating the time complexity of the sorting algorithms:

Big O Notation, O:
Omega Notation, Ω:
Theta Notation, θ:

### Table of Sorting Algorithms In applications such as in radix sort, a bound on the maximum key value "k" will be known in advance, and can be assumed to be part of the input to the algorithm.
However, if the value of "k" is not already known then it may be computed, as a first step, by an additional loop over the data to determine the maximum key value.

Algorithm	Time Complexity			Space Complexity
	Best Case	Average Case	Worst Case	Worst Case
Quick Sort	`Ω(n log(n))`	`Θ(n log(n))`	`O(n^2)`	`O(log(n))`
Merge Sort	`Ω(n log(n))`	`Θ(n log(n))`	`O(n log(n))`	`O(n)`
Tim Sort	`Ω(n)`	`Θ(n log(n))`	`O(n log(n))`	`O(n)`
Heap Sort	`Ω(n log(n))`	`Θ(n log(n))`	`O(n log(n))`	`O(1)`
Bubble Sort	`Ω(n)`	`Θ(n^2)`	`O(n^2)`	`O(1)`
Insertion Sort	`Ω(n)`	`Θ(n^2)`	`O(n^2)`	`O(1)`
Selection Sort	`Ω(n^2)`	`Θ(n^2)`	`O(n^2)`	`O(1)`
Tree Sort	`Ω(n log(n))`	`Θ(n log(n))`	`O(n^2)`	`O(n)`
Shell Sort	`Ω(n log(n))`	`Θ(n(log(n))^2)`	`O(n(log(n))^2)`	`O(1)`
Bucket Sort	`Ω(n+k)`	`Θ(n+k)`	`O(n^2)`	`O(n)`
Radix Sort	`Ω(nk)`	`Θ(nk)`	`O(nk)`	`O(n+k)`
Counting Sort	`Ω(n+k)`	`Θ(n+k)`	`O(n+k)`	`O(k)`
Cube Sort	`Ω(n)`	`Θ(n log(n))`	`O(n log(n))`	`O(n)`

### Big O Complexity Chart