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

learn more… | top users | synonyms

1
vote
1answer
21 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
12 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
56 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
27 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
44 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
45 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
30 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
13 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
20 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
69 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 ...
3
votes
0answers
49 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
46 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
25 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
votes
0answers
30 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) + ...
1
vote
2answers
59 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
65 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
231 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
42 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
66 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
124 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, ...
0
votes
0answers
20 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
91 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
66 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
73 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
35 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 ...
-3
votes
1answer
82 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
40 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 ...
4
votes
0answers
53 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 [A1 .. A2 .... An](random order). We have a comparator C, but it has a probability p to return correct ...
1
vote
1answer
55 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 ...
1
vote
1answer
42 views

Why is Mergesort $O(n)$ rather than $O(n\log{n})$?

Assume we want a divide-and-conquer algorithm that finds the max and min of a set $S$ with $n = 2^k$ elements, e.g. mergesort. The recurrence for time complexity is $T(n)=2*T(n/2) +2$, for $n>2$, ...
0
votes
1answer
65 views

Is this a valid example of a poset?

I am trying to understand better the basic concepts of partially ordered sets, and tried my own examples by using modular-arithmetic. For this, I tried to define an algorithm to order integers, here ...
1
vote
1answer
60 views

Sorting algorithms

How could we show that the algorithm of Mergesort is stable, Quicksort is not stable but it can be implemented as stable, Heapsort is not stable. I have show that the algorithm of Insertion ...
0
votes
1answer
31 views

Is the invariant correct?

I want to show that Insetion Sort is stable... Do I have to do that using an invariant?? Is the invariant the following?? At the beginning of each iteration of the for loop, if $A[a]=A[b], a<b ...
0
votes
0answers
48 views

Can linear execution time be achieved [duplicate]

The SELECT algorithm determines the $i$th smallest of an input array of $n>1$ distinct elements by executing the following steps. Divide the $n$ elements of the input array into $\lfloor ...
0
votes
2answers
198 views

Dividing the interval in subintervals of equal length

I am asked to describe the operation of the processure BUCKET SORT at the array $$A=\langle 0.75, 0.13, 0.16, 0.64, 0.39, 0.20, 0.89, 0.53, 0.71, 0.42, 0.19 \rangle $$ dividing the interval $[0, 1)$ ...
1
vote
2answers
491 views

Can anyone explain the average case in insertion sort?

I am not sure if this question is off topic or not but a question like this has been asked on this site before - Insertion sort proof Here is an example of insertion sort running a on a set of data ...
1
vote
1answer
24 views

Is there a typo in this runtime analysis of selection sort?

This is from https://courses.cs.washington.edu/courses/cse373/13wi/lectures/02-25/19-sorting2-select-insert-shell.pdf, slide 6. The instructor is doing a runtime analysis of selection sort. Here is ...
0
votes
0answers
65 views

Why the space of all permutations of a vector (n!) is smaller than the space of all possible permutations of a sorting network?

Imagine you have a vector with 2048 entries. The total permutations are 2048! Now you have a sorting network let us say AKS, the total number of possible results with nlog(n) gates is $2^ {n log (n)}$ ...
0
votes
1answer
44 views

Can a comparison network obtain all the n! permutations of a vector?

I want to permute a vector using comparison networks. This is the only method I have at my disposal. My original idea is to use a sorting network like Batcher or Bitonic. Basically I place my vector ...
0
votes
1answer
92 views

Counting Inversion Pair using Merge Sort

An inversion is a pair of places of a sequence where the elements on these places are out of their natural order. I understood the naive approach where we take an element from 1 list and compare with ...
0
votes
1answer
340 views

Insertion Sort algorithm array ordering and comparisons

I'm trying to figure out different scenarios in which insertion sort will have to make n(n-1)/2 comparisons (the worst case). The obvious case is when it the array is ordered in reverse (decreasing ...
2
votes
1answer
35 views

How to sort 4 (or more) values with non-piecewise functions?

This question was inspired by this: Finding a non-piece wise function that gives us the $i$'th largest number. My question is how to do this for four or more values. In other words, given 4 ...