Questions tagged [sorting]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
18 views

How can be called a numerical table whose columns are sorted?

I have found a pattern within some of my tables in a thesis. Sorting in a given column "f.05" in this case turns out to make it such that you cannot distinguish what column the table is ...
0
votes
0answers
14 views

Bubble Sort, Selection Sort from descending to ascending

I need to solve following questions: A sequence of numbers is to be sorted in ascending order, is already sorted in descending order. How many comparisons and permutations do Bubblesort and Selection ...
0
votes
0answers
17 views

Unique distribution of participants across tables

I am trying to help a friend solve a problem. He has a tiny startup for dating meetups where a number of people=n, males=m, females=f, sit at tables and talk for a time period across "s" ...
1
vote
1answer
75 views

How do I prove by using induction on k, that MergeSort uses $n(\log_2(n)+1)=2^k(k+1)$ comparisons?

I have been asked this question in an assignment for my exam. The assignment question is: "Assume that Merge uses (exactly) $a+b-1$ comparisons to combine two lists with a and b elements. ...
-1
votes
0answers
12 views

insertion sort time complexity where all elements are same

What would be the time complexity, in the worst case, of insertion sort for an array of length n, where all the elements are the same (basically n copies of the same element).
0
votes
0answers
94 views

Transactions & Schedules

The below transactions are given : and the below schedules : Give the respective dependency relations as well as the precedence graphs. Which schedules are conflict serializable? Which schedules are ...
1
vote
0answers
20 views

Maximize the sum of weights of covered intervals

Suppose we are given n open intervals $(a_1, b_1)$, ..., $(a_n, b_n)$, with interval $i$ being assigned a weight $w_i$ for all $i$. We are given an integer $k<n$, and we are allowed to choose $k$ ...
0
votes
0answers
24 views

How to prove if a list is sorted if any two consecutive elements are sorted?

To check if a list is sorted, a typical approach is to check every element and its next element, and see if they are sorted. Intuitively, I understand it is correct. But is there a more mathematical ...
0
votes
0answers
30 views

average number of comparisons in Quicksort

If there is anyone who is familiar with Quicksort try to help me to understand the following. I am taking specifically some text from the book 'The Concrete Tetrahedron' Manuel Kauers . Peter Paule ...
24
votes
1answer
385 views

Average swaps needed for a random bubble sort algorithm

Suppose we have $n$ elements in a random permutation (each permutation has equal probability initially). While the elements are not fully sorted, we swap two adjacent elements at random (e.g. the ...
0
votes
0answers
5 views

Grouping/Sorting using matrices. Large number of Items and unknown number of groups.

I have a program that reads user entries and needs to appropriately group them. The user entries are NOT exact each time. Entries are strings(text). I have a function that compares 2 strings and ...
0
votes
1answer
66 views

Minimize the absolute difference of the sum of two dijoint sets in which terms are in the powers of $p$.

Given $n(n>=1)$ integers $k_1,k_2 \cdots k_n(k_i>=0)$, and an integer $p>=1$, Johny picks $p^{k_i}$ from $i-th$ category for each category , and he wants to divide them into two disjoint sets,...
0
votes
0answers
68 views

De-Bruijn Graph and Topological sort

Let $𝐺_{σ,𝑛} = (𝑉, 𝐸)$ be a De-Bruijn graph corresponding to a De-Bruijn sequence decoding all the words of length $n$ over an alphabet $∑$ of size $σ$. Recall that $𝐺_{σ,𝑛}$ has $σ^{n−1}$ ...
4
votes
1answer
64 views

distance between sorted arrays

Assume we have two arrays of real numbers: $$ X = \{x_{1}, x_{2}, \dots, x_{n} \} $$ and $$ Y = \{y_{1}, y_{2}, \dots, y_{n} \} $$ Next, assume that $d = \max(|x_{i} - y_{i}|)$. Next let us sort both ...
1
vote
1answer
37 views

prove $T(n)=max_{1\leq q\leq n-1}(T(q)+T(n-q))+\theta(n) \\~\\ \Longrightarrow T(n)=O(n^{2})$

let $T(i)$ denote the worst-case running time of QuickSort algorithm on an input of size $i$. Then, the recurrence for the worst-case running time is given by: $$T(n)=max_{1\leq q\leq n-1}(T(q)+T(n-q))...
0
votes
0answers
26 views

I am looking for a formula to sort a database by 2 values, both should be as big as possible but balanced

I have a database on spreadsheet and it looks like this: ...
0
votes
0answers
19 views

Minimum number of subsets of rectangles such that no rectangle fit in any other rectangle

Largest subset of rectangles such that no rectangle fit in any other rectangle After reading this article, I wonder whether we can find the minimum number of subsets sastify that condition with the ...
1
vote
0answers
31 views

Sort an array of numbers in a specific order using an algorithm

I'm working on a Discord bot that lets users build a base in isometric perspective. For this, I add images of buildings on top of a background with a grid. To make sure the buildings in the front are ...
0
votes
0answers
33 views

Shop priority to buy cake ingredients

Let's say I want to make a cake. I'll need flour, eggs, milk, chocolate and strawberry sauce. I have a selection of different shops around my house but not all shops have all the ingredients or at the ...
2
votes
1answer
31 views

Non-comparison based sorting algorithm based on "Number of unique integer in random generated arrays"

I have asked questions about Number of unique integer in randomly generated arrays. Suppose we have $10^6$ random generated numbers, we should have about $~6*10^5$ unique numbers. I wrote a custom ...
6
votes
1answer
167 views

An expected value puzzle

While working on a larger problem, I encountered this smaller problem that I’ve enjoyed thinking about, but have yet to solve. Shuffle the numbers 0 to 24 into a 5 by 5 matrix. Sort each column in ...
1
vote
1answer
33 views

Proof that mergesort uses $\sum_{1\le k < N}(\lfloor\lg k\rfloor+2)$ compares to sort $N$ elements

In the book "An introduction to the Analysis of Algorithms" by R. Sedgewick and P. Flajolet, There is this exercise Exercise 1.4 Develop a recurrence describing the quantity $C_{N+1} − C_{N}...
4
votes
1answer
53 views

Proof of Mergesort $N$ elements with $N \log N + O(N)$ comparisons

In the book "An introduction to the Analysis of Algorithms", written by Robert Sedgewick and Philippe Flajolet during the proof of the Theorem 1.1: (Mergesort) To sort an array of N ...
1
vote
1answer
25 views

Are there compare-based sorting algorithms that are faster than n lg(n) by some constant factor?

Is it possible to have algorithms that sort using, say, $1/2 * N*lg(N)$ compares? Essentially, I am confused because I have seen the $N * lg(N)$ lower bound on sorting written in both tilde and big-...
0
votes
1answer
40 views

Ranking objects using least squares

I need to develop an application to automatically rank objects. This is the use case: I have a set of objects, all of which have the same set of properties. For example, a set of cars, all of which ...
1
vote
1answer
48 views

Picking $2k$ sets from a $2^k$ collection under $2$ constraints

Assume we have a collection of $2^k$ different items and we need to pick $2k$ sets of different items out of it under the following constraints: Each item must be picked at least in $2$ sets. The ...
0
votes
1answer
34 views

sorting of infinite positive vector from $\ell_{1}$

Let us consider the sequence space $\ell_{1}$. Next, let $\mathcal{X} \subset \ell_{1}$ be a subset of $\ell_{1}$ of all vectors with non-negative elements. Can we then define operator $f: \mathcal{X} ...
2
votes
2answers
217 views

Arranging numbers in an array (Swedish Math Olympiad 1986)

Consider an $m\times n$ array of real numbers. Let $d>0$. Suppose that the difference between the maximum number and the minimum number in each row is at most $d$. We then sort the numbers in ...
1
vote
0answers
17 views

When is longest increasing subsequence at least N/2 long?

When analizing some algorithms I came up with this problem. Suppose we have a sequence a with N elements. The goal is to find (aproximately) the ratio of #{permutations of a s.t. the LIS is at least N/...
1
vote
1answer
19 views

Count the specific amount of steps in a sorting algorithm with given pseudo code

I need to count the specific amount of steps which are used by sorting algorithm pseudo code. Here are some guide lines given: a:=1 is considered 1 step a:= b + c is 1 step a:= b + c - d is 2 steps ...
1
vote
1answer
79 views

Sorting balls into groups

Given 26 balls, 8 of them red and 18 of them blue, and 3 distinct, labeled groups to sort them in, how many different combinations can we make that satisfy the following conditions: All balls are ...
1
vote
1answer
103 views

How to sort a permutation cycle in the mapping form?

Consider a cycle $(6\; 1\; 4\; 3\; 5\; 2 )$ of a symmetric group $S_n$ of degree $n$. This implies $6$ maps to $1$, $1$ maps to $4$, $4$ maps to $3$, $3$ maps to $5$, $5$ maps to $2$ and $2$ maps ...
0
votes
1answer
59 views

Insertion Sort Running Time Complexity

In the worst case, $j$ comparisons are required to insert the $jth$ element into the correct position. For the insertion sort algorithm, the running time complexity would be $\mathcal{\Theta}(n^2)$ ...
1
vote
1answer
832 views

How many comparisons does the insertion sort use to sort the lists in question

I have two lists to sort using insertion sort: How many comparisons does the insertion sort use to sort the list $n, n − 1, . . . , 2, 1$? How many comparisons does the insertion sort use to sort ...
3
votes
2answers
171 views

Sorting an array to get the maximum combined sum of the differences between every two adjacent elements

This is related to this question: Stack Overflow Problem description We are given a sequence of n positive integers. How to sort the elements to get the maximum combined sum of the differences between ...
0
votes
1answer
19 views

Minimum Absolute Difference in a List of Integers

Finding the minimum absolute difference in a list of integers by comparing each possible pair in the list is inefficient due to the number of comparisons required. If we sort the list first, then ...
1
vote
0answers
33 views

Balanced splits in Randomized Quicksort

I am reading about usage of Chernoff bounds for bounding number of comparisons in a randomized Quicksort from here. What is proved is that ($n$ is number of elements in the array) $$\Pr[\text{Number ...
1
vote
2answers
36 views

Searching/Sorting Algorithm

I just started studying algorithms and data structures and came across this problem: Given $x \in \mathbb{N}$ and two integer Arrays $A_1$ and $A_2$ each of the length $n$. Write an algorithm in ...
1
vote
2answers
21 views

A machine can compare at most three integers in one run. Show that at least $k(n) := \lceil log_6(n!) \rceil$ runs are needed to sort $n$ integers.

My idea is to use a proof by induction on $n$. For $n = 1,2,3$, $1$ run is needed so we are done. Assume the statement is true for sets of $n$ or less integers, $n > 3$. Let $S$ be a set of $n+1$ ...
0
votes
3answers
71 views

Reordering task

I'm trying to solve tiny task within a c++ algorithm but don't want to reinvent the wheel and looking for a math way. Imagine a row of people when some of them are changing their positions by their ...
0
votes
0answers
823 views

Algorithm for Liquid sort puzzle

I recently came across this game and it is really interesting. https://play.google.com/store/apps/details?id=com.picolaf.liquidsortpuzzle&hl=en_US&gl=US The goal here is to sort the liquid of ...
-1
votes
1answer
395 views

Median-of-$3$ quicksort probability

Consider modifying the Partition procedure of Quicksort by randomly picking three elements from array $A$ and use the median of the three elements as the pivot. What is the exact probability (not ...
0
votes
1answer
158 views

How to find minimum number of switches to sort a given permutation(let's say 1-10) in ascending order

King Arthur has a shelf with $10$ books, numbered $1,2,3,\dots,10$. Over the years, the volumes got disordered. Arthur tries to order the books in the increasing order by exchanging positions of two ...
3
votes
2answers
162 views

Difficult word problem, looks like statistics/combinatorics. Having trouble making progress

"A trader has discovered a source of 1000 unique types of stamps which she can buy in bulk and then sell to a network of 100 merchants through an intermediary. No matter what type of stamp, she ...
0
votes
2answers
57 views

Could you please help me understand the logic behind the 'New Years Chaos' question?

This is a coding challenge, but first I need to understand the problem and the solution from a purely thought/logical point of view. I kind of worked out how to find the people in the list who have ...
3
votes
2answers
70 views

Deriving an evaluation metric for how out of order an ordering is compared to ground truth?

Let's say we have an unsorted list and we know what the sorted list looks like (ground truth). What are some metrics we could employ to quantify how badly unsorted our list is? i.e. How bad is [4, 5, ...
0
votes
1answer
52 views

$(N^2 - 1)/(N - 1) = N+1$ and its relation to sorting square matrices.

I'm working on a problem that involves sorting the members of square matrices into groups. Here are the sorting rules: Group size equals the square root of the number of members in the matrix Every ...
1
vote
1answer
48 views

Generating function of recursive algorithm with random subcalls

I was presented with the following algorithm. As input the algorithm gets an array of length $n \geq 0$. If $n \geq 2$ then for each $k \in \{1, 2, ..., n\}$ the algorithm calls itself recursively ...
1
vote
1answer
59 views

Efficient algorithm for computing the number of ways $a$ and $b$ from different ordered sets can be summed such that $a + b \leq x$, $x \in Z$

Let $A$ and $B$ be ordered (ascending) sets of integers, and let $x \in Z$. Design an efficient algorithm (in # of steps) for computing the number of different ways an element of $A$ can be summed ...
0
votes
2answers
267 views

Sorting Algorithm Proof

Hydrosort is a sorting algorithm. Below is the pseudocode. ...

1
2 3 4 5
7