×

Home Discussions Write at Opengenus IQ

×

Sorting Algorithms

Sorting is an important operation as rearranging a data set optimally based on a given comparison strategy is a challenging task. The best approach depends on the characteristics of the data

Counting Sort vs Radix Sort vs Bucket Sort

This article compares counting sort, radix sort, and bucket sort with important points that will help you make out the differences between these sorting algorithms.

Time Complexity

Time and Space complexity of Quick Sort

We have explained the different cases like worst case, best case and average case Time Complexity (with Mathematical Analysis) and Space Complexity for Quick Sort.

Time and Space Complexity of Bucket Sort

We have explained the Time and Space Complexity analysis of Bucket Sort along with its algorithm, space complexity and time complexity for worst case, average case and best case.

Time and Space complexity of Bubble Sort

In this article, we have explored the time and space complexity of Bubble Sort. We have covered the mathematical complexity analysis and different cases like worst case, best case, average case, space complexity and comparison with other sorting algorithms.

Median in stream of running integers [Explained 3 Algorithms]

Given that integers are being read from a data stream, we need to find the median of all the elements read so far starting from the first integer till the last integer. This is called the Median in Running stream of Integers.

Least frequent element in an array

Given an array of N elements, our task is to find the least frequent element present in it. In this article, we are going to talk about 3 methods to solve this problem along with their implementation.

Time Complexity

Time & Space Complexity of Selection Sort

In this article, you will learn about Time Complexity and Space Complexity of Selection Sort algorithm along with the complete mathematical analysis of the different cases.

Time Complexity of Insertion Sort

The average code and worst case time complexity of Insertion Sort is O(N^2) and the best case time complexity is O(N). The space complexity is O(N) for N elements.

Column Sort Algorithm

Column Sort Algorithm is a non-traditional sorting algorithm for Distributed Memory Clusters (DMC) (means multiple processors). It is a generalization of odd-even merge sort and is used in a parralel system where multiple CPUs are available for use.

Commonly asked interview questions on sorting algorithms. Power booster for your interview preparation!

In this article, we have presented several multiple choice questions (MCQs) on Sorting Algorithms for coding interviews with answers. This will help you get prepared.

Comparison b/w Different Advanced Sorting algorithms (Interview preparation)

We have reviewed and compared different Advanced Sorting algorithms that will help you in your Interview preparation. We have covered 5 sorting algorithms namely bucket, radix, counting, heap and shell sort.

Different Basic Sorting algorithms. Know when to use which one and Ace your tech interview!

We have covered the basic ideas of the basic sorting algorithms such as Insertion Sort and others along with time and space complexity and Interview questions on sorting algorithms with answers.

Pancake Sort Algorithm (in-place, not stable)

Pancake sort is a sorting algorithm in which the only allowed operation is to "flip" one end of the list. It is inplace but not stable. Pancake sort is called so because it resembles sorting pancakes on a plate with a spatula, where you can only use the spatula to flip some of the top pancakes.

Tim Sort

Tim Sort is a hybrid stable sorting algorithm that takes advantage of common patterns in data, and utilizes a combination of an improved Merge sort and Binary Insertion sort along with some internal logic to optimize the manipulation of large scale real-world data.

Postman Sort

Postman sort works by sorting the integers of an array from their most significant digits to their least significant digits. It is a variant of radix sort.

Bozosort

Bozosort is a random sorting algorithms where the key idea is to swap any two elements of the list randomly and check if the list is sorted. The average time complexity of Bozosort is O(N!) and the space complexity is O(1).

Gnome Sort

Gnome Sort is a simple sorting algorithm with time complexity O(N^2) where the key idea is to swap adjacent elements (if not in order) to sort the entire list

Stooge Sort

Stooge sort performs sorting in first 2/3 part and then it performs sorting in last 2/3 part. After that, sorting is done on first 2/3 part to ensure the array is sorted.

Pigeonhole Sort

Pigeonhole sorting is a sorting algorithm that is suitable for sorting lists of elements where the number of elements and the number of possible key values are approximately the same.

Cocktail Shaker Sort / Bidirectional bubble sort

Cocktail Sort is a variation of Bubble sort. The Bubble sort algorithm always traverses elements from left and moves the largest element to its correct position in first iteration and second largest in second iteration and so on. It traverses through a given array in both directions alternatively.

Odd Even Sort / Brick Sort

Odd Even Sort uses parallel algorithm which is based on bubble sort technique. It is also known as Brick Sort. It has a best time complexity of O(N) whereas the worst case time complexity is O(N^2)

Sleep Sort

Sleep Sort is time-based sorting technique. We create different threads for each individual element present in the array. The thread is then made to sleep for an amount of time that is equal to value of the element for which it was created. Time complexity is O(NlogN + max(input))

Circle Sort

Circle sort is a sorting algorithm in which diametrically opposite elements are compared to each other and swapped with an average time complexity of O(N log N) and space complexity of O(1). It is an unstable, recursive, parallelizable, in place sorting algorithm

Cartesian tree sorting

Cartesian tree sorting, also called Levcopoulos Petersson algorithm is an adaptive sorting algorithm, i.e. it performs much better on a partially sorted data. It needs two data structures a Cartesian tree and a priority queue. The algorithm here uses min-heap Cartesian tree to give a sorted sequence

Cycle Sort

Cycle sort is a comparison based sorting algorithm which forces array to be factored into the number of cycles where each of them can be rotated to produce a sorted array with O(N^2) time complexity It is an in-place and unstable sorting algorithm and is optimal in terms of number of memory writes