Questions tagged [sorting]
the algorithmic problem of ordering a set of elements with respect to some ordering relation.
933
questions
0
votes
0
answers
11
views
Relation between running time of Insertion sort and number of inversions
What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.
Consider Insertion sort
...
- 1
1
vote
1
answer
47
views
Prove maximum score is achieved by being greedy
I have a list of tokens T, of length n. Initially I have power p and a ...
- 284
3
votes
2
answers
31
views
What is the Time Complexity of Least Topological Ordering?
I knew the time complexity of Topological ordering is O(V+E) since we don't need to do sorting during the selection of node whose incoming degree is 0. But what about the least topological ordering ...
- 31
0
votes
1
answer
24
views
Is this bayesian average calculation right?
I have asked it already on math.stackexchange.com and stackoverflow.com but they said it was off-topic and could not help me. They pointed me to cs.stackexchange.com so hopefully somebody here can ...
- 101
0
votes
1
answer
37
views
Selection sort on the array $\{5,9,11,10,2\}$
I want to understand how the algorithm of selection sort sorts the given array,
$$A[5]=\{5,9,11,10,2\}$$
Step -$1:-$
I compare A[0] with remaining elements of the array and since $A[4]<A[0]$ I swap ...
- 109
1
vote
0
answers
43
views
Bottom-up well-balanced mergesort
If you implement mergesort top-down you can always split the input of length $n$ into one of length $\lfloor n / 2\rfloor$ and one of length $\lceil n / 2 \rceil$. This ensures that all merges are ...
- 13.4k
0
votes
2
answers
56
views
Correctness proof of bubble sort(bogus proof)
I am aware of bubble sort correctness proof. But what is wrong with following argument while using induction.
Proof: Assume correctness of array size $1$ and $n$ (base and hypothesis). Then for ...
- 43
0
votes
0
answers
33
views
given a list of 3 dimension what is the best approach to find the highest sum
We are given a file of three columns
- the first is player name
- the second is game item name
- the third is the price of the game item when bought by the player
items may repeat for the same player ...
- 101
0
votes
2
answers
92
views
Is it possible to sort numbers in linear time and constant extra space?
The programming language is C++, and the elements of the input vector are of type int and able to take all valid ...
- 960
2
votes
5
answers
2k
views
Isn't counting sort a better sorting algorithm for linked lists rather than merge sort?
I have to analyze how every sorting algorithm's complexity would change if it had to sort a linked list and which of all of them is the most efficient. I find everywhere that merge sort is the most ...
- 73
1
vote
0
answers
111
views
How many comparative sorting algorithms are there?
I've invented an abstract structure to represent a comparison-based sorting algorithm, which I will call a comparison tree (similar to the decision tree of a comparative sorting algorithm). ...
- 51
2
votes
1
answer
71
views
Sorting with element merging
I'm seeking information about a specific sorting algorithm. This algorithm performs pairwise comparisons and distinguishes between three states:
a > b: In this case, standard sorting logic proceeds ...
- 121
1
vote
0
answers
36
views
Performance considerations of index maps for rearranging a vector
Imagine two vectors $V=[v_1, v_2, \ldots, v_n]$, $S=[s_1, s_2, \ldots, s_n]$ where $S$ is a rearrangement of $V$ based on some relation $\leq$. Imagine that, instead of computing $S$ using as input $V$...
- 529
2
votes
0
answers
91
views
How to sort an array A using an array S with the properties below
A is an array of size n of different numbers (not necessarily integers). Indexes start from $1$ to $n$.
S is an array with the property:
$$S[i] = |\left\{A[j] \ : 1\le j<i \ \text{and} \ A[j] \le ...
- 143
0
votes
0
answers
32
views
Sorting exams dividing the task between m teachers
I have to find 2 efficient ways to sort 1000 exams according to the students' last names and give the complexity. The task has to be divided between m teachers.
I think one efficient way is to give ...
- 73
1
vote
1
answer
106
views
Is there a [non-comparative] sorting algorithm, sorting an array in $o(n \log n)$?
We have shown that any comparative sorting algorithm has the worst-case complexity of $\Omega(\log (n!)) = \Omega(n \log n)$, as it has to cover all the ways a permutation can be, and according to the ...
- 51
3
votes
1
answer
47
views
Finding Specific Order Statistics with O(n log(n/k)) Complexity
I'm working on a problem where I need to find specific order statistics in a set of numbers. Given n numbers, I want to determine the ...
- 133
0
votes
0
answers
49
views
Insertion sort - how it works
This is the pseudocode for insertion sort.
My question is this: suppose I have the array [5,2,4,6,1,3].
key = 2 and i = 1. Then A[i+1] = A[i] is A[2] = A(1) = 5. So now isn't the new array [5,5,4,6,1,...
2
votes
0
answers
49
views
The Festival-Clique-Sorting Problem
The following is a real world problem, for which I adjusted the explanation, such that it is easier to understand.
In a very abstract form, the challenge is to find a group-sorting algorithm, that is ...
- 21
-1
votes
2
answers
61
views
At what case/problem, Binary Insertion Sort would be faster than Insertion Sort?
We know Insertion Sort would be faster than Merge Sort and Quick Sort for nearly sorted data. What about Binary Insertion Sort? At what case is it better than Insertion Sort?
Also, is there a better ...
- 3
0
votes
0
answers
23
views
maximum step of sorting network
How to calculate the maximum step of sorting network?
Based on image below, it has most comparators at second index which is 9 comparators than another indices. That's mean, overall networks need 9 ...
3
votes
0
answers
146
views
Recover unknown vector through shifted argmax queries
I am interested in finding an efficient algorithm for the following problem:
Let $x \in [0,1]^n$ be some vector, with $x_n = 1$.
We want to recover $x$, solely by asking queries of the form $\texttt{...
1
vote
1
answer
87
views
Sorting rational numbers in linear time
I am currently studying algorithms and computational complexity at University.
I have recently got through three questions I found in an old exam:
Is it possible to sort in asymptotically linear time ...
- 11
0
votes
0
answers
21
views
Minimal pairwise comparisons to combine multiple binary trees that are only relatively sorted?
I'm intending on writing a program to let my friends make pairwise comparisons of computer generated images, ranking them. I'm mostly doing this for fun and to do some learning and I picked computer ...
- 420
2
votes
1
answer
52
views
Randomizing pairing in "gift swawp"
The problem
I'm arranging a "gift swap" for Christmas with N people involved (N > 2).
I want to create an algorithm that generate the pairing gifter->giftee so that:
everyone receives ...
- 123
1
vote
0
answers
38
views
Algorithm for grouping set items into ordered buckets without crossing boundaries between same set items
I'm trying to order some data in real-time (in an API call) where my item count is on the order of a few million.
I'm using Go, so my pseudo code may resemble that. My input items look like this:
<...
- 111
1
vote
1
answer
95
views
Diffucuty in understanding code after a recursive call
This is an example algorithm of a recursive insertion sort I'm trying to understand. I've have tried understanding this with
the help of print statements (which I've commented).
...
- 11
1
vote
1
answer
47
views
Understanding crossover points in efficiency between insertion and merge sorts
Self-taught programmer here. I'm reading CORS, and right at the beginning, question 1.2-2, there asks a question:
For inputs of size $n$, insertion sort runs in $8n^2$ steps, which merge sort runs in ...
- 113
1
vote
1
answer
39
views
Schoolclass Optimization Algorithm for finding Stable Matching
I have the task to write a program that puts students in classes and that in the best possible way.
We have given the name, the foreign language a student chooses(french or latin), a profile (Music,...
- 13
0
votes
0
answers
65
views
Hoare's partition original method
So I was reading the Hoare's partition part of the Quicksort wiki and it says:
"With respect to this original description, implementations often make minor but important variations. Notably, the ...
0
votes
0
answers
24
views
Subtrees of decision tree for comparison sort are recurrences?
Consider sorting on $n$ distinct elements, where all $n!$ permutations are possible. I think a decision tree for comparison sort can can be uniquely characterized as $T(a,n!)$ where $a$ is the ...
- 149
4
votes
2
answers
85
views
Looking for efficient algorithm to pick out a unique equivalence class representative for 2D arrays with lots of symmetries
Given 2D arrays (number of rows between 0 and 10, number of columns between 0 and 10, elements are integers between 0 and 31)
Two arrays $A,B$ are equivalent $A\sim B$ if $A$ can be transformed into $...
- 73
0
votes
0
answers
59
views
Efficient way of exploiting many symmetries
I have a problem domain that has several kinds of symmetries. I will try to keep this as general as possible. Given an array of strings:
["4533", "1234", ...]
The two symmetries ...
- 73
0
votes
0
answers
23
views
Is there any sorting algorithm that can generate all the sets of notes?
As we can visualize and listen to a sorting algorithm sorting an array, does exist an algorithm that can generate any set of notes? More precisely, does exist a sorting algorithm so that exists a ...
- 51
1
vote
0
answers
15
views
Correlation between branchless algorithm length (Assembly) and its latency
I have recently reviewed the new article by DeepMind (Google) in Nature named "Faster sorting algorithms discovered using deep reinforcement learning". They claim that branchless algorithms, ...
- 111
1
vote
2
answers
140
views
Is there an upper bound on the number of different sorting algorithms
Is there a proven upper bound on the number of possible sorting algorithms that cannot be reduced to another sorting algorithm?
Sorting algorithms with "useless steps" wouldn't count because ...
- 111
7
votes
6
answers
4k
views
How AlphaDev improved sorting algorithms?
On the 7th of June 2023, Google DeepMind released an article about AlphaDev. AlphaDev is an evolution of AlphaZero (used to beat world champions at Go, Chess and Shogi), and it can produce assembly ...
- 81
4
votes
0
answers
137
views
Comparison-based computation: percentage of current software development?
Vol. III of The Art of Computer Programming, chapter 5 (Sorting, intro) mentions:
Computer manufacturers of the 1960s estimated that more than 25
percent of the running time on their computers was ...
- 602
0
votes
1
answer
63
views
How does merge sort decide how to merge an array?
So, the way I understand merge sort: We split an array into two halves, then we split those halves into halves, etc. until we get arrays that can be split no further. We kind of build up a tree in the ...
- 185
1
vote
0
answers
43
views
1
vote
0
answers
30
views
Shell algorithm knuth sequence time complexity analysis
Given this shell sort algorithm implementation:
...
- 21
2
votes
1
answer
92
views
Efficient way to calculate many Dutch auctions?
I have 4,500 ($N$) unique items, and I want to auction each one off to the highest bidder (break ties arbitrarily).
Each item has $T$ binary traits. Since it is too complex for the $B$ bidders to ...
- 141
0
votes
0
answers
37
views
Trouble understanding inductive proof of Lomuto's partitioning algorithm
I'm doing a review of sorting algorithms and trying to self-learn how to prove them as well. The foundation of the quicksort proof is intuitive enough if I'm assuming that the recursion holds - but ...
- 1
1
vote
2
answers
94
views
Given an array of size $n$, return a sorted array of floor($n^k$) elements for some $k<1$
We are given an array of size $n$ (it is not specified if we have an integer array, a specific range or any other assumptions), which might be unsorted, and a real number as a
constant $k<1$. We ...
0
votes
2
answers
87
views
Bucket sort for gaussian / standard distribution
I know this post. But I still have no idea to adapt the bucket sort algorithm to handle input with a gaussian / normal distribution. Can someone provide me a Pseudocode / Python code for that? So far ...
- 121
0
votes
0
answers
31
views
Ask for an algorithm for sub-ordering a sub-array of an already sorted super-array
Suppose I have already sorted an array $a$ of length $N$, each element having its position index into the sorted result recorded together with the element. Now I randomly sampled a sub-array $b$ of ...
- 1
1
vote
0
answers
89
views
Algorithm: sorting a set of numbers based on a "score matrix"
I have a list of $n$ items, where each item gives a score to every other item, so I get a $n\times n$ square matrix $M$ of scores. Each score is a natural number. Items also score themselves. Example ...
- 529
2
votes
1
answer
88
views
Algorithms for sorting under some restrictions
I was recently sorting a large list of names - I just ended up sorting it in Python, but it inspired in me the following question. If we're given a list $L$ of $n$ numbers, but can only see $k$ ...
- 121
1
vote
1
answer
59
views
Optimal worse-case sorting algorithm when some comparisons are cheap
I want to sort a set of items, where some comparisons are expensive and others are cheap. What is an algorithm that will minimize the worse-case number of expensive comparisons?
For instance, I want ...
- 113
-2
votes
1
answer
116
views
How do I make a stable sorting algorithm that uses an unstable algorithm as a subroutine
The stable algorithm has to run in O(n) time and must call the following unstable algorithm at least once.
EDIT: Calling unstablesort() is free (costs 0 operations).
...
