# Questions tagged [sorting]

the algorithmic problem of ordering a set of elements with respect to some ordering relation.

694 questions
Filter by
Sorted by
Tagged with
25 views

### Proof for time complexity of Insertion (k-proximate) Sort equals O(nk)

The following is the definition for Proximate Sorting given in my paper: An array of distinct integers is k-proximate if every integer of the array is at most k places away from its place in the array ...
24 views

### What factors of the integer dataset being sorted can I change, in order to compare two sorting algorithms?

I am comparing two comparison and binary data structure based sorting algorithms, the Tree Sort, and the Heap Sort. I am measuring the time taken for both algorithms to sort an increasing size of an ...
213 views

### Sorting strings using Counting Sort in O(n), where n is the total number of characters in all the strings

Suppose, you are given an array of strings of different lengths, but the total number of characters over all the strings is n. Describe an algorithm using Counting Sort to sort the strings in ...
19 views

25 views

### Quicksort Time Complexity

I am learning the Quicksort algorithm and I am struggling with understanding the time complexity. Here is the JavaScript ES6 code for the partition function that is used in the algorithm: ...
1k views

### Is this in-place merge algorithm efficient or not?

I have trouble analyzing the characteristics of this algorithm that merges two adjacent sorted lists. Basically it looks at some number of the tail of the first list, and the same number of head ...
51 views

### Theoretical lower bound of finding number of occurrences of a target integer in a sorted array

Given a sorted array of integers and a target integer, find the number of occurrences of the target integer. It is well-known that a binary search has time complexity $O(\lg n)$ where $n$ is the ...
53 views

### Choose $n$ out of $2n-1$ boxes containing at least half of all white balls and half of all black balls

We are given $2n - 1$ boxes with a total of $B$ black and $W$ white balls. In the $i$-th, box there are $w_i$ white and $b_i$ black balls. It is required to choose $n$ boxes so that, the sum of the ...
5k views

### Sorting a list of strings in lexicographic order of sorted strings

Let $A$ be a collection of strings over the alphabet $\{0,\ldots,m-1\}$ that in total contain $n$ symbols. Your task is to sort each of the strings internally, and then sort the resulting strings in ...
26 views

### Average Case Analysis of Insertion Sort as dealt in Kenneth Rosen's “Discrete Mathemathematics and its Application”

I was going through "Discrete Mathematics and its Application" by Kenneth Rosen where I came across the following algorithm of the Insertion Sort and also its analysis. The algorithm is quite ...
58 views

### How to wiggle sort an array in linear time complexity?

The wiggle sort is nums < nums > nums < nums > nums ... For an input: nums = [1, 5, 1, 1, 6, 4], the expected output is ...
96 views

### Is it possible to sort a linked list without copying its values but linking the nodes?

Is there an algorithm I could use when copying the values is not allowed? My list is going to be sorted in an ascending order. Also can this be done in a quadratic time? I will be attempting this in ...
29 views

### Merge $k$-sorted arrays - without heaps/AVL tree in $O(n\log(k))$?

Given $k$-sorted arrays in ascending order, is it possible to merge all $k$ arrays to a single sorted array in $O(n\log(k))$ time where $n$ denotes all the elements combined. The question is ...
315k views

### Why is quicksort better than other sorting algorithms in practice?

In a standard algorithms course we are taught that quicksort is $O(n \log n)$ on average and $O(n^2)$ in the worst case. At the same time, other sorting algorithms are studied which are $O(n \log n)$ ...
12 views

### Analysis of Radix sort of $n$ $b$ bit numbers

I was reading radix sort in Introduction to Algorithms by CLRS . And it gave the following Lemma with its analysis I understood the proof of the Lemma but confused on the part where they try to ...
101 views

### Sort array of duplicate integers in place

Given an array of integers within [1, n] where n = size of array, some elements may appear more than once. Could we sort it with just 1 extra space and in O(n) time?
18 views

### Sorting with high-latency compare

My basic setup is very simple: I'm trying to sort N items now, and later on I'll need to incrementally sort more items. The unique part of the problem is that my item comparison is not a computational ...
27 views

### Radix sort slower than Quick sort?

I would like to demonstrate that sometime radix-sort is better than quick-sort. In this example I am using the program below: ...
431 views

### Can this “double pop” Heapsort variation speed up sorting on average?

For classic Heapsort (in this example using a maxheap), only the root node is extracted (popped) at each iteration and the last element in the heap is swapped into its place and then the tree is "re-...
18 views

### How to represent a recurrence that increments by one at each tree level?

I am using a merge sort like algorithm. Each level of the tree has a different Big O runtime. The runtime as a whole can be represent as follows: $$O(\sum_{i=0}^{log(n)}2^{\frac{n}{2^i}} * 2^i)$$ I ...
38 views

### Runtime of Divide and Conquer Flavored Bogo Sort

Here we propose a way to reduce Bogo Sort's runtime from factorial to exponential using a divide and conquer approach. This is something we have likely all pondered on extensively. https://en....
37 views

### Analysis of Pan-cake sorting

i was implementing pan-cake sorting. We can implement it by taking largest element to start and flipping it recursively (Like selection sort). However it is mentioned that the A[i] has to be a ...
25 views

### “Low-High” sort divide and conquer with merge… how small to make the subproblems for good efficiency?

For a mental exercise, I decided to try out my own simple sorting algorithm which processes an array of integers in any order, and as it passes thru them all, records the highest and the lowest. So ...
109 views

### Doest sorting accept a dynamic programming solution?

Are there any known / efficient dynamic programming solutions to sorting? I understand of course that dynamic programming applies to scenarios where we have overlapping subproblems and optimal ...
213 views

### Can I make last part of counting sort become to be starting from lowest index?

Counting sort is originally like below code. ...
20k views

### Least number of comparisons needed to sort (order) 5 elements

Find the least number of comparisons needed to sort (order) five elements and devise an algorithm that sorts these elements using this number of comparisons. Solution: There are 5! = 120 possible ...
19 views

### How can divide by 2 blocksize bubblesort followed by a final mergesort be optimized in a particular environment?

I am wondering if we had a large array to sort (let's say 1,048,576 random integers), chosen because it is a perfect power of 2, if we can just keep dividing those blocks into smaller and smaller half ...
101 views

### Algorithm to identify top $\log n$ elements in $O(n)$ time

Airlines has a new policy to give a first-class upgrade coupon to their customers based on the number of miles accumulated. They decided to give it to their top $\log(n)$ frequent flyers, where n is ...
17 views

### Quicksort with lomuto partition - how many repeating elements are too many?

I know that quicksort with Lomuto's partition method faces worst case run-time $\Theta(n^2)$ when there are many repeating elements in the array. However, I'm trying to figure out - how many ...
76 views

### Understanding how quicksort operates

I am having a hard time understanding the quick sort partition operation. I understand what partition is supposed to do, I just don't understand how partition does it. Specifically, I don't understand ...
174 views

### Pancake Sorting Graph Recursive Definition

I'm having trouble understanding exactly how the graph for Pn (where n = number of pancakes) is defined recursively for n>= 4. I can see obviously that, in the case of n=4, there will be 4 rough ...
45 views

### Interval sorting that avoids covering

I have a collection of intervals and I want to sort them so that the order is interpreted as a sort of "z-index". That is, a given interval may or may not be "visible" depending on whether the merge ...
56 views

### Quick Sort vs Radix Sort

In an coding exam, I was once asked this question: Assuming that you are only sorting Integers in ascending order, which algorithm do you use when you want to prioritize speed the most, but you ...
54 views

### Improve algorithmic complexity

We have an array of N size. We have to perform Q queries on it, in which each Query contains and Index I for which we do: ...
40 views

### Need help analyzing the runtime analysis of this algorithm/algorithms in general

This is the algorithm I was trying to find the runtime of (doSomething) - ...
60 views

### Question about how can i determine if counting sort is the right option over other sorting algorithms

So, an exam's exercise asks me to find an alghoritm that can determine if counting sort is the best solution, otherwise use another optimal sorting algorithm. Now i find that solutions for that ...
67 views