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

learn more… | top users | synonyms

-2
votes
0answers
23 views

Fixed decimal place sort problem [on hold]

I have a collection of randomly arranged fixed dp numbers, e.g. 5.0, 5.000, 5, 5.000000. The problem is to sort these numbers.
0
votes
1answer
19 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
21 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
38 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
41 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
57 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
41 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
0answers
8 views

Order subsets amongst em self and in global list?

This is the scenario, I have a list of 200 names I want to order to the users preferences. I present this names to the user four at the time and the user ranks em 1-4 click next and gets to see a new ...
0
votes
2answers
36 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. ...
1
vote
3answers
60 views

How many comparisons are required?

Let $S$ be a set of $n$ integers. Assume you can perform only addition of elements of $S$ and comparisons between sums. Under these conditions how many comparisons are required to find the maximum ...
1
vote
1answer
48 views

A decision tree has an expected depth of at least $\log n!$

I am looking at the proof of the following theorem and I have some questions. The theorem is the following: On the assumption that all permutations of a sequence of $n$ elements are equally ...
0
votes
2answers
63 views

The decision tree has height at least $\log n!$

The proof of the theorem Any decision tree that sorts $n$ distinct elements has height at least $\log n!$ is the following: Since the result of sorting $n$ elements can be any one of the $n!$ ...
3
votes
2answers
125 views

Application of Mergesort

We have $8$ players and we want to sort them in $24$ hours. There is one stadium. Each game lasts one hour. In how many hours can we sort them?? I thought that we could it as followed: ...
0
votes
1answer
49 views
+50

Merge two sets, list and tree

We are given two sets $S_1$ and $S_2$. We consider that $S_1$ is implemented, using a sorted list, and $S_2$ is implemented, using a pre-order sorted tree. I have to write a pseudocode, that ...
1
vote
0answers
24 views

Help with proof about merge two heaps to one heap…

We have two heaps: $H_1,H_2$ that have $n_1,n_2$ elements ($H_1$ have $n_1$ elements and $H_2$ have $n_2$ elements). We know that the smallest element at $H_1$ is bigger the root (the biggest element) ...
0
votes
1answer
39 views

Notation for rank of weakly ordered elements

I'm looking for a mathematical notation for the following algorithm where $D$ is a diagonal square matrix and $w$ a scalar value. Sort $D$ by the diagonal entries ascending for the first entry ...
1
vote
0answers
18 views

Minimal and maximal elements of a set consisting of sums of random variables

Consider a set of $n$ correlated random variables, $A =\{X_1, \ldots, X_n\}$. Suppose that I have another set, $B$, of all possible combinations of size $k$ of the random variables. Now, if for each ...
0
votes
1answer
22 views

Recursive sort that doesn't require list splicing?

I was just wondering if there was some form of sort algorithm that doesn't require any form of splicing of the original list? Thanks in advance.
0
votes
0answers
15 views

Estimating how many searches will be needed to justify time spent on presorting an array.

Problem Estimate how many searches will be needed to justify time spent on presorting an array of $10^3$ elements if sorting is done by merge sort and searching is done by binary search. (You may ...
1
vote
2answers
68 views

Sort sequences of the form ABCABCABC, ABABAB, ABCDABCD, etc.

You are given a sequence of distinct elements $P$ and a positive integer $R$. Consider the sequence obtained by repeating $P$ $R$ times and concatenating together. For example, if $P = \langle A, ...
1
vote
0answers
70 views

About Bayesian formula and rating system

I'm building a scoring system with score from 0 to 5) and I would like to sort products according to the number of reviews and their scores. After some research on the Internet I have found two ...
1
vote
1answer
24 views

correcting an invalid binary heap in $\Theta (n)$

We are given a binary max (every node is larger than its children) heap with $n$ elements. We now change $\frac{n}{4}$ of the elements at random. We don't know which ones and to which value. And so, ...
2
votes
1answer
43 views

How equal are two given numbers

I have two numbers x & y for N different readings and wish to find how close they are from each other and would like to rank the reading in order of they equalness. If I were to have the ...
0
votes
0answers
32 views

# of ways to sort. Quick Sort Problem.

This is a question about the quick sort algorithm and the # of ways I can place the books on shelves. I have to place a book on n number of shelves with m number of books; m >= n >= 1. But I have to ...
2
votes
0answers
34 views

Empty List is Sorted?

Is an empty list considered to be sorted? Let's say I have a math function sort that sorts a list of numbers. ...
1
vote
0answers
38 views

Can we sort 6 numbers with at most 9 comparison? [duplicate]

i know there is an algorithm to sort 5 numbers with 7 comparison. Can we sort 6 numbers with at most 9 comparison? thanks to all.
5
votes
1answer
102 views

SQRTSORT from Vazirani's book on algorithms

I study the Algorithm book and saw the following exercise. I couldn't solve it. This is not homework, nor exam. Just reading some material on algorithms for preparing entrance exam. Any nice idea or ...
2
votes
1answer
209 views

Recurrence Relation - Merge Sort

We know the recurrence relation for normal merge sort. It is T(n) = 2T(n/2) + n. After solving it we can get T(n) = cnlogn. I ...
0
votes
0answers
66 views

sorting young's tableau better than n^3

Young's tableau takes $O(n^3)$ to sort. By sorting I mean sort numbers in existing young's tableau. http://en.wikipedia.org/wiki/Young_tableau Simply it is a matrix sorted by rows and columns. ...
0
votes
1answer
56 views

Why is the sentence true?

I am looking at the algorithm of the insertion sort: ...
0
votes
1answer
37 views

Show that the height of the heap is $\lfloor \lg n \rfloor$

I want to show that a heap with $n$ elements has the height $ \lfloor \lg n\rfloor$. That's what I have tried: The "best" case is a complete binary tree,and then it is of the form: So,the height ...
0
votes
2answers
52 views

Why is the height of a heap defined as $\lg n$?

I'm a bit confused about why the height of a heap (or a binary tree in general) is given by the floor of $\lg n$. E.g. if you have a tree with 7 nodes, you would get $h = 0$ instead of $h = 2$. Isn't ...
1
vote
1answer
70 views

Find 3rd largest number out of 7 under at most 11 comparisons

I know similar problem like "sort 5 numbers in 7 comparisons". I know no general algorithms exist. Do I just enlist all possible game trees?
0
votes
2answers
61 views

The value of loop variable at the end of a loop in the insertion sort

I am looking at the algorithm of the insertion sort: Input: $A[1 \dots n]$ ...
0
votes
0answers
62 views

An efficient algorithm to pair chess players in a team tournament

I found this question on a website. Your team is playing a chess tournament against a visiting team. Your opponents have arrived with a team of $M$ players, numbered $1,2,\dots,M$. You have $N$ ...
2
votes
0answers
28 views

Ordering binary matrices for reflection/rotation

I have a collection of $n\times n$ binary matrices and I would like to reduce it for symmetry ($D_4$ -- reflections and rotations). The naive method of testing each pair is very slow because the ...
5
votes
2answers
455 views

Is it possible to sort an array of 10 elements with 20 comparisons of two elements?

I think it's not, because there are $10!$ permutations of $10$ elements, and $10! \gt 2^{20}$. Can anyone point me how to prove it rigorously?
2
votes
0answers
29 views

Is it possible to sort products by result without calculating?

I have some numbers n in range 100 ... 999 and some other numbers m also in range 100 ... 999. Is it possible to sort all the product m*n without calculating the actual product? Sorry, my English for ...
1
vote
0answers
117 views

Pancake and increasing order

Determine the number of 5 pancake stacks that requires exactly 2 flips to put into the increasing order, i.e., 1,2,3,4,5. (Example: 3,4,2,1,5 is one of them.)
1
vote
0answers
30 views

Elementary Discrete Math Sorting Algorithms

I have a quiz tomorrow and cannot figure out a few of the examples he wishes us to complete. They seem pretty basic. Add (Input a list of numbers A1,A2.....An) Step 1: Let i =1 and S = 0 Step 2: ...
0
votes
1answer
58 views

Optimization problem for feeding the hungry

So I am trying to solve a problem. I believe it is $NP$. Assume we have $F$ cans of food of varying sizes. There are $P$ homeless people at the local shelter, where $F>P$. Each can of food, $i$ , ...
0
votes
0answers
37 views

Sorted result of a mod operation

Here is a fairly interesting but potentially unsolvable problem at stake. I hope it's in fact fairly well covered and known within modular mathematics. Let's suppose there is a segment of contiguous ...
2
votes
0answers
129 views

Finding maximum differences in an array of real numbers .

This is an algorithm design question which often appears in exams in a course that I take in the university . Suppose I have an array $A\in\mathbb{R}$ of size $n$ . I am required to find the ...
1
vote
1answer
49 views

Comparing factorials (From greatest to least)

Let's say we're asked to arrange these factorials in descending order: $1000!, \,\,700!\cdot300!,\,\,500!\cdot500!,\,\,600!\cdot300!\cdot100!$ For the first three, we could do: ...
-1
votes
1answer
19 views

Question about $N$ numbers sorting

Gonna use some help on this: I have $M$ channels lining up and each channel possesses $n$ users, with $n$ taking value from $1$ to $N$. I'm interested in such a situation: the numbers of users in the ...
6
votes
2answers
203 views

Average complexity of random-pick comparison sort

Motivation. Suppose we have a number of images that we want to arrange in a linear order from the prettiest to the ugliest. At our disposal we have a trained aesthete, whom we can show two pictures ...
0
votes
1answer
79 views

How many digits are in the bijective base-k numeral for n?

For integers $n \ge 0$ and $k \ge 2$, the following are equivalent: How many digits are in the bijective base-k numeral for n? If all the words on an alphabet of size $k$ are listed in shortlex ...
0
votes
3answers
187 views

Minimum number of exchanges

Suppose we want to arrange n numbers stored in an array such that all negative value occur before the positive ones. What will be the minimum number of exchanges in the worst case ? I tried it in the ...
0
votes
1answer
64 views

Question Understanding Simple Algebra With Regards to Computational Complexity

Initial Disclaimer: I decided not to post this on Stack Overflow as my problem lies with understanding the mathematics of this problem, but does not relate to theory at all. I am studying Parallel ...
1
vote
1answer
87 views

Why elapsed time is an exponential function of the number of elements in a vector that is sorted (MATLAB)

In the following script (that performs "bubble sort" on an row vector) it seems that the time elapsed when matlab executes the sorting depends exponentially on the number of elements in the vector. ...