Skip to main content

Questions tagged [sorting]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
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?
Ahmed Tayee's user avatar
3 votes
0 answers
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 ...
janezb's user avatar
  • 31
1 vote
0 answers
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 ...
Dom's user avatar
  • 19
0 votes
1 answer
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 ...
phill2mj's user avatar
0 votes
0 answers
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 ...
Dion's user avatar
  • 161
1 vote
1 answer
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 ...
Ali Kwant's user avatar
1 vote
1 answer
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 ...
Sharp Edged's user avatar
1 vote
1 answer
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 ...
Jason Kleban's user avatar
1 vote
0 answers
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 ...
David Smith's user avatar
31 votes
3 answers
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 ...
Dannyu NDos's user avatar
  • 2,049
0 votes
2 answers
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 ...
TSR's user avatar
  • 507
1 vote
1 answer
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 ...
saroyr's user avatar
  • 59
3 votes
1 answer
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 ...
Owen S's user avatar
  • 31
-3 votes
1 answer
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 ...
Suraj Nair's user avatar
1 vote
1 answer
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. ...
templatetypedef's user avatar
0 votes
0 answers
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 ...
Suraj Nair's user avatar
3 votes
1 answer
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 ...
wsz_fantasy's user avatar
  • 1,664
0 votes
0 answers
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&...
Wob's user avatar
  • 11
1 vote
0 answers
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 ...
user51462's user avatar
  • 673
0 votes
0 answers
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. ...
Leandro Casella's user avatar
1 vote
1 answer
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 ...
Zluudg's user avatar
  • 329
0 votes
0 answers
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 ...
ABu's user avatar
  • 451
0 votes
0 answers
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 (...
Kristián Stroka's user avatar
1 vote
0 answers
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 ...
Kristo Vaher's user avatar
1 vote
1 answer
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 ...
Sayan Dutta's user avatar
  • 9,144
0 votes
1 answer
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 ...
9j09jf02jsd's user avatar
0 votes
1 answer
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 ...
kote's user avatar
  • 19
0 votes
1 answer
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 ...
Hugh Mann's user avatar
0 votes
1 answer
33 views

An exercise I made for myself about probabilistic analysis (PERMUTE-SORT)

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 ...
sag0li's user avatar
  • 195
1 vote
0 answers
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 ...
TonyMontana18's user avatar
1 vote
0 answers
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 ...
User42's user avatar
  • 21
1 vote
0 answers
124 views

Been trying to prove that $n! = \Omega(n^{100})$. I was approaching it with the solution below. I am not really sure my assumptions

We know that: $$f(n) = n! = \Omega (g(n)$$ if $$g(n) = O(f(n))$$ then, $$f(n) \in O(g(n))$$ If $$ f(n) \leq c \cdot g(n) \quad \textbf{for all $n\geq 1$}$$ then, assuming $n=1$ and $c=100^{100}$: $$n^{...
Mike's user avatar
  • 21
0 votes
0 answers
150 views

Prove that $n! = \Omega(n^{100})$

I justed started studying the sorting algorithm, so I need help solving problems on (big Omega) $\Omega$ How can I Prove that $n! = \Omega(n^{100})$ I know that we write $f(x) = \Omega(g(x))$ if $g(x) ...
user avatar
1 vote
0 answers
48 views

Sort a group of distributions

Given a group of $n$ probability distributions, $P_1, P_2, \ldots, P_n$, we sample an outcome for each of the distributions $X_i \sim P_i, \forall i \in [n]$, and we want to compute the probability of ...
Vezen BU's user avatar
  • 2,098
0 votes
0 answers
289 views

Prove that MergeSort is stable for any input size n ∈ N using induction on n.

In terms of a list of objects with two separate fields, suppose a stable sort would order the list in increasing order. However, if two elements have the same number, then they'll appear in the same ...
Anonymous_00011's user avatar
1 vote
1 answer
434 views

Modified quicksort

Quicksort has an expected runtime of $\mathcal O(n\log n)$ when choosing a pivot uniformly at random. Now consider that before each iteration of quicksort, we sample $\log n$ elements of the array and ...
joeren1020's user avatar
0 votes
1 answer
65 views

Question about quicksort

It is known that the expected running time for quicksort is $\mathcal O(n \log n)$ if the pivot is chosen uniformly at random. In this case the running time $T(n) $satisfies, $$ T(n) \leq \mathcal O (...
Keio203's user avatar
  • 551
1 vote
1 answer
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 ...
Sylvain Hubert's user avatar
4 votes
1 answer
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 ...
Philipp's user avatar
  • 4,554
1 vote
0 answers
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}, ...
euraad's user avatar
  • 2,964
1 vote
1 answer
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)$ ...
JJJohn's user avatar
  • 1,446
0 votes
0 answers
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 ...
osaro's user avatar
  • 101
1 vote
1 answer
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 ...
orlp's user avatar
  • 10.5k
1 vote
2 answers
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 ...
karnop's user avatar
  • 127
1 vote
0 answers
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 ...
geeshta's user avatar
  • 11
2 votes
0 answers
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 ...
Uday Uppal's user avatar
0 votes
1 answer
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 ...
jamaicanworm's user avatar
  • 4,524
1 vote
0 answers
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 ...
Duncan Taylor's user avatar
1 vote
1 answer
190 views

Algorithim to choose comparison pairs for topological sorting

I'm trying to find or create an algorithm to roughly sort arbitrary objects using pairwise comparison where the only concern is minimizing the number of comparisons. So my question is essentially is ...
Salvatore Ambulando's user avatar
3 votes
1 answer
110 views

Generalized Catalan number satisfying recursive definition

Wondering if the numbers satisfying the following relationship have a name or known closed-form solution. They show up in enumerating possible configurations of swaps during the execution of a bubble ...
elplatt's user avatar
  • 133

1
2 3 4 5
8