Skip to main content

Questions tagged [sorting]

the algorithmic problem of ordering a set of elements with respect to some ordering relation.

Filter by
Sorted by
Tagged with
2 votes
2 answers
29 views

Minimal k-way comparison sorting algorithm?

I've watched 600 TV shows, and I want to sort them in order of how much I liked them. I'm bad at assigning absolute scores, but good at comparing relative enjoyment, so it has to be a comparison sort. ...
JentGent's user avatar
1 vote
1 answer
57 views

Algorithm to sort array into K increasing subsets?

Let's say we got an array of size n with real numbers, and a natural number k. n must be multiple of k. We want to sort the array in a way that, when we divide this array into k subsets of equal size, ...
user166586's user avatar
1 vote
1 answer
25 views

Is there a lower bound on space complexity of non-in-place sorting?

There is a well known result stating that any comparison-based sorting algorithm has a time complexity of at least O(n log n). Selection sort and merge sort are two common examples, with time ...
A. Darwin's user avatar
  • 123
4 votes
0 answers
55 views

Deterministic solution of "nuts and bolts" problem

How are the samples in "Matching nuts and bolts" paper in chapter two chosen deterministically to achieve $O(n^{1.5})$ complexity? I don't see how projective planes can help here.
Gh0st's user avatar
  • 41
0 votes
2 answers
72 views

Is it possible to sort this type of array in O(n) time?

Pseudo-Sorted array is an array that for every 0=<k<n the k smallest cell will be in the first 2k cells. For example the smallest cell will be in indexes 0-1 The second will be in indexes 0-3 ...
Itamar Adar's user avatar
2 votes
1 answer
49 views

Minimize cost for list of words given a list of letters

What is a general algorithm to reorder a list of letters such that it minimizes the cost for a fixed list of words? Algorithm input To be optimized a list of unique letters: ...
wjwrpoyob's user avatar
  • 141
1 vote
1 answer
117 views

Why is the number of array accesses not considered in analyzing the complexity of mergesort?

I'm reading Robert Sedgewick's Algorithms and in the section about The complexity of sorting, I found the following paragraph: Proposition. Mergesort is an asymptotically optimal compare-based ...
Tran Khanh's user avatar
5 votes
1 answer
719 views

What don't I understand in topological sort using DFS?

Wikipedia says: The algorithm loops through each node of the graph, in an arbitrary order, initiating a depth-first search that terminates when it hits any node that has already been visited since ...
porton's user avatar
  • 493
0 votes
1 answer
30 views

Why is it impossible to do a linear time radix sort on n integers and ranging from $0$ to $n^{3} - 1$?

I propose by doing a base-n expansion of the numbers, we have that since there are $n^{3}$ values and $n$ digits in this expansion, there are a total of $\log_{n} n^{3} = 3$ digits. Note in this base-...
cdknight's user avatar
  • 103
0 votes
0 answers
12 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 ...
Omkar's user avatar
  • 1
1 vote
1 answer
53 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 ...
rranjik's user avatar
  • 284
3 votes
2 answers
37 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 ...
san zhang's user avatar
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 ...
user2812779's user avatar
0 votes
1 answer
40 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 ...
RAHUL 's user avatar
  • 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 ...
orlp's user avatar
  • 13.6k
0 votes
2 answers
68 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 ...
user146551's user avatar
0 votes
0 answers
34 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 ...
Don Freecs's user avatar
0 votes
2 answers
98 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 ...
Zirui Wang's user avatar
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 ...
Zumikya's user avatar
  • 73
1 vote
0 answers
113 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). ...
sbh's user avatar
  • 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 ...
vakvakvak's user avatar
  • 121
1 vote
0 answers
37 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$...
ABu's user avatar
  • 529
2 votes
0 answers
93 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 ...
Lior's user avatar
  • 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 ...
Zumikya's user avatar
  • 73
1 vote
1 answer
108 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 ...
sbh's user avatar
  • 51
3 votes
1 answer
62 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 ...
Iman Mohammadi's user avatar
0 votes
0 answers
51 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,...
STRICKLAND_7's user avatar
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 ...
luifire's user avatar
  • 21
-1 votes
2 answers
66 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 ...
Amir's user avatar
  • 3
0 votes
0 answers
25 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 ...
Muhammad Ikhwan Perwira's user avatar
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{...
Florian Tramèr's user avatar
1 vote
1 answer
117 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 ...
Lorenzo's user avatar
  • 13
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 ...
AncientSwordRage's user avatar
2 votes
1 answer
54 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 ...
il_mix's user avatar
  • 123
1 vote
0 answers
43 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: <...
contrapsych's user avatar
1 vote
2 answers
125 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). ...
river_bell's user avatar
1 vote
1 answer
54 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 ...
Jim Diroff II's user avatar
1 vote
1 answer
40 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,...
Hagenbeck's user avatar
0 votes
0 answers
74 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 ...
Reggie Hurley's user avatar
0 votes
0 answers
27 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 ...
C.C.'s user avatar
  • 159
4 votes
2 answers
86 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 $...
Todd Sierens's user avatar
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 ...
Todd Sierens's user avatar
0 votes
0 answers
24 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 ...
sbh's user avatar
  • 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, ...
Gideon Kogan's user avatar
1 vote
2 answers
146 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 ...
Eric Coulthard's user avatar
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 ...
nico263nico's user avatar
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 ...
ExpressionCoder's user avatar
0 votes
1 answer
67 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 ...
moonman239's user avatar
1 vote
0 answers
44 views

Shell sort algorithm analysis

Given this Shell sorting algorithm implementation: ...
Kim's user avatar
  • 21
1 vote
0 answers
37 views

Shell algorithm knuth sequence time complexity analysis

Given this shell sort algorithm implementation: ...
Kim's user avatar
  • 21

1
2 3 4 5
19