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

learn more… | top users | synonyms

0
votes
2answers
44 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
28 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
12 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
19 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
61 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
47 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
40 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
16 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
21 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
28 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
56 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
51 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
20 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
23 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
11 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
127 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
36 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
36 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
93 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
19 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
23 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
51 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
63 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
69 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
34 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
59 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
39 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
42 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
45 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
62 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
57 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
37 views

Question about a cycle when doing topological sorting

First off, this is a homework question, but I'm just a bit confused on some of the smaller details of doing a topological sort. The homework question can be seen here (it shows the graph). It says: ...
0
votes
0answers
47 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
0answers
20 views

Under what conditions is this a good idea for modifying bucket sort?

So bucket sort works best if the data are uniformly distributed. So suppose we have $n$ numbers to sort and we take a random sample of size $O(n^{1/2})$ or $O(n^{2/3})$ or even $O(n / \ln n)$ and sort ...
0
votes
2answers
137 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
281 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
21 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
61 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
43 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
81 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
284 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
32 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 ...
1
vote
1answer
457 views

Sorting a sequence by two stacks

There is a finite length sequence $A$ which is a permutation of 1~n.for example A=(1,3,2,4) And two stacks S1,S2 like this: Each time you can choose one operation from below: 1. Put the first number ...
0
votes
1answer
47 views

Quicksort-How did we get the relation?

At the proof of the theorem that the expected time of Quicksort is $O(n \log n)$, there is the following sentence: We suppose that the partitions are equally likely, so the possibility that the sizes ...
1
vote
1answer
92 views

Expected time of Quicksort

I am reading the proof of the theorem: The Algorithm Quicksort sorts a sequence of $n$ elements in $O(n \log n)$ expected time. The proof is this: For simplicity in the timing analysis assume ...
1
vote
2answers
52 views

The expected time to sort $n$ elements is bounded below

Prove that the expected time to sort $n$ elements is bounded below by $cn \log n$ for some constant $c$. Could you give me some hints how I could do that?
0
votes
2answers
87 views

Find both the largest and second largest elements from a set

Consider finding both the largest and second largest elements from a set of $n$ elements by means of comparisons. Prove that $n+\lceil \log n \rceil -2$ comparisons are necessary and sufficient. ...