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

learn more… | top users | synonyms

1
vote
1answer
21 views

Help with simplifying summation

Let $x \in \mathbb{R}^n$ be a vector of non-negative numbers $x = (x_1, \ldots, x_n)$ with mean $\bar{x}$. I would like to prove that $$\frac{\sum_{i = 1}^n \sum_{j = 1}^n \left| x_i - x_j \right|}{2 ...
3
votes
1answer
24 views

Sorting rows then sorting columns preserves the sorting of rows

From Peter Winkler's book: Given a matrix, prove that after first sorting each row, then sorting each column, each row remains sorted. For example: starting with $$\begin{bmatrix} 1 & -3 &...
0
votes
0answers
23 views

How to get increasing int number based on two values

I did ask this question on SO but it seems this will find more appropriate audience here. I have a Google map where I am dropping markers based on events, this happens periodically and after 8 hours ...
0
votes
0answers
17 views

Derive a probability distribution to transform scalars for weighted random sampling

Let's say I have a case with only two choices: $N_a$ = 20 $N_b$ = 10 I want to find a probability distribution that I can map these two values too, such that the probability of one variable being ...
0
votes
1answer
36 views

Expected number of permutations required to sort a list of numbers

Given a list of N numbers if we are performing random permutations each time and checking whether the list is sorted, what will be the expected number of permutations required to sort that list?
0
votes
0answers
14 views

2D Bin Packing with Ordering Along One Dimension

This is my second attempt at solving this particular problem (original is here: Topological sort into a limited number of bins, each with limited capacity). For clarity, I have reproduced the relevant ...
1
vote
1answer
27 views

Topological sort into a limited number of bins, each with limited capacity

I'm working on a scheduling/design tool for educational courses. I have lists of courses, some which require others to be taken first (dependencies), others that require courses to be taken together ...
1
vote
0answers
19 views

How to sort a list of tuples?

I am neither a mathematician, nor a computer scientist, but I have the following problem, which I cannot solve myself. I have $k$ $i$-tuples $(x_1, x_2, …, x_i)$, where $x ∈ [0,1]$. I need to order ...
1
vote
0answers
23 views

Sort a set of points to minimize the sum of the square distances between two consecutive points

Let $P$ be a finite set of points in $\mathbb{R}^3$. Let the number of points in $P$ be $n\in\mathbb{N}$. I want to sort the points in $P$ to minimize the sum of the distances between two consecutive ...
2
votes
1answer
47 views

why can't sort 12 elements in 29 comparisons

The information theoretic lower bound for sorting 12 elements is using 29 comparisons, but actually we can't sort them in less than 30 comparisons. My problem is that why we can't reach the ...
0
votes
0answers
7 views

Why %RSD of execution times, while sorting hundreds of arrays, is lower for larger arrays of random integers?

I am experimenting with the sorting of arrays and their execution times. While using bubblesort, insertsort and ...
2
votes
2answers
24 views

Hasse diagrams for sorts of size 3 and 4?

Does anyone know what does the following mean? I understand that a Hasse diagram represents a given partial order but I don't seem to get this example. Below is a Hasse diagrams for sorts of size 3 ...
0
votes
2answers
56 views

Comparison between $n\log n$ and $n^2$ sorting algorithms

Suppose we have two sorting algorithms which takes $O(n\log n)$ and $O(n^2)$ time. What can we say about it? Is it always better to choose $n\log n$ if the size $n$ is not given? Or can we say on an ...
1
vote
1answer
24 views

Looking for an equation that reflects the majority of a collection

I'm working on a computer program, part of which involves sifting through large collections of numbers (by large, I mean 16 million+ numbers). I expect these collections to almost entirely be composed ...
-1
votes
1answer
21 views

How to sort ten coin for twenty single weightings? [closed]

We can sorting 10 coin for 20 weighting, don't it? We can know which of the two coins is heavier for one weighting. Any two coin have different weight.
0
votes
0answers
13 views

Finding the Reccurrence of a Periodic Sorting Network

Consider this Periodic Network of input size $n = 8$. I am trying to find an asymptotic approximation of the size (# of comparators) for such network. My attempt: Since there are $n$ inputs, there ...
0
votes
1answer
13 views

For which $k$ I could sort permutation?

Suppose we have some permutation: $$p = a_{1}..a_{n}$$ We could inverse some subarray length of $k$. So my question is: for which $k$ I could sort my permutation using only my $k$-inverse? Obviously ...
1
vote
1answer
59 views

Formulating an equation for a group sorting program.

I'm trying to formulate an equation/algorithm to solve this problem (for a program I'm writing): Rules: A person, p, that is to be sorted can exclude n amount of people from the list. The excluded ...
0
votes
0answers
34 views

Vector sort operator

I was wondering whether there exists a definition of the sort operator for vector, i.e., the operator that given a vector of $\mathbb{R}^n$ yields a vector of $\mathbb{R}^n$ whose components are ...
1
vote
1answer
49 views

Randomized Quick Sort and Partition Probability?

We know about Quick Sort and Randomized Version and Partition. I ran into a Fact when I read my notes. Let $0 < a < 0.5$ be some constant. We have an $n$-element array as input. Randomized ...
0
votes
2answers
47 views

Break a tie in a sum of a series of points

I'm an engineer and a programmer, NOT a mathematician. I hope that I am able to describe my problem well enough for you to understand, even though I'm incapable of asking it in "mathematician speak". ...
0
votes
0answers
33 views

The complexity of bubble sort and insertion sort for a list with a given number of inversions

Let the length of a list be $n$, and the number of inversions be $d$. Why does insertion sort run in $O(n+d)$ time and why does bubble sort not? When I consider this problem I am thinking of the ...
0
votes
0answers
15 views

How to sort list with Bayesian inference?

I have long list of Instagram accounts with the following data: number of followers of the account (N); number of users, who follows both this and mine accounts (n). I would like to get list of ...
0
votes
1answer
21 views

Sorting Algorithm for weakly ordered list

I am aware of some sorting algorithms and there pros and cons but my question is specifically: What is a good sorting algorithm for a list that is generally but not strictly increasing, i.e. 1 5 4 8 5 ...
2
votes
2answers
76 views

Is It Possible to Represent the Fractional Part of a Number as an Integer?

This question may not even have an answer in mathematics, so I apologize if it is too dumb. I am writing an algorithm to order a series of numbered items. These items have a unique numbering style ...
6
votes
1answer
116 views

How much life does it take to stack your deck? (Sorting problem)

There is a card in Magic the Gathering called Lim-Dul's Vault. While it is slightly more complicated than presented, the question I would like to consider is this: Pay 1 life. Look at the top 5 ...
4
votes
2answers
47 views

Sorting almost sorted array in $O(n)$ time

What is the best way to sort an array that has at least half of its elements in their final position? Is it possible to achieve $O(n)$ running time?
0
votes
1answer
17 views

How big the maximal decrease in consecutive elements of a sequence?

Consider a sequence $(s_1, ..., s_k)$, and we have it sorted in decreasing order $(\tilde{s}_1, ..., \tilde{s}_k)= (\sigma(s_1), ..., \sigma(s_k))$. Define $k_{\max} = \max \left( \max_i \left( s_i ...
0
votes
0answers
28 views

Binary tree for sorting combinations

Let's imagine to have a binary n-array as input. All the possible combinations for this n-array will be 2^n. Right? Now, I want to put these combinations in a specific order. In particular, I want "0,...
0
votes
0answers
31 views

What does it mean sum of the Indicator random variable times something?

I am studying quick-sort and analysis its expectation. The following is quick sort's recurrence. $$ T(n) = \left\{ \begin{array}{ccc} T(0) + T(n-1)+\Theta(n),\ \ if\ \ 0:n-1\ \ split\\ T(1) + T(n-...
1
vote
2answers
60 views

Using a function to order an integer's digits from least to greatest?

Say you have an integer denoted as $n$. Is it possible to make a purely mathematical function that could take $n$ and order its digits from least to greatest? I know how to do this programatically. I ...
1
vote
0answers
78 views

Proving Quick Sort algorithm

Can we provide a proof for the correctness of the following quick sort algorithm: quicksort(a1,a2,...an) { (b) less := the empty list (c) greater := the empty list pivot = a1 for i := 2 to n if ...
0
votes
0answers
23 views

Sorting by k-ary Comparisons

I found this paper and was trying to decipher it to derive the minimum number of sortings of n elements with k elements in each query that would solve for the entire linear order. The paper defines: ...
0
votes
1answer
25 views

Prove that removing elements from a sorted list of numbers does not make the list unsorted

In other words, you have an ordered finite list of numbers which is sorted ascendingly (without loss of generality), for example [1,2,5,7,10,12]. Remove elements from the list, the list is still ...
0
votes
0answers
13 views

Is is possible to toposort in weighted cyclic graph by Markov chain simulation?

I'd like to order the nodes in a weighted, cyclic graph. The graph is rather large (~50000 nodes) and very sparsely connected (~100 per node). All connection weights are in $]0..1[ \subset \mathbb{R}$ ...
1
vote
1answer
406 views

Bubble Sort vs Shuttle Sort

When sorting a list of items, shuttle sort (the one taught in the A-Level Maths unit D1 by OCR, NOT Cocktail sort - see below) does no more than as many comparisons as bubble sort (they always do ...
0
votes
0answers
44 views

Worst case complexity of Shell Sort

I am considering the gap sequence $g=4,2,1$. I am able to prove that the upper bound of the algorithm is $O(n)$ assuming that in every step we are going to have $g$ insertion sorts of $n/g$ elements ...
2
votes
0answers
77 views

Setting up a recurrence for Odd-Even Mergesort

Given the below algorithm How would one go about setting up a recurrence for both that merging algorithm AND using this "new" merging algorithm in a traditional merge sort? What I've tried For ...
1
vote
0answers
139 views

Setting up and solving a recurrence relation

Assume we have two lists, $A$ and $B$; both are sorted lists each with $n$ elements (assume $n$ is a power of 2). We want to recursively merge the odd-indexed elements from each list: merge $a_1, a_3,...
0
votes
0answers
21 views

Type(s) of Hashing function that keeps the ordering information

I am asking this question from a perspective that we need to store a set of hashed data that can be queried later for in an ordered fashion. My situation is that some data has to be encrypted, I am ...
1
vote
1answer
24 views

Sorting triangles by hypotenuse length

I have some points in $xy$ space and I need to sort distances between these points. If I calculate real distance, then I need to perform $\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$ and this is very time ...
0
votes
0answers
142 views

Displaying a graph with minimum overlapping edges

Context I am developing UI for a skill web for a mobile game. Each skill may have requirements from other skills, or sometimes no requirement at all. The problem The description above is ...
0
votes
0answers
45 views

Ideal amount of piles to sort a stack of 250 cards (magic the gathering)

I'm a hobbyist working on a mechanical sorting machine to sort magic the gathering cards. I'm by no means a mathematician though, and I was wondering if you all wouldn't mind helping me out with a ...
0
votes
3answers
69 views

A lower bound on sorting algorithms

I think I have a proof that $n\ln n$ is optimal in the sense that is it a lower bound for sorting algorithms. See here for a list. It must be greater than $n$ as this is too linear, and the $\ln$ ...
0
votes
2answers
74 views

find which two points an arbitrary point is nearest to

I have a line segment of connected points (a path in 2D), and a point $P$ that is not calculated based on this segment, although I can guarantee that the point will be placed along the path. Based on ...
0
votes
0answers
40 views

How to divide items into nearly equal sized groups

I teach a class with about $N=290$ students who will be taking an exam next week. The exam consists of two sections ($A$ and $B$) each with 6 essay questions. Students must answer one essay question ...
-4
votes
1answer
101 views

How many recursive calls are made when quicksort is size n [closed]

How many recursive calls are necessary when quickSort sorts an array of size n if you use median-of-three pivot selection? I thought the answer is n times because isnt this the best case?
1
vote
0answers
41 views

How to state a recurrence that expresses the worst case for good pivots?

The Problem Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and $...
5
votes
0answers
70 views

Analysis of sorting Algorithm with probably wrong comparator?

It is an interesting question from an Interview, I failed it. An array has $n$ different elements $[A_1 , A_2, ..., A_n]$ (random order). We have a comparator $C$, but it has a probability $p$ to ...
1
vote
1answer
59 views

What would the expected number of swaps in a merge sort be?

If I were given a list of random numbers say x1, x2, .........., xn and these numbers are sorted according to the merge sort algorithm. What would be the number of expected swaps/exchanges which would ...