# Questions tagged [sorting]

For questions about dividing groups of objects based on their properties.

360 questions
Filter by
Sorted by
Tagged with
37 views

### Is there a way for this to sort into a rectangle? Also, how would one compute this mathematically?

Is there a rigorous way to solve a problem like this. Also is there a solution to this exact case?
59 views

### Sorting a permutation by sorting half of the elements at a time

The problem: suppose we have an array $p[1..n]$ (where $n$ is a multiple of 4) which initially contains some permutation of the numbers $\{1, 2, \ldots, n\}$. The only way we are allowed to modify ...
• 31
1 vote
51 views

### Complexity of a Sorting Problem

i investigate the following problem. Given a set of tuples $(a_i, b_i), i=1\ldots,n$ with $a_i,b_i \in \mathbb{N}$, i want to order them into a sequence such that the sum of differences of endelements ...
• 19
32 views

### Is there an algorithm for sorting points in a field based on sweeping a line through them at an arbitrary angle?

Given a set of coordinates on a euclidean plane, is it possible to sort the points by sweeping a line through them where the line might not be strictly horizontal or vertical? The inputs to the ...
42 views

### Generating all possible rankings when merging sorted lists with rank instead of raw score information per element

Let $\{e_1, e_2, ..., e_n\}$ be the set of elements. Let $\{s_1(e_1), s_1(e_2), ..., s_1(e_n)\}$, $\{s_2(e_1), s_2(e_2), ..., s_2(e_n)\}$ be the scores of elements after applying two ranking functions ...
• 161
1 vote
38 views

### Average number of required swaps in selection sort

Assume that the distinct integers 1,...,N are in random order and need to be sorted using selection sort. Here I am interested in the average number of swaps required, rather than the number of ...
1 vote
165 views

### Proving a property of the Selection sort algorithm

Consider running the Selection sort algorithm on a permutation $p$ of $n$ elements. Let $f(p)$ denote the number of times the 'running minimum' changes throughout the algorithm. Conjecture: $f(p)$ is ...
• 168
1 vote
92 views

### Sort rectangles by size, but with a tunable advantage favoring squareness

I want to sort some rectangles from biggest to smallest, but with a tunable advantage favoring squarer rectangles. I'm sure this is super easy but I'm not getting it. I think it's related to topics ...
1 vote
22 views

### Proof for Largest enclosed area of a random set of points in a 2 dimensional coordinate field [closed]

Consider a set of points randomly distributed on a $2$ dimensional coordinate plane. There should exist one solution in which each point is used once to create a shape defined by each point as a ...
3k views

### Is it possible to "sort" a continuous function?

I was motivated for this question while seeking for a new sorting algorithm. Suppose a continuous function $f : [a, b] \to \mathbb{R}$ is given. I wanted to define the sorted version $g$ of $f$, which ...
• 2,049
50 views

### Is $a\log_2(b) \le b\log_2(a)$ for all $a$ and $b$ given that $1 \le b \le a$?

I am trying to optimize the number of comparison in the merge sort algorithm, particularly during the merging step. Is $a\log_2(b) \le b\log_2(a)$ for all $a$ and $b$ given that $1 \le b \le a$? I ...
• 507
1 vote
150 views

### Expected length of Stalin-sorted sequence [closed]

There is a pogramming meme called Stalin sort which works as follows: the algorithm proceeds from left to right and each time it encounters a value $a_i$ less than the previous one $a_{i-1}$ the ...
• 59
59 views

### Managing warehouse based on how likely it is that products are ordered together

I am trying to solve a rather difficult issue at my job right now. We are interested in installing a set of automatic trays in our warehouse, each of which can hold $N \in \{5, 6, \dots, 20 \}$ unique ...
• 31
48 views

### How to prove this sorting algorithm? [closed]

3 4 2 1-4 2 3 1 0-3 1 2 0 0-2 0 1 0 0-1 In this algorithm, the last column is reserved for the number of numbers in the sequence. In this algorithm,first we write the sequence and then put the number ...
1 vote
77 views

### Is there an intuitive reason natural logarithms arise in the analysis of randomized quicksort?

The randomized quicksort algorithm works as follows: If the list to sort is empty or has length one, it’s sorted. Otherwise, pick a uniformly random element of the list called the pivot element. ...
• 10.4k
54 views

### Doubts in Sorting algorithm-Pancake flipping.

Here, is the solution pdf for the pancake sorting problem. http://home.ustc.edu.cn/~ustcsh/py2016/data/GP79.pdf In the fifth page, the para with the start,"where xi is multiplied by the number of ...
64 views

### Is the number of transpositions always bounded by the number of inversions

While learning about alternating tensors, I did some searching and found that the parity of the number of inversions for a permutation $\sigma$ is the quals to the parity of the number of ...
• 1,664
49 views

### Tetrahedral pancake problem game.

I am currently playing around making a little puzzle game and was looking for some input from people better at maths than me. It is based on the pancake problem. You have a stack of $8$ "pancake&...
• 11
1 vote
153 views

### Average time complexity of insertion sort in Rosen's Discrete Mathematics and Its Applications

I came across the following average-case time complexity analysis for the insertion sort algorithm on page 483 of "Discrete Mathematics and its Application" by Kenneth Rosen: Average-Case ...
• 673
9 views

### What is the best way to sort X numbers into an Y positions "circle" to avoid any repetition of Z elements, minimizing consecutive numbers?

Please, what is the best way to sort X numbers into an Y positions "circle" to avoid repetition of any Z consecutive elements, minimizing consecutives? So let me try to better explain: A. ...
1 vote
55 views

### Is there a name for the problem of inferring a natural ordering from ordered subsets?

I came up with this question while sorting lego bricks. Is there a name for this type of problem? The so-called "Eintstein's Riddle" pops up in my mind, but I'm unable to discern if that ...
• 329
57 views

### Finding row/column permutation of a square matrix with similar rows that sorts rows lexicographically

I have a $n\times n$ square matrix $M$, and a set of $n$ natural numbers, where the rows of $M$ contain different permutations of such $n$ elements (with repeated rows allowed). I want to find a ...
• 451
33 views

### Sort including ratio between values and best of list

I have following values for each object: 100,50,50 30,100,20 100,80,20 120,50,70 120,60,60 300,100,20 350,50,100 30,300,300 120,10,100 I want to find an function how to calculate optimal ratio (...
1 vote
60 views

### What is the best algorithm to use for tournament ranking where every winner also "autowins" every win of the loser?

Let's say I have a tournament where I need to get a complete ranking of all players at the end of the tournament. The rule of the ranking is that if player A wins player B, then they also win every ...
1 vote
114 views

### Permuting the rows in ascending order first and then the columns of any Young tableau gives a standard Young tableau

Show that if you take any Young tableau and permute the rows in ascending order first and then the columns in ascending order (or columns first and then row), then you get a standard Young tableau. I ...
• 9,144
120 views

### Proof that sorting an array of n numbers requires n - c transpositions?

Story: I was trying to do a leetcode problem that wanted me to calculate the minimum number of non-adjacent swaps (i.e transpositions) to sort an array. This led me into a rabbit hole, learning about ...
23 views

### Size of the Partitions of Quicksort

We are partitioning a sequence of $n$ elements, obtaining two partitions with $n-1$ total elements (an element is consumed as the pivot). My textbook says in a best-case split, the partitions have ...
• 19
119 views

### How to prove Bead-Sort is correct?

"Consider a set X of n positive integers to be sorted and assume the biggest number in X is m. Then, the frame should have at least m rods and n levels." (see linked article below for ...
33 views

I'm trying to learn about probabilistic analysis of algorithms, so I made some exercises for myself to try to solve. One of these exercises I don't understand how to solve: Given the following ...
• 195
1 vote
27 views

### 2d threshold satisfying problem with minimum number of elements

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
39 views

### Algorithm for sorting by equivalence relation

I hope the thread title isn't too strange, but I don't know better. My question seems a quite simple one. Having a set of objects I'm interested in the subsets that are pairwise equal. Example: A set ...
• 21
1 vote
124 views

• 551
1 vote
97 views

### Constructing uniformly random permutation by coin flippings

Let $R \subseteq \{1 \dots n\}^2$ be a variable of strict partial order on $n$ elements. Initially, $R_0 := \emptyset$. The goal is to gradually and randomly enlarge R, so that R end up being a ...
212 views

### probability of number of comparisons of randomized quicksort

Let's assume we have an array of length $5$ which contains pairwise different integers. The subcript denotes the order of the respective integer, so $i_1<i_2<i_3<i_4<i_5$. We apply the ...
• 4,554
1 vote
28 views

### Sorting data tables based on trends - With linear algebra

Assume that you have $y$ series of data. Each data set is $n$ length long. Example: $$X_1 = x_{1,1}, x_{1,2}, x_{1,3}, x_{1,4}, x_{1,5}, x_{1,6}, x_{1,7}, \dots , x_{1, n}$$ X_2 = x_{2,1}, x_{2,2}, ...
• 2,964
1 vote
86 views

### Does one level of worst-case recursion in quicksort cost $\Theta(n^2)$ or $\Theta(n)$?

Page 180 (section 7.4.1) of CLRS 3rd edition says a worst-case split at every level of recursion in quicksort produces a $\Theta(n^2)$ running time It seems that $\Theta(n^2)$ should be $\Theta(n)$ ...
• 1,446
27 views

### Get max number with lowest number of steps

I have a csv with Rows of data. Each row consists of an amount_of_apples and a number of steps. The amount_of_apples are the ...
• 101
1 vote
59 views

### Simpler proof that sorting a $n$-tuple of i.i.d. random variables gives a random permutation

It seems quite "obvious" that if you sort a $n$-tuple of i.i.d. variables (assuming they have an order and ties do not exist - which is true with probability $1$ for, say, $U(0, 1)$) that ...
• 10.5k
1 vote
45 views

### prove that a binary string can always be sorted using the above operation finite number of times

Blockquote I came across this problem on a competitive programming site : 'CodeChef'. I was given a binary string and I had to sort it using the following operation : "I could take any substring ...
• 127
1 vote
25 views

### How to calculate "hot" or "interesting" data? Based on both the rating and the number of ratings.

I can't be the first to ask this but I have now idea how to word my question correctly. I tried googling but was not successful. Let's say I have an excel sheet with names of applications. Each row ...
• 11
135 views

### I think I have discovered a new sorting algorithm using binary search tree. [closed]

If we some how transform a Binary Search Tree into a form where no node other than root may have both right and left child and the nodes the right sub-tree of the root may only have right child, and ...
45 views

### How to sort into X bins Y times with minimum overlap?

Let's say I'm hosting a series of dinner parties for a total of $N$ guests. Each night, there are $X$ tables, and we are meeting for a total of $Y$ nights. I want to preassign the guests to tables ...
• 4,524
1 vote
89 views

### Proving that the permutation 312 is not stack-sortable

We say that a permutation $σ ∈ S_n$ is sortable through a stack if there is a sequence of (PUSH) and (POP) operations such that the initial state: can be transformed into the final state: I’m ...
1 vote