# Questions tagged [sorting]

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

252 questions
0answers
15 views

### Isometric grid sort relation

I need to define relation function, which will for any two elements A, B return -1 if A is ...
1answer
43 views

### Is it possible to calculate how many Topological sortings exist for any given Graph?

Is it possible to calculate for any given graph, how many topological sortings exist? In this previous question, it is explained for a certain graph but I'm wondering if there is a more general way ...
0answers
33 views

### Recurrence in exercise divides and conquers

I am new to this site, I hope to contribute. For now i have the following problem of recurrences in a subject of discrete mathematics: Consider the algorithm, called StoogeSort in honor of the ...
0answers
12 views

### Discrete Math - Proving two sorted sequence properties.

Any ideas on proving the following problem will be appreciated! I think it has to do with the numbers of elements in the two lists, but I just can't figure it out. Let $X_1$, $X_2$, $\dots$, $X_{m+r}$...
1answer
37 views

### Sort two list of jobs result in minimum execution time

Two twins, James Johnson and Jonathan Johnson, work at a factory which produces bicycles. Their job is probably the most important one: James attaches the front wheel, and Jonathan does the same with ...
1answer
18 views

### Heapsort using MaxHeap and MinHeap

As I read in Introduction To Algorithms [3rd edition]: MaxHeap is used to sort an array into ascending order, while MinHeap is used to sort an array into descending order. And the tree below can be ...
0answers
34 views

### Does 'a graph is a DAG $\iff$ there exists a topological sorting' hold for graphs with a non-finite number of nodes?

Does 'a graph is a DAG $\iff$ there exists a topological sorting' hold for graphs with a non-finite number of nodes? I see this statement at a lot of places e.g. wiki. However it is not specified ...
2answers
246 views

### Sorting numbers with a special set of permutations

I'm wondering if there are well known sorting techniques for the following problem. Problem: Suppose you would like to sort a list of integer numbers $0, 1, 2, \ldots, d$. If one is only allowed to ...
0answers
49 views

### boxing algorithm problem

This is a bit of a computational algorithm problem, I am not entirely sure if here would be the right place to ask this, but here is the problem. I got some “containers” that each can hold 15, and I ...
1answer
52 views

### Topological Sorting

In some country, there are n flights among n cities. Each city has an exactly one outgoing flight but may have no incoming flight or multiple incoming flights. Design an algorithm to find the largest ...
1answer
21 views

### How to find the split in the given set of numbers.

Beforehand I would like to express apologies if this sort of question is not suited here, but I desperately need it answered. I have a set of numbers: [2, 5, 6, 2, 2, 81, 72, 77] From the above ...
1answer
57 views

### Empirical distribution of sorted Gaussian numbers

I wrote a small program that does the following : Pick $N$ independent standard Gaussian numbers (expected value : 0, standard deviation : 1). Call that list $L=\{y_1, \ldots, y_N\}$. Sort that list ...
0answers
42 views

### How to sort incidence matrix by the number of ones in two dimensions?

I have a set of "machines", each "machine" is described by a set of "tags". Not all tags present in all machines. How to find largest subset of tags and largest subset of machines, where each tag is ...
0answers
63 views

### Can you sort a list like $(1, 2, 0, 3, 1, 5, 1)$ without arbitrary swaps?

Background Imagine you have a tuple of integers, say $t=(1, 2, 0, 3, 1, 5, 1)$. Then you can order the list with your favourite sorting algorithm and obtain $t'=(5, 3, 2, 1, 1, 1, 0)$. An alternative ...
1answer
59 views

### Quick Sort Question

Can anybody please help me out with this sorting question? I am new to the topic of sorting algorithm and just trying to complete the same. Ques: Sort the below using Quick sorting algorithm 15, 10, ...
1answer
113 views

### Sort an array given the number of inversions

Given an array $A$ with $n$ integers in it, one way of measuring the distance of the array from a sorted array is by counting inversions. A pair of indices $i,j ∈ {0,...,n−1}$ is called an inversion ...
1answer
37 views

### Concrete Mathematics: Quicksort analysis

I'm trying to work my way through Concrete Mathematics (2nd Edition). I'm struggling to understand the transition for the analysis of the quick sort algorithm from the recurrence to the harmonic ...
0answers
31 views

### Does the transpose graph has the same number of topological sorts as the original graph?

I've just started Introduction to Algorithms, and I've encountered the following question: Let $G=(V,E)$ be a directed graph. Assume that G has exactly 1000 different topological sorts. What can be ...
1answer
77 views

0answers
23 views

### does it make sense to ask the expected value for discrete values ​in non-enumerable sets?

I want to know, is this question well formulated? If so, what is the answer? "Let randomly choose n numbers in a range [0,1], what is the expected value of the smallest number? if distribution ...
0answers
109 views

### ELO Rating as a sorting algorithm

Let $N$ be the number of players each with a true rating $R_i$, where $i \in \{1,2,...,N\}$. Two players, $A$ and $B$, are selected at random and made to play a game. Let their current ratings be $R_A$...
1answer
194 views

### How many ways can blocks be arranged in a grid

I have a 16x16 grid to fill up with 4 different sized blocks listed below: 16x16 16x8 8x16 8x8 How many different combinations of 16x16 grids can I make while filing the grid up completely? Just to ...
1answer
439 views

### recurrance with merge-sort

Trying to modify a merge sort by recursively splitting an array of size n into k sorted subarrays k > 2 and merging these subarrays. Time for merging is c(k-1)n. Specify the recurrence relation and ...
1answer
25 views

### Lower bound for asymptotic time of sorting algorithms

I am dabbling in sorting algorithms in my Algorithms course in university. Is there any proof for a lower bound on the asymptotic time cost of a sorting algorithm? Or, to word my question ...
1answer
383 views

### Insertion Sort Using Logical Operators

So i have stumbled across the following insertion sort algorithm for Matlab which works as it should: ...
0answers
49 views

### Finding an order-2 permutation that sorts colored balls

Suppose there are $M$ different colors of ball and you have $N$ of each kind. You arrange all of the balls in an arbitrary linear order. Is it always possible to find a permutation of order 2 such ...
2answers
968 views

### For which values of n does insertion sort beat merge sort?

I reading "Introduction to Algorithms", where I asked solve exercise (ex. below) "Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size $n$,...
0answers
48 views

### Inversions of a Deck of Cards

Suppose I have a deck of cards in some ordering. Consider all of the other possible orderings of this same deck relative to the first one. Is there a bound we can put on the maximum number of ...
0answers
223 views

### Sorting a graph's adjacency matrix by the *objectively* best edges for the TSP

Is there a way that I can take an adjacency matrix and sort the edges in terms of which edges are objectively most valuable (a best pick) for a TSP circuit? You cannot do it via sorting by lowest ...
1answer
25 views

### Question regarding the $\mathcal{O}$ notation used on constant functions

I'm having difficulties to understand the following passage out of the CLRS book, when the Counting Sort algorithm is introduced: Counting sort assumes that each of the elements is an integer in ...
2answers
61 views

### Writing an algorithm which takes $O(\log n)$ to run

there was a question in the exam as below: Let we have a sorted array consisting of $n$-many positive integers. Write a code that checks whether $k^{th}$ term is $k$ or not which takes $O(\log n)$ ...
1answer
20 views

### Sorting numbers into bins, with a variable offset

This is for a personal project. I have a start number, and an interval. The start number will stay the same while sorting, but I can't know what it is ahead of time. For start number = 50,000, and ...
1answer
28 views

### Number of Queries to determine Order of Integers

I have this question as follows: The eight numbers $11,...,18$ are in a database in some order. You can query any subset of indices, but the reply will be randomly shuffled. For example, if ...
0answers
40 views

### Efficiently Filling A Two-Dimensional Space

I was wondering if there is a formal name for an equation I am dealing with at work. For the problem, I am given five values (for example) that are dimensions in the form of $(x,y)$ (width of a page, ...
1answer
36 views

### Prove that the minimal number of comparisons to merge two ordered sequences of length 2 and 5 is 5

I would like to prove that $5$ is the minimal number of comparisons needed to merge two ordered sequences of length $2$ and $5$. I'm preparing for an Algorithms test and this is a problem that ...
1answer
422 views

### Algorithm to determine minimum of swaps to make two binary arrays identical

Is there a known algorithm or formula to determine how many swaps are to make a binary array A look like B? For example if: ...
1answer
29 views

### How to find the position of an element in a vector

Given the vector: $$v=[a_1,a_2,\ldots,a_N]$$ where $N\in\mathbb{N}$ and $v_j\in\mathbb{R}$ with $a_j\lt a_{j+1}$ and given a number $b$ with $b\in\mathbb{R}$ what is the fastest algorithm to find the ...
1answer
21 views

### sorting sets of triangulation

I have two sets of triangles: $A = \{[(0,0),(1,0),(1,1)], [(1,0),(1,1),(2,1)], [(2,1),(1,0),(2,0)]\}$ and $B = \{[(1,0),(0,0),(1,1)], [(2,1),(1,0),(2,0)], [(2,1),(1,1),(1,0)]\}$ What algorithm can ...
1answer
86 views

### Bounds on computational complexity of a sorting algorithm

Assume that you are designing a sorting algorithm that uses an operation $x \leq y$ that have 3 possible results: • $x < y$ • $x = y$ • $x > y$ Can your algorithm do better than \${\cal \...
5answers
900 views

### Expected number of items looked at

Currently failing at basic probability… Given a sequence of items, linear search means looking at each in turn and seeing if it's the one we're looking for. (I.e. in the worst case, it's the ...