# Questions tagged [sorting]

the algorithmic problem of ordering a set of elements with respect to some ordering relation.

908 questions
Filter by
Sorted by
Tagged with
1 vote
23 views

### Algorithm for grouping set items into ordered buckets without crossing boundaries between same set items

I'm trying to order some data in real-time (in an API call) where my item count is on the order of a few million. I'm using Go, so my pseudo code may resemble that. My input items look like this: <...
1 vote
44 views

### Diffucuty in understanding code after a recursive call

This is an example algorithm of a recursive insertion sort I'm trying to understand. I've have tried understanding this with the help of print statements (which I've commented). ...
1 vote
27 views

### Understanding crossover points in efficiency between insertion and merge sorts

Self-taught programmer here. I'm reading CORS, and right at the beginning, question 1.2-2, there asks a question: For inputs of size $n$, insertion sort runs in $8n^2$ steps, which merge sort runs in ...
1 vote
31 views

### Schoolclass Optimization Algorithm for finding Stable Matching

I have the task to write a program that puts students in classes and that in the best possible way. We have given the name, the foreign language a student chooses(french or latin), a profile (Music,...
31 views

### Hoare's partition original method

So I was reading the Hoare's partition part of the Quicksort wiki and it says: "With respect to this original description, implementations often make minor but important variations. Notably, the ...
17 views

### Subtrees of decision tree for comparison sort are recurrences?

Consider sorting on $n$ distinct elements, where all $n!$ permutations are possible. I think a decision tree for comparison sort can can be uniquely characterized as $T(a,n!)$ where $a$ is the ...
77 views

43 views

### minimum number of 2d elements whose sums across both dimensions satisfy some threshold

I have the following problem formulated as a linear integer program: \begin{align} & \text{minimize} && \sum_{i \in n} x_i\\ & \text{subject to} && \sum_{i \in n}{a_i}x_i \ge ...
1 vote
26 views

### Quicksort sampling

This question is in the context of quicksort. Consider that a subarray of distinct elements of size $k$ is sampled from the input array of size $n$, and then we choose a pivot from the sampled ...
215 views

### Sort doubly linked list with just manipulating pointers

Given doubly linked list $L$ that contains $n$ elements of numbers. Between QuickSort, and MergeSort and InsertionSort, which algorithm preferred to sorting $L$ by just swapping links of $L$? I think ...
18 views

### Algorithm to find best order for items on pages with a fixed height

I am looking for an algorithm to find the best order of items to fit on pages. Consider the following case, we have a page with the height = 300 We have images with the following heights - [150,200,...
23 views

### Algorithm to alternaly order elements in a list

So, I have N sets of objects of various sizes. I want to put them in order, in a way that's as much "alternative" as possible. For example, if I have 5 A, and 6 b, that's easy: B A B A B A B ...
37 views

### Compare list of parameters with each other and sort them from most to least selected

I want to sort the list of parameters (p1, p2, p3, p4, ..., pn) according to their importance. All parameters have to be compared with each other at best once, but not less than once. The person will ...
31 views

### Maximum Accumulated Balance after Purchasing Machines

A company is able to earn x dollars per day without any machines. However, there are n machines available for purchase. The <...
82 views

### Analysis of randomized algorithms

The expected running time, $T(n)$, of quicksort when the pivot is chosen uniformly at random satisfies $$T(n) \leq \mathcal O(n) +\frac{1}{n}\sum^{n-1}_{i=0}(T(i) + T(n - i)),$$ which leads to the ...
I am reading an algorithm book. Any comparison sort must make $\Omega(n\log(n))$ comparisons in the worst case to sort $n$ elements. Can we create a decision tree for any comparison sorting algorithm ...
In the comparison sort model of sorting, the fastest possible algorithm is order $n \log(n)$, where $n$ is the number of input numbers. What is the time complexity of sorting a list of natural numbers,...