Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [sorting]

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

0
votes
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 ...
2
votes
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 ...
1
vote
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 ...
0
votes
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}$...
0
votes
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 ...
0
votes
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 ...
1
vote
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 ...
2
votes
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 ...
0
votes
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 ...
0
votes
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 ...
1
vote
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 ...
1
vote
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 ...
2
votes
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 ...
3
votes
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 ...
0
votes
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, ...
3
votes
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 ...
1
vote
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 ...
0
votes
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 ...
3
votes
1answer
77 views

Quantity of same numbers in same positions of permutations and its resort

If we resort numbers in permutations of length $n$ by their positions, ex. $12=12, 21=21$ $123=123, 132=132, 213=213, \color{red}{231=312}, \color{red}{312=231}, 321=321$ $1234=1234, 1243=1243, ...
0
votes
0answers
16 views

Two dimensional sorting: finding $\max_\sigma \langle M^\sigma,C\rangle$ for permutation function $\sigma$

Suppose that we have a non-negative matrices $C,M\in \mathbb{R}^{m\times m}_{\ge0}$. Also suppose $\sigma:[m] \rightarrow [m]$ is a permutation of $\{1,2,...,m\}$. We want to find the permutation that ...
0
votes
2answers
36 views

What is the name of shorting algorithm used? [closed]

For example, Set X = { Apple = 1, Banana = 2, Cucumber = 3 } Set Y = { CFO = 1, CFO = 2, CSO = 3 } Combinations are in some order [X, Y] = K [1, 1] = 1 [1, 2] = 2 [2, 1] = 3 [1, 3] = 4 [2, 2] = 5 [3,...
0
votes
0answers
20 views

Asymptotic time complexity, Big oh and Theta analysis. Is this a trick question though

Here's the question: Consider the following sorting algorithm: I. Insert the given input A[1], A[2], ..., A[n] into a binary search tree T in the given order, starting from an empty tree; II. Do an ...
0
votes
1answer
55 views

Why am I unable to observe $O(n^2)$ time complexity with Bubble Sort?

I am seeking to confirm that Bubble Sort has an average performance of $O(n^2)$ I wrote the following code in Python. bubble_sort takes a list of size $n$ and ...
2
votes
1answer
72 views

How to order the set of all graphs?

When trying to figure out how to order the set of all graphs, it seems obvious to me that graphs with fewer nodes come before graphs with more nodes, and that among graphs with equal nodes that graphs ...
1
vote
0answers
126 views

How to apply merge sort to nxn matrix [closed]

For example take the below matrix, it has been sorted, The sorting algorithm needs to be merge sort. Merge sort is basically a divide and conquer strategy, I do not exactly know how to divide a matrix ...
1
vote
1answer
62 views

Permuting with Sinkhorn normalization: find $\sigma$ s.t. $\bf{min}\frac{dS}{dp}\rightarrow \bf{\sigma} \times \bf{X'}= \bf{X}$

I have a matrix of samples vs. features and would like to organize or permute the features such that the sum of the first derivative along these features is minimized for all of the samples within the ...
0
votes
0answers
22 views

Prove the maximum sum of products algorithm

We are given two equal sized sets of positive integers (n integers). We can multiply any two numbers from different sets, each number being used once. All multiplied pairs are added. Prove that ...
0
votes
1answer
40 views

symmetric difference of two sorted lists in parallel

We can merge two sorted lists of distinct elements in parallel using the merge path concept: See https://www.cc.gatech.edu/~bader/papers/GPUMergePath-ICS2012.pdf and: https://www.researchgate.net/...
0
votes
0answers
277 views

Average case complexity of insertion sort?

I have no idea how $p_j(k)$ and $X_i(k)$ are combined into $$\sum_{k=1}^{i}p_i(k)\cdot X_i(k),$$ such that it's $E(X_i)$, is it possible to visualize the process? My confusion are: Since $a_1,a_2,\...
1
vote
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 ...
2
votes
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$...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
1
vote
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: ...
5
votes
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 ...
0
votes
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$,...
0
votes
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 ...
1
vote
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 ...
0
votes
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 ...
-2
votes
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)$ ...
0
votes
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 ...
3
votes
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 ...
0
votes
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, ...
0
votes
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 ...
0
votes
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: ...
0
votes
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 ...
0
votes
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 ...
1
vote
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 \...
6
votes
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 ...