Questions tagged [sorting]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
38 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
31 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 while it bought by the player items may repeat ror the dame player ...
Don Freecs's user avatar
0 votes
2 answers
81 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
4 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
107 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
69 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
1 vote
0 answers
35 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
  • 499
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 ...
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
103 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
39 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
34 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
48 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
57 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
22 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
85 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
  • 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 ...
AncientSwordRage's user avatar
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 ...
il_mix's user avatar
  • 123
1 vote
0 answers
37 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
1 answer
84 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
40 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
38 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
57 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
21 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
  • 149
4 votes
2 answers
84 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
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 ...
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
136 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
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 ...
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
62 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
42 views

Shell sort algorithm analysis

Given this Shell sorting algorithm implementation: ...
Kim's user avatar
  • 11
0 votes
0 answers
27 views

Shell algorithm knuth sequence time complexity analysis

Given this shell sort algorithm implementation: ...
Kim's user avatar
  • 11
2 votes
1 answer
85 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 ...
Neel's user avatar
  • 141
0 votes
0 answers
31 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 ...
blu's user avatar
  • 1
1 vote
2 answers
93 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 ...
LearningSomeone's user avatar
0 votes
2 answers
76 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 ...
Titanlord's user avatar
  • 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 ...
zzzhhh's user avatar
  • 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 ...
ABu's user avatar
  • 499
2 votes
1 answer
84 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$ ...
Varun Vejalla's user avatar
1 vote
1 answer
58 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 ...
zale's user avatar
  • 113
-2 votes
1 answer
113 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). ...
user19843013's user avatar
0 votes
3 answers
173 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 ...
Mike Rain's user avatar
-4 votes
2 answers
70 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 ...
Arushka's user avatar
0 votes
1 answer
25 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. ...
chausies's user avatar
  • 532
0 votes
0 answers
64 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 ...
Nick B. 's user avatar
0 votes
2 answers
71 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:]$ ...
WalaWizon's user avatar
0 votes
1 answer
121 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 ...
Tomyy's user avatar
  • 25

1
2 3 4 5
19