Questions tagged [sorting]
the algorithmic problem of ordering a set of elements with respect to some ordering relation.
908
questions
1
vote
0
answers
23
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
0
answers
44
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
27
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
31
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
31
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
17
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 ...
- 129
4
votes
2
answers
77
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 $...
- 43
0
votes
0
answers
58
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 ...
- 43
0
votes
0
answers
20
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 ...
- 11
1
vote
0
answers
13
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
121
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
3k
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 ...
- 590
0
votes
1
answer
48
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
0
votes
0
answers
25
views
0
votes
0
answers
22
views
Shell algorithm knuth sequence time complexity analysis
Given this shell sort algorithm implementation:
...
- 1
1
vote
1
answer
40
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 ...
- 131
0
votes
0
answers
24
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
92
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
63
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
86
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 ...
- 457
2
votes
1
answer
78
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
57
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
102
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).
...
0
votes
3
answers
155
views
Sorting Numbers in O(N)?
Why is sorting numbers Omega(nlogn)? I'm thinking of an reduction algorithm where:
For all the numbers x_i, we create a point (x_i, 0) on a 2d graph.
Fit a line directly to the right starting from ...
-4
votes
2
answers
55
views
Design and analyze an efficient algorithm that, given n distinct integers, returns an element which is neither the smallest nor the largest
I'm trying to prepare for mock exam, could you please help me with possible solutions?
Design and analyze an efficient algorithm that, given n distinct integers, returns
an element which is neither ...
- 1
0
votes
1
answer
23
views
Ranked voting method where unranked candidates on a preference list aren't taken to be the least preferred?
Say there are 5 candidates, A, B, C, D, and E. An election is held using a ranked voting method. That is to say, each voter submits a preference list (the order in which they prefer candidates). E.g. ...
- 512
0
votes
0
answers
38
views
Is there a sorting program or formula to sort and place individuals in classes based on preferences
I am looking for a formula or program to help place people in classes based on their preferences.
The elements of the problem are:
There are 30 class choices a student can pick from.
There are 400 ...
- 1
0
votes
2
answers
58
views
merging logn + 1 sorted subarrays
given array A of size $n$ which is made of $logn + 1$ sub arrays which are sorted,
I need to sort ASAP.
example of array : $A[500,501,3,8,100,1,2,9]$ as you can see, sub arrays are :$[1:2][3:5][6:]$
...
- 11
0
votes
1
answer
59
views
Algorithm to find minimum amount of swaps to convert array A into array B with repeated elements
I'm trying to create an algorithm that finds the minimum number of swaps to convert array A into array B. In this case the arrays can only contain the numbers 0, 1 or 2.
So for example: given ...
- 25
0
votes
1
answer
51
views
Telling unique values in a short array
I have thousands of short arrays (length less than 9) holding integers. These numbers can be identical with high probability (in many arrays there are two triples of equal numbers). I need to remove ...
user16034
-1
votes
1
answer
33
views
0
votes
1
answer
33
views
Shell's Increments Worst Case Analysis
My textbook claims the worst-case running time of Shellsort with Shell's increments is $Ω(N^2)$, but this analysis is done when $N = 2^m$ for a positive integer $m$. I see why the proof would work for ...
0
votes
0
answers
71
views
Range updates in segment trees of sorted arrays (merge sort trees)
I understand range updates in segment trees using lazy propagation where each node is an integer.
Merge Sort Tree (source GFG): https://media.geeksforgeeks.org/wp-content/uploads/20220722205737/...
- 139
0
votes
1
answer
163
views
Is this sorting problem NP-complete?
Consider array $A=(a_1,a_2,...,a_n)$ such that $a_i$s are positive integers. Moreover, we have $k$ binary tuples, each with length $n$. In each iteration, we choose one of those tuples, and decrease ...
-1
votes
2
answers
82
views
Is the bubble sort algorithm more efficient for sorting and how to implement it?
I don't know which algorithm is more efficient for sorting, but I want to use Bubble sort and how to implement this algorithm.
- 3
-2
votes
2
answers
200
views
Modified Bubble Sort's time complexity
I have an array (of hundreds of numbers) and I need to sort them. In this case, I used Bubble Sort because of the better time complexity compared to other algorithms, $\Theta(n^2)$.
...
- 3
-2
votes
1
answer
56
views
Is there an algorithm that can get the minimal element of a min-heap in O(log* n)?
I came across this question when studying for an exam:
given a min-heap that has no prime numbers in it, is there an algorithm that can get and delete the minimum of that heap in O(log* n) ?
The ...
- 1
1
vote
1
answer
134
views
Sorting a collection of tuples using merge rearrangements
Given a collection of tuples $X=\{(x_1,y_1),\dots,(x_n,y_n)\}$, where elements
$x_i, y_i \in R_{\geq 0}$ are non-negative real values. The collection $X$ is
sorted if $x_i \leq x_{i+1}$ and $y_i \leq ...
- 123
2
votes
1
answer
43
views
minimum number of 2d elements whose sums across both dimensions satisfy some threshold
I have the following problem formulated as a linear integer program:
\begin{align}
& \text{minimize} && \sum_{i \in n} x_i\\
& \text{subject to} && \sum_{i \in n}{a_i}x_i \ge ...
1
vote
0
answers
26
views
Quicksort sampling
This question is in the context of quicksort. Consider that a subarray of distinct elements of size $k$ is sampled from the input array of size $n$, and then we choose a pivot from the sampled ...
- 71
0
votes
3
answers
215
views
Sort doubly linked list with just manipulating pointers
Given doubly linked list $L$ that contains $n$ elements of numbers. Between QuickSort, and MergeSort and InsertionSort, which algorithm preferred to sorting $L$ by just swapping links of $L$?
I think ...
- 1,554
0
votes
1
answer
18
views
Algorithm to find best order for items on pages with a fixed height
I am looking for an algorithm to find the best order of items to fit on pages.
Consider the following case, we have a page with the height = 300
We have images with the following heights - [150,200,...
0
votes
1
answer
23
views
Algorithm to alternaly order elements in a list
So, I have N sets of objects of various sizes.
I want to put them in order, in a way that's as much "alternative" as possible.
For example, if I have 5 A, and 6 b, that's easy:
B A B A B A B ...
0
votes
2
answers
37
views
Compare list of parameters with each other and sort them from most to least selected
I want to sort the list of parameters (p1, p2, p3, p4, ..., pn) according to their importance.
All parameters have to be compared with each other at best once, but not less than once.
The person will ...
0
votes
0
answers
31
views
Maximum Accumulated Balance after Purchasing Machines
A company is able to earn x dollars per day without any machines. However, there are n machines available for purchase. The <...
- 11
0
votes
0
answers
82
views
Analysis of randomized algorithms
The expected running time, $T(n)$, of quicksort when the pivot is chosen uniformly at random satisfies $$ T(n) \leq \mathcal O(n) +\frac{1}{n}\sum^{n-1}_{i=0}(T(i) + T(n - i)),$$
which leads to the ...
- 257
0
votes
3
answers
237
views
Can we create a decision tree for any comparison sorting algorithm even if it is very complicated?
I am reading an algorithm book.
Any comparison sort must make $\Omega(n\log(n))$ comparisons in the worst case to sort $n$ elements.
Can we create a decision tree for any comparison sorting algorithm ...
- 113
0
votes
2
answers
239
views
Time complexity of sorting binary natural numbers
In the comparison sort model of sorting, the fastest possible algorithm is order $n \log(n)$, where $n$ is the number of input numbers. What is the time complexity of sorting a list of natural numbers,...
- 189