sorting - created from Mind Map

Página 1

Merge Sort

Quick Sort

Bubble Sort

Selection Sort

Bucket Sort

Radix Sort

Insertion Sort

Counting Sort

Heap Sort

The Merge Sort algorithm is a sorting algorithm that is based on the Divide and Conquer paradigm. In this algorithm, the array is initially divided into two equal halves and then they are combined in a sorted manner.

Example: When we put together a puzzle, we divide out the edge pieces first, put them together, then build the rest of the puzzle on that

Time Complexity

Space Complexity:O(N)

Average Case: O(n*logn)

Best Case: O(n*logn)

Worst Case: O(n*logn)

Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.

Example: You have a shopping list, and your mom is telling you to grab them in 15 minutes. She gives you also priorities, so you need to grab them first. You gotta rush!

Time Complexity

Space Complexity:O(n*logn)

Worst case:O(n2)

Average Case:O(n*logn)

Best Case:O(n*logn)

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity is quite high

Example:A real-world example of a bubble sort algorithm is how the contact list on your phone is sorted in alphabetical order. Or the sorting of files on your phone according to the time they were added.

Time Complexity

Space Complexity: O(1)

Worst Case: O(n2)

Average Case: O(n2)

Best Case: O(n)

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at the beginning.

Example:For example, picking apples from a tree. We can see all the apples on the tree, find and pluck the biggest one, and drop it into our basket

Time complexity

Space Complexity O(1)

Average Case O(n2)

Best Case O(n2)

Worst Case O(n2)

Bucket Sort is a sorting algorithm that divides the unsorted array elements into several groups called buckets. Each bucket is then sorted by using any of the suitable sorting algorithms or recursively applying the same bucket algorithm. Finally, the sorted buckets are combined to form a final sorted array.

Example:in a retail store they have bins in the front labeled either by department or with letter ranges (A-D, E-H, etc) to sort things for restocking that people carried to the front and didn't buy.

Time Complexity

Space Complexity: O(n*k)

Best Case: O(n + k)

Average Case: O(n + k)

Worst Case: O(n2)

Radix Sort algorithm is a stable sorting subroutine-based integer sorting algorithm. It is a sorting algorithm that does not use comparisons to sort a collection of integers. It classifies keys based on individual digits with the same significant position and value

Example:Radix sort can be applied to data that can be sorted lexicographically, such as words and integers. It is also used for stably sorting strings.

Time Complexity

Space Complexity: O(n + k)

Average Case: θ(nk)

Worst Case O(nk)

Best Case: Ω(n+k)

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Example: Cards:You first pick one card, then pick the next card and put it after the first card if it is bigger or before the first card if it is smaller; then you pick another card and insert it into its proper position.

Time Complexity

Space Complexity:O(1)

Average Case: O(n2)

Worst Case: O(n2)

Best Case: O(n)

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then do some arithmetic to calculate the position of each object in the output sequence.

Example:if the count of element 3 is 2 then, 2 is stored in the 3rd position of count array

Time Complexity

Space Complexity: O(max)

Best Case: O(n + k)

Average Case: O(n + k)

Worst Case: O(n + k)

Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to the selection sort where we first find the minimum element and place the minimum element at the beginning. Repeat the same process for the remaining elements.

Example:Heap Sorting can be applied to a sim card store where there are many customers in line. The customers who have to pay bills can be dealt with first because their work will take less time. This method will save time for many customers in line and avoid unnecessary waiting.

Time Complexity

Space Complexity: O(1)

Average Case: O(n log n)

Worst Case: O(n log n)

Best Case: O(n logn)