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

learn more… | top users | synonyms

0
votes
0answers
14 views

number of call randomized partition function in quick sort

If the number of calling randomized partition function in the array of n elements name $C(n)$ I know that $\frac{n}{2} \leqslant C(n) \leqslant n - 1$ and the question is show that for every number ...
0
votes
1answer
36 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
16 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
21 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
13 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
62 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, ...
0
votes
0answers
47 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
22 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
40 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
29 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
30 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. ...
3
votes
0answers
37 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.
10
votes
1answer
97 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 ...
1
vote
1answer
126 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
63 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
54 views

Why is the sentence true?

I am looking at the algorithm of the insertion sort: ...
0
votes
1answer
36 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
63 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
55 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
54 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
25 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
428 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
28 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
116 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
53 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
35 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
120 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
47 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: ...
0
votes
1answer
17 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
199 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
71 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
164 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
61 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
77 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. ...
6
votes
1answer
137 views

Reference Request on Order Theory topics

I am looking for some references (especially a good recent book) that covers important topics involving partial orders such as: order polytopes, sorting/selection in partially ordered sets, upper and ...
1
vote
1answer
546 views

What is meaning of strict weak ordering in layman's term?

I gone through many pages using Google, but not understand exact meaning of Stick-weak Ordering term. I have this requirement while sorting strings. Thanks.
1
vote
1answer
52 views

Minimization of difference

Given two lists $\{a_1,a_2, \ldots,a_n\}$ and $\{b_1,b_2, \ldots,b_n\}$ and you can rearrange elements in each list individually. You have to rearrange element in it in such a way value of S is ...
1
vote
0answers
25 views

Redistribution Algorithm

I've one thousand buckets of different sizes. Each bucket consists of red and blue balls of different weights. I know that 60 percent of the total ball weight comes from the red balls and 40 percent ...
1
vote
2answers
113 views

Probability of a sorted sequence

Now I tried tackling this question from different sizes and perspectives (and already asked a couple of questions here and there), but perhaps only now can I formulate it well and ask you (since I ...
1
vote
1answer
40 views

Array sort input

Suppose that there is an algorithm which sort a sequence of $n$ elements $$a_1, a_2, ..., a_n$$ Each of the $a_i$ is chosen with probability $1/k$ from a set of $k$ distinct integer numbers. Is it ...
1
vote
1answer
261 views

Sorting Numbers into Groups

I have a list of numbers N1,N2,N3………… The list must be grouped into groups of 3 G1,G2,G3….. The sum of Each Group must be >= X, The sum of Each Group must be <= Y I understand that there may be ...
0
votes
1answer
77 views

Formula for sorting a list of two values

I have one problem during building my online service and need your help: I have a list of workers who are working on some task. They can be rewarded for their results or not. Of course they try to ...
0
votes
0answers
478 views

Packing rectangles in a grid

I have a problem that, discovered today, may be called "rectangle packing". I found extremely interesting references to papers in this question. But the rectangles I want to pack have dimensions that ...
0
votes
0answers
122 views

Worst case lower bound for comparison sort

It is known that in the worst case comparison sort takes $\Omega(nlgn)$ of time for n elements. Let's say I'm given $n$ elements as input to sort. Each input sequence of $n$ elements has $n/k$ ...
0
votes
1answer
44 views

how to sort a matrix in matlab

I have matrix like= 1 10 2 0 1 5 9 7 50 5 7 13 87 3 10 9 54 90 60 2 25 16 0 1 0 25 3 but after sorting the matrix will look like 0 1 1 2 5 7 9 10 50 3 5 7 9 10 13 54 87 ...
1
vote
1answer
2k views

Compute number of comparisons in quicksort pivoting on median or third

With a few friends we read the Algorithm Design Manual from Skiena. One of his (chapter 4) exercises asks for the number of comparisons that the quicksort algorithm does (comparing an element to the ...
1
vote
2answers
80 views

Could graph theory aid in the understanding of comparison sorting algorithms?

I am interested in computing the exact number of comparisons that are needed to sort a list. See this wikipedia article. Up to $n=15$, we know how many comparisons between elements one must make to ...
1
vote
1answer
196 views

Is there an optimized version of rectangle packing algorithm?

I have a rectangle with 200 width and 100 height. I have a mix pool of 50 rectangles and boxes. The rectangles comes in shapes like 20x40, and 40x20. The boxes will come in shapes of 20x20 and 40x40. ...