Questions tagged [sorting]
the algorithmic problem of ordering a set of elements with respect to some ordering relation.
961 questions
0
votes
0
answers
29
views
Implement bubble sort with limited memory elements
Suppose you have elements (a,b,c,d), and you want to use bubble sort to sort them(either ascending or descending,doesnt really matter), but you can only use a single memory stack (with infinite ...
- 141
1
vote
1
answer
106
views
Prove optimality of a sorting algorithm
I'm working on proving a greedy solution to the problem in Codeforces 205B, which states:
Given an array of integers a of length ...
0
votes
1
answer
72
views
You are given two unsorted lists $R$ and $C$ of possibly different sizes containing elements from the same universe. Find a Balancing Split
For any value $v$, the list $L$ is split into two sublists $L_{low}$ and $L_{high}$.
$L_{low}$ has all values in $L$ which are less than or equal to $v$.
$L_{high}=L-L_{low}$.
The balancing split is ...
- 118
1
vote
1
answer
112
views
Lower Bound on Sorting an Array Where Elements Are at Most $\sqrt{n}$ Positions from Their Sorted Position
Let $A[1 \ldots n]$ be an array of $n$ elements, such that each element is at most $\sqrt{n}$ positions away from its position in the fully sorted array. That is, for every element $A[i]$, its ...
- 385
2
votes
0
answers
89
views
How to generate a minimal sequence of lazy pair swaps to cover all N! combinations of a list of N-elements?
I'm trying to find a method to quickly generate all index-pair sequences for the following problem:
Given a sequence of N elements, find the shortest sequence of lazy pair swaps (i, j) — where each (...
- 21
2
votes
1
answer
95
views
Is finding minimum total flip cost equivalent to finding minimum flips in pancake sorting problem?
Flip cost: the number of pancakes that was flipped during one flip.
Total flip cost: the sum of the flip cost during the pancake sorting process.
Minimum total flip cost: the smallest total flip cost ...
- 21
0
votes
1
answer
66
views
What is the worst-case time complexity for sorting within a range?
Suppose I have numerical data that's certain to be within a particular range: say, integers between 0 and 100. I know radix sort can be used to sort them faster than $O(n \log n)$: sort them first by ...
- 7,216
2
votes
1
answer
112
views
Sorting: worst-case time complexity best upper bound (Challenge)
Assuming a model of like multitape TM, (meaning do not assume O(1) time for operations or anything). Informally, what is the best known algorithm worstcase-wise (as a function of the input) for ...
- 123
0
votes
0
answers
48
views
Characterization of all comparison sorting algorithms
In analogy to group theory, where all finite groups have been characterized, can we do something similar for comparison sorting algorithms (CSAs).
Maybe we first need a way to define isomorphism ...
- 101
1
vote
1
answer
88
views
Calculate ordering index of an alphabet from a differenct ordering index
I am trying to describe this question in an intuitive manner.
Say we have an alphabet A consisting of three symbols: A={a,b,c} ...
- 111
0
votes
0
answers
75
views
timsort + powersort
I've been trying to implement timsort with the powersort merging strategy.
The problem I'm having is that I can't figure out how the conditions required by merge_hi and merge_lo is upheld even when ...
2
votes
3
answers
140
views
Can comparison sorts be implemented with an opaque compare-and-swap operation?
The standard library sorting functions I'm familiar with in C and Java accept a user-defined comparator, which takes two elements a and b and returns a <=> b, ...
- 123
0
votes
0
answers
49
views
What is the name of the "Egyszerű cserés rendezés" sorting algorithm in English?
In some Hungarian sources about sorting algorithms one can come across the following pseudocode:
...
- 101
0
votes
0
answers
40
views
Ranked voting method that accounts for the sample size of a particular comparison?
If there are 2 competing products on Amazon, and one has an average rating of 4.5 (by 2 people) and one has an average rating of 4.49 (by 10000 people), I'll obviously choose the second product with ...
- 652
1
vote
0
answers
75
views
Transforming a sorted array into a maximally unsorted circular buffer
If I have a sorted array, e.g.
['A', 'A', 'A', 'B', 'B', 'B', 'B', 'B', 'C', 'C']
Is there an algorithm for turning this into:
...
- 111