More and more Sorting Algorithm

আপাতত এগুলা দেখে মাথা নষ্ট করার দরকার নাই।

Bucket Sort

bucket sort or bin sort. you partition the whole array into small buckets. put numbers in the related bucket and then sort each bucket by another algorithm or using bucket sort.

for example, you have an array where numbers between 1 to 100 is for a million times.

If you want to sort it by any of the method we talked before, will be time consuming.

Bucket sort would be convenient here

Shell Sort

how does it works: it takes a gap. for example gap of five. in that case it will take all the elements at 1, 6, 11, 16... and will sort them among themselves. Hence this gapped array will be sorted. secondly it will take 2, 7, 12, 17th positioned element and will sort among themselves

second time. it will take all in three positioned. like 1, 4, 7, 10, 13, 16, 19 and will sort among themselves. after this all these will be sorted. and then goes to 2, 5, 8, 11, 14, 17, 20

Then it will do 1 gap sorting...

shell sort is rarely used in application as it performs more operations and have higher cache miss ratio than quick sort.

ref: wiki: shell sort

Pigeonhole Sort

also known as count sort (not counting sort). you have an array. and each element has a key value pair. you iterate over the original array and put each element based on the key to its small array (pigeon hole). and then iterate over the pigeonhole array in order.

Counting sort: counting sort works same way, but it returns number of elements for each key other than the original elements. very thoughtful name, indeed.

ref: wiki pigeonhole sort

Binary Tree sort

Radix Sort

its a non comparative integer sorting algorithm. it compares the integer based on the position of the number (significance).

there are two radix sort. LSD (least significant digit) radix sort and MSD (most significant digit) radix sort

cocktail sort

also known as bidirectional bubble sort, cocktail shaker sort, shaker sort, ripple sort, shuffle sort, shuttle sort.

difference with bubble sort is that this sort in both direction each pass. Its difficult to implement.

Other sorting algorithms

patience sorting: sorting based on solitaire card game. you draw card either put in a new pile or existing pile. when you are putting card on a pile, a higher value card will go on top

comb sort: it is an improvement on bubble sort. the inner loop of bubble sort is modified so that gap between swapped elements goes down for each iteration of the outer loop by using a shrink factor. wiki comb sort the usual shrink factor is 1.3 and the gap (>=1) is calculated by Math.floor(lenght/1.3)

Spaghetti sort: it takes linear time but need parallel processor to sort. read it to understand

Intro sort:combines both quick sort and heap sort. so that worst and average becomes O(nlongn). it starts with quick sort and switch to heap sort if recursion depth increases based on the number of elements to be sorted.

Timsort: this is a hybrid of merge and insertion sort. try to find subset of data that is already sorted. and use that data to sort rest efficiently. and then merged by merge sort. this algorithm is primarily used in python. This actually invented by Tim peters to use in python.

Block sort: runs at least two merge operation with one insertion sort. wiki: block sort

library sort: it is an insertion sort with gaps in the array to improve insertion. wiki: library sort

Tournament sort: Its a selection sort with a priority queue to find the next element to sort. wiki: tournament sort

others: Gnome sort, unshuffle sort, Strand sort, smooth sort

আর খেয়ে দেয়ে কোন কাজ কাম না থাকলে www.JhankarMahbub.com দেখে আয়