Questions tagged [sorting]
For questions about dividing groups of objects based on their properties.
361
questions
2
votes
1
answer
61
views
Arrange given numbers in a way such that the minimum absolute difference between any two consecutive numbers is maximized.
I've been doing some competitive programming practice on Codeforces recently, and I stumbled upon a problem here. The solution to this problem can be found here.
Now, what if the set of numbers wasn't ...
- 21
1
vote
0
answers
40
views
about the mathematics of sorting networks from computer science
Well, I had some searching about https://en.wikipedia.org/wiki/Sorting_network but it looks to me that all my findings focus on programming issues (in which I'm interested, too) but lack a clear ...
- 1,162
1
vote
1
answer
34
views
Is there any algorithm to calculate this ranking method quickly?
I want to rank the 20 teams in the English Premier League. Say that each team are assigned to the number 1 through 20, defining their ranking, no ties. There would be $20!$ number of permutations for ...
- 45
0
votes
1
answer
40
views
Is there a way for this to sort into a rectangle? Also, how would one compute this mathematically?
Is there a rigorous way to solve a problem like this. Also is there a solution to this exact case?
- 43
3
votes
0
answers
62
views
Sorting a permutation by sorting half of the elements at a time
The problem: suppose we have an array $p[1..n]$ (where $n$ is a multiple of 4) which initially contains some permutation of the numbers $\{1, 2, \ldots, n\}$. The only way we are allowed to modify ...
- 31
1
vote
0
answers
52
views
Complexity of a Sorting Problem
i investigate the following problem.
Given a set of tuples $(a_i, b_i), i=1\ldots,n$ with $a_i,b_i \in \mathbb{N}$, i want to order them into a sequence such that the sum of differences of endelements ...
- 19
0
votes
1
answer
35
views
Is there an algorithm for sorting points in a field based on sweeping a line through them at an arbitrary angle?
Given a set of coordinates on a euclidean plane, is it possible to sort the points by sweeping a line through them where the line might not be strictly horizontal or vertical? The inputs to the ...
- 3
0
votes
0
answers
43
views
Generating all possible rankings when merging sorted lists with rank instead of raw score information per element
Let $\{e_1, e_2, ..., e_n\}$ be the set of elements.
Let $\{s_1(e_1), s_1(e_2), ..., s_1(e_n)\}$, $\{s_2(e_1), s_2(e_2), ..., s_2(e_n)\}$ be the scores of elements after applying two ranking functions ...
- 161
1
vote
1
answer
52
views
Average number of required swaps in selection sort
Assume that the distinct integers 1,...,N are in random order and need to be
sorted using selection sort. Here I am interested in the average number of
swaps required, rather than the number of ...
- 93
1
vote
1
answer
167
views
Proving a property of the Selection sort algorithm
Consider running the Selection sort algorithm on a permutation $p$ of $n$ elements. Let $f(p)$ denote the number of times the 'running minimum' changes throughout the algorithm. Conjecture: $f(p)$ is ...
- 168
1
vote
1
answer
94
views
Sort rectangles by size, but with a tunable advantage favoring squareness
I want to sort some rectangles from biggest to smallest, but with a tunable advantage favoring squarer rectangles. I'm sure this is super easy but I'm not getting it. I think it's related to topics ...
- 63
1
vote
0
answers
22
views
Proof for Largest enclosed area of a random set of points in a 2 dimensional coordinate field [closed]
Consider a set of points randomly distributed on a $2$ dimensional coordinate plane. There should exist one solution in which each point is used once to create a shape defined by each point as a ...
- 11
31
votes
3
answers
3k
views
Is it possible to "sort" a continuous function?
I was motivated for this question while seeking for a new sorting algorithm.
Suppose a continuous function $f : [a, b] \to \mathbb{R}$ is given. I wanted to define the sorted version $g$ of $f$, which ...
- 2,049
0
votes
2
answers
51
views
Is $a\log_2(b) \le b\log_2(a)$ for all $a$ and $b$ given that $1 \le b \le a$?
I am trying to optimize the number of comparison in the merge sort algorithm, particularly during the merging step.
Is $a\log_2(b) \le b\log_2(a)$ for all $a$ and $b$ given that $1 \le b \le a$?
I ...
- 507
1
vote
1
answer
156
views
Expected length of Stalin-sorted sequence [closed]
There is a pogramming meme called Stalin sort which works as follows: the algorithm proceeds from left to right and each time it encounters a value $a_i$ less than the previous one $a_{i-1}$ the ...
- 57