# Questions tagged [sorting]

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

133 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
910 views

### Complexity of Sorting Integers on a Multitape Turing Machine

How expensive is sorting integers on a Multitape Turing Machine? Well known sorting algorithms, like quicksort, tend to rely on jumping / indirect-access being cheap. But MTMs have no indirect access.....
474 views

### What is the average-case running time of Fun-sort?

I read this paper: http://www.sciencedirect.com/science/article/pii/S0166218X04001131?np=y (you can check the PDF online for free), and I translated section 4's Fun-sort algorithm (correct me if I'm ...
167 views

### Sort 2D arrays so that cost of reaching new position as described at each iteration is minimized

Problem is as following: We are 8 trumpet players in an orchestra. There are for example 4 parts so there are always two players on the same part. Now, there are not always the same two players ...
44 views

936 views

### How to prove stability of sorting algorithms?

I know to prove instability, we can simply provide a counter-example. But is there a general way to prove that a sorting algorithm is stable? Could you please tell a general method and then show an ...
43 views

### Element-wise merging and re-sorting lists of sorted elements

Imagine you have a vector of pairs $(id, x)$ where $id \in I$, some set of opaque identifiers (hereafter, ids), and $x \in \mathbb{N}$ some value. Assume that every $id$ value is unique in your list. ...
104 views

### Parallel bubble sorting on arbitrary graphs

Are there bubblesort-esque algorithms for sorting on arbitrary graphs? I'm working on a problem in which $k$ robots are placed randomly on a graph and have to reach their respective goals as quickly ...
1k views

### Find the median of two sorted arrays of different size in O(min(log(n),log(m)) complexity

Given two sorted arrays of length m,n, how do I find the median of the union of these two arrays in O(min(log(n),log(m)) time? I've been trying to come up with an algorithm (and a proof) for several ...
68 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: ...
99 views

### Minimum number of comparisons to sort k elements among n

In The Art of Computer Programming D. Knuth, in section 5.3.3 Minimum Comparison Selection defines : $V_t(n)$ as the minimum number of comparisons needed to find the $t^{th}$ largest element of $n$ ...
75 views

### Optimal ordering of items with contradictory constraints

I've got a set of items that I'd like to sort into a list. The items have two independent sets of constraints that the ordering should respect: A set of hard constraints that must be satisfied, e.g.: ...
144 views

### How to find the top k pairwise product of in an array of integers?

Input: An array $a$ of integers $[a_{1}, \cdots, a_{n}]$, and a positive integer $k$. Output: The the top-k products of pairs in $a$. Example: $a = [7,6,5,4,3,2,1],k=3$ , output $(42,35,30)$, with ...
229 views

### Time complexity of obtaining the set of distinct elements in a sequence?

Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we can read, write and compare them in O(1) time with arbitrary positions). What's known ...
546 views

### How to sort an array $A[1..n]$ with $\sqrt n$ distinct elements in $\Theta(n)$ time and $\Theta(\sqrt n)$ space?

I need to write an algorithm which will sort an array $A[1..n]$ with $\sqrt n$ distinct elements in $\Theta(n)$ time and $\Theta(\sqrt n)$ space? The solution must use hash-tables and advanced data ...
178 views

### Find a sorting procedure for seven elements that minimises the average number of comparisons performed

In The Art Of Computer Programming, Volume 3, Chapter 5.3.1, Problem 26, Knuth asks one to construct a sorting method that achieves the minimum number of average comparisons for n=7. This means that ...
59 views

### Is there a known worst start configuration for Ford-Johnson sorting algorithm?

By this I mean a permutation of the $n$ input items to be sorted such that the number of comparisons taken to produce the correct order is maximal over all of the possible permutations of $n$ items. ...
128 views

### Sorting with gaps

Suppose we have a directory containing $N$ files whose names are numerals, but not necessarily contiguous numerals. Let's say for concreteness that each file contains an email message, each of which ...
5k views

### Best case analysis for Shell sort

The exercises in a textbook I studied asks about the best case for Shell sort. I have scribbled a derivation for the same along the margins almost two years ago. Basically I don't know if this was my ...
18 views

### approximate line segments from array of unsorted points

The polygon above is actually a collection of a lot of black points closely packed together. I want to approximate these black points as straight line segments. The black points are not sorted in any ...
68 views

### Hypothetical Situation for sorting in $O(n)$ using median finding machine that works in $O(\sqrt{n})$

In a hypothetical world, we have a machine that can find median of $n$ numbers in $O(\sqrt{n})$. (Of course this machine is not real). Can we use this machine to sort an array in $O(n)$? I don'...
21 views

### Sorting using k stacks with operation poppush(original stack, adjacent other stack)

I've been trying to read about sorting algorithms on stacks optimizing the amount of push and pops. One of a number of related probems I'm interested in can be formalized like that: There is a set of ...
69 views

### Goemans' Extended Formulation of the Permutahedron And Comparator Networks that are not Sorting Networks

I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are not sorting networks. In his paper "Smallest Compact ...
57 views

### A binning (sorting) algorithm

Rules: A conveyor belt is giving you little boxes. They are labeled for your convenience: Box $1$, Box $2$,... For your inconvenience, though, you can't see the number (from $1...n$) hidden in it. You ...
282 views

### Worst case for linear-time k'th smallest element algorithm?

There's an algorithm for finding the k'th smallest element in an unsorted array similar to quickselect: kthSmallest(arr[0..n-1], k) 1) Divide arr[] into ⌈n/5⌉ groups where size of each group is ...
64 views

### Sort arrays $A$ and $B$ of the same elements using only comparisons between an element of $A$ and one of $B$

Premise: Let $A := [ k(1), k(2), ..., k(n) ]$ and $B:=[ l(1), l(2), ..., l(n) ]$ be two Arrays where $k$ and $l$ are permutations. (What I'm trying to express: $A$ and $B$ contain the same elements in ...
39 views

### Algorithms / heuristics for a distributed sorting problem

The setting: There's a cluster of $k$ computers (= nodes). For simplicity, assume their hardware is identical. The network topology can be complicated, but let's simplify and assume it's a clique ...
52 views

556 views

### Quick Select explanation

I have been looking for a quick and easy explanation on Quick Select and stumbled upon this. It's quick and easy to follow, but there's a part which I am not following quite well: The uploader is ...
3k views

### Insertion sort Proof by Induction

I am reading Algorithm design manual by Skiena. It gives proof of Insertion sort by Induction. I am giving the proof described in the below. Consider the correctness of insertion sort, which we ...
645 views

### Why does Shellsort work well on Sorted and Reverse ordered lists?

I've ran some tests and found that Shellsort runs much faster on ordered and reversed lists compared to random lists and almost ordered lists. ...
17 views

### Looking for a subjective ranking algorithm

I'm interested in learning about ranking algorithms that sort items based on preference. For example: If a person was food taster/judge and had 10 small bowls of chili that they had to rank in order ...
29 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 ...