Questions tagged [sorting]

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

313 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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" ...
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. ...
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).
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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,...
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}$ ...
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 ...
37 views

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 ...
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$ ...
71 views

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 ...
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 ...
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 ...
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 ...
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 ...
57 views

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 ...
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, ...
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 ...
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 ...
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 ...