Questions tagged [sorting]
For questions about dividing groups of objects based on their properties.
367 questions
8
votes
1
answer
191
views
What is the minimum number of moves required to "sort" an $N$-element list?
Suppose that we are given an ordered list $L_0$ of $N$ arbitrarily permuted, totally ordered elements. Our goal is to "sort" the elements into either ascending or descending order (both ...
- 1,040
0
votes
1
answer
96
views
Trouble understanding quicksort O(nlogn) proof
I have trouble understanding this proof for quicksort: The goal is to bound the overall number of comparisons performed by the algorithm. Consider an array $A$ with elements $z_1, z_2, ..., z_n$ with $...
- 3
1
vote
1
answer
106
views
Time complexity of bogo-selection sort
Just out of curiosity, I have created a sorting algorithm that is a mix between bogosort and selection sort. It operates as follows:
Initialise $x$ to 1. This will count the number of sorted elements....
- 113
1
vote
1
answer
151
views
Exact Triangle Sorting for Orthographic Rendering of a Triangulated Surface
I want a definitive front-to-back triangle drawing order under orthographic projection.
This is an X-post due to inactivity on the other: https://tex.stackexchange.com/q/735053/319072
Note: I have ...
- 267
0
votes
2
answers
151
views
Average-case analysis of Insertion-sort, & of binary-search based version.
The analysis for the average-case of Insertion-sort, is given here, with C-implementation.
It states the chance for the $i-$th insertion, requiring $0, 1, 2,\cdots, i-1$ comparisons is equal, and is ...
- 4,972
0
votes
0
answers
86
views
How to prove the correctness of a sorting program using Hoare logic?
I am working on a problem where I need to analyze a small sorting program using Hoare logic to formally verify its correctness. Here's the program:
...
- 17
2
votes
1
answer
66
views
Does a topological sorting algorithm exist, that is stable on induced subgraphs
I now that topological orderings are not unique.
But I wonder whether are exists an algorithm that sorts DAG nodes by topological order and is stable on induced subgraphs.
What I means by that is that ...
- 201
0
votes
1
answer
65
views
Are a fixed amount of pairs sufficient to output any permutation here?
Let $T$ be any finite set such that for any $2$ elements $a \in T$ and $b \in T$, either $a<b$ or $b>a$. Say we have some sort of a collection $C$ with a notion of order, such as a list, which ...
- 3,162
2
votes
0
answers
31
views
Extending Quicksort's $\mathcal{O}(n \lg n)$ Bound to Duplicated Elements
This is the final part of Problem 7-2 of CLRS' Introduction to Algorithms. The exercise asks to modify the argument given in the text so that the $\mathcal{O}(n \lg n)$ bound also applies to arrays $A$...
- 25k
1
vote
1
answer
59
views
The polynomial $ f_1 = -xy^2 z^2 + z^8 + 6x^3 y + 2y^4 z $ with variable order $ x > y > z $ should be sorted
The polynomial $ f_1 = -xy^2 z^2 + z^8 + 6x^3 y + 2y^4 z $ with variable order $ x > y > z $ should be sorted according to the various monomial orders LEX, DEGLEX, REVLEX and DEGRELEX.
My ...
user1348309
2
votes
1
answer
215
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
53
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,406
1
vote
1
answer
78
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
3
votes
0
answers
160
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
0
votes
1
answer
128
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