# Questions tagged [sorting]

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

852 questions
Filter by
Sorted by
Tagged with
42 views
+50

### What is a good model for predicting which item the user will select from a list?

I have a list of apps the user has installed, a history of all previously opened apps, and a series of characters that the user has input. The user is shown a list of apps filtered taking into account ...
1k views

### Algorithm for merging arrays while keeping their order

My question is generalizable to arrays of any type but I'll use strings to keep it short. We take a couple of strings as an input. Let's denote them ${S_1,...S_n}$. (Ex: "ABEF" and "CDE&...
92 views

### Permute rows of a matrix to minimize total number of inversions of its column vectors

Let $A$ be an $n \times k$ matrix of real numbers. I'm looking for an exact algorithm to find a permutation of the rows of $A$, in such a way that the total number of inversions found in the resulting ...
1 vote
41 views

### Compare solutions of counting sort

I was looking for implementations of counting sort and most of them are implemented with cumulative counts like this: ...
37 views

### Given a 2D Array (of 0's and 1's), find the minimum number of rows required so that maximum columns have their sum greater than a threshold

I have a 2D array of some rows and columns which are having only 0's and 1's. I would want to know if there is a way to optimize the number of rows so that maximum number of columns have their column ...
1 vote
26 views

### Sampling unique records from a large dataframe

Suppose we have a dataframe with ~10M rows with ~9M duplicate records. What is the most time efficient way of selecting the unique records from this dataframe? Some sort of sampling algorithm?
1 vote
421 views

### Stable sort an array with k distinct elements, each appearing double the times the previous one appears

I've started with thinking of a bucket sort/radix sort variation, only to be disproved by a colleague. Here's the problem: Given an array with $k$ distinct elements, it is known that the smallest ...
79 views

### I think I have discovered a new sorting algorithm using binary search tree [closed]

If we some how transform a Binary Search Tree into a form where no node other than root may have both right and left child and the nodes the right sub-tree of the root may only have right child, and ...
134 views

### Sorted list of counters in constant time

Summary. A data structure maintains in constant time a sorted list of counter values, for a dynamic set of counters. I am interested in references using this structure, and in possible improvements. ...
49 views

### Algorithm for generating sorted lists of random floats

More out of curiosity than anything else. I know you can always generate a list of random numbers and then sort it, but I was wondering if there exists a (pseudo)random number generator whose output ...
153 views

### Finding Median value given a tuple (value, frequency) in O(n) worst case time complexity

An accountant in a big firm would like to find the median of the salaries of all employees. The data they received is a list of size n containing the tuples $\left\{s_{i\ },f_{i\ }\right\}_{i=1}^{n}$, ...
289 views

### Number of Inversions found in Selection sort vs Exchange sort

Exchange sort is similar to selection sort, just swaps "overly eagerly" instead of finding the minimum and doing only one swap. And the swaps affect how often the ...
58 views

### Is it faster to use Counting Sort to lexicographically sort characters in a word in Python?

Assuming I have very long words, is it worth it to use Counting Sort with its memory overhead to achieve linear time complexity? I wrote a Python function that sorts the characters in a given string ...
1 vote
80 views

### How to find wiggle sortable arrays? Did I misunderstand John L.s' answer?

I have read following answer and question How to wiggle sort an array in linear time complexity?. But while reading I came up with a question. I can't comment on answers yet, so I decided to make an ...
30 views

### Sorting optimization to presorted array

I'm looking up the complexities of sorting algorithms. There can be performance harm when the array is already presorted when running certain algorithms. E.g. Using last element as pivot in quick sort ...
25 views

### Where is external sorting used beyond databases?

I am trying to find applications/systems that use external sorting techniques or avoid external sorting by using other methods to achieve a task. I know most relational databases (like PostgreSQL or ...
3k views

### "partial sorting" algorithms (aka "partitioning")

Context: When trying to tame real-world datasets that contain outliers and noise, the interquartile mean is a handy tool: you sort the data, throw away the top and bottom 25% of the data and take the ...
1 vote
199 views

### Unique combinations of growing collection elements

Initial collection A = [1,2,3] should provide such combinations: {(1, 2), (1, 3), (2, 3)} I want to pop the first combination <...
111 views

### Is there an O(m (log n+ log m))-time algorithm that finds k-th smallest element in a row-wise-sorted two dimensional array?

I prepare for entrance exam and try to practice some hard problems. The following nice problem is problem 1(c) of this problem set. Suppose we are given a two-dimensional array $A[1...m][1...n]$ in ...
1 vote
124 views

### Efficient sorting an array generated from random distribution

I need to sort an array of n real numbers that was randomly generated in this way: I have a given set of k closed intervals: [a1,b1],[a2,b2],...,[ak,bk] whose beginning and end are natural numbers. ...
153 views

### Greedy filling unit intervals

I have unit intervals given such as $I = \{\{s_1, s_1 + 1\}, ..., \{s_k, s_k+1\}\}$ ($\forall s_i \in \mathbb{R}$). I am given a list of $X$ reals, such that each of the reals belongs to at least one ...
1 vote
135 views

### Sorting segments from high to low

I have a set of segments. None of them intersect or touch each other, and none of them have slope $0$ or infinity (i.e. the endpoints have different $x$ and $y$). All segments have length $> 0$. ...
1 vote
82 views

### Sorting in linear time using Trie data structure

I have written an article on a new way of non comparison sorting and I want it to get peer reviewed. The sorting algorithm uses Trie data structure to store digits of numbers as nodes and iterating ...
1 vote
50 views

### uniformly distributed edge weights in an MST

Suppose that the edge weights in a graph are uniformly distributed over the halfopen interval [0, 1). The question is, how can one sort the edge weights in linear expected time? I know the ...
42 views

### Understanding TAOCP paragraph "Will Keysorting help" in "external" sorting?

Near the end of subsection 5.4.9 Disks and Drums in 5.4. External Sorting, a process is sketched in a paragraph headed Will Keysorting help?: Schematically, the process has the following form: stage ...
34 views

### Why is the time complexity of introspective sort O(n log n)?

I understand that intro sorts avoids the running time O(n^2) of quick sort, by changing to heap sort when the algorithm exceeds a certain recursion depth. But what about insertion sort? It kicks in ...
1 vote
43 views

### Sorting lower bound is linear when only a constant number of distinct keys?

I saw this proposition on Sedgewick's lecture slides on QuickSort, and I've been wondering why the number of comparisons is linear in the case of a constant number of distinct keys. I tried to ...
1 vote
21 views

### Sorting a list over rounds of binary comparisons

You have a list of $n$ items you want to sort over $r$ rounds using binary comparisons. In each round, you specify $k$ binary comparisons to be made in parallel. The objective is to fully sort the ...
100 views

### Fastest Algorithm for "Merge" step in Mergesort

Given two sorted arrays $a_1,a_2,\dots,a_n$ and $b_1,b_2,\dots,b_m$, merge them together into one sorted array $c_1,c_2,\dots,c_{n+m}$ containing the elements of $a$ and $b$. The typical mergesort ...
76 views

### Is there a solution faster than O(n^2) for this greedy/sorting problem?

In a market there are N different items where each item is unique and identified by id (1-N). There are also K buyers with names (1-K). Each buyer has 2 items that they want to buy (A, B), where A is ...
22 views

### Best way to sort two arrays in correspondence in a manner that coordination between them does not change

Let me put it this way. I have two arrays A and B. Array A contains manufacturing dates of cars, and Array B contains corresponding car model names. A and B are in correspondence. Now I want to sort ...
1 vote
92 views

### Maximize the sum of weights of covered intervals

Suppose we are given $n$ open intervals $(a_1, b_1), \dots, (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$ ...
47 views

### Sorting N dimensional data

What would be a good choice for a key to sort a complex number $(a+ib)$ or any $n$-dimensional data for that matter. Is using the magnitude of that vector a good choice rather than using any one of ...
50 views

### Finding the smallest amount of function operations to sort an array

Let's say we have a function shift(array[], int s) which swaps the position of array[s] to array and shifts all other elements to the right. For example: array = {1,2,3,4,5,6} --> shift(array, 3)...
1 vote
48 views

### Examples of comparison-based algorithms that are not a sort or a search over lists

Can you share examples of comparison-based algorithms used in practice that are not a sort or a search over lists? Heapify is an example of a comparison-based algorithm that is neither a sort nor a ...
1 vote
142 views

### Best-case time: comparison-based sorting on a list of size n must make n-1 comparisons (reference to proof)

I am looking for a reference to a proof that for every list of size $n$ comparison-based sorting cannot make less than $n-1$ comparisons. Do you have a reference of a book that covers it (with page ...
24 views

### Searching for sorting algorithm taking into account all possible solution of similar numbers

I need a reference for sorting algorithm where all possible orders are considered. example: if we have four values of n, and we do know there values n1(3) n2(5) n3(5) n4(10) and want to order them in ...
107 views

### Is there a difference between Heapify and Bottom-Up/Top-Down heap construction, when using array representation of binary tree?

Won't both the methods ultimately give a max/min heap? So if I am given a binary tree, as an array, and am asked to convert it to a max heap, can I just use the bottom up construction of the heap? ...
1 vote
21 views

### (Branchless) Bitonic Sorting Network for a Set of Floating Point Numbers

In the past I've implemented a branchless Bitonic Sorting Network on a gpu using CUDA, for integers. I am facing a related problem: In my Order Independent Transparency implementation, I would like to ...
1 vote
34 views

### How can vector angle comparison between lattice points be done without using floating-points? (Convex Hull)

Let's say I have a point $(x_0, y_0)$, and some other points $(x_1, y_1), (x_2, y_2) ... (x_n, y_n)$, such that all of them are lattice points; all have integer coordinates. Let's further assume that ...
93 views

### Quicksort with insertion sort

Okay so I have implemented quicksort with insertion, where K is a value until which the recursion occurs and then rest of the array is sorted using insertion sort. Now I am comaparing 3 different ...
58 views

### Prove the worst case runtime of the cocktail shaker sort is $\theta(n^2)$

Question: Prove the worst-case running time of the cocktail shaker sort is $θ(n^2)$ by demonstrating that the sort is $O(n^2)$ and $\Omega(n^2)$ in the worst case My attempt: I believe I am supposed ...
60 views

### List of algorithms that depend on sorting / ranking / argsorting

I am looking for a list of algorithms that depends on sorting / relative ranking / argsorting, not for a list of sorting algorithms. I want to study and illustrate the importance of fast sorting in ...
64 views

### Number of comparisons for mergesort

In their book An introduction to the Analysis of Algorithms, Flajolet and Sedgewick analyze the number of compares performed by Mergesort along the following lines. They denote by $C_N$ the number of ...
1 vote
718 views

### What could be the most efficient algorithm to compare two unsorted arrays?

I have two arrays A and B of the same length n. I am looking to swap such that all the elements of array A are less than each element of B. Elements in A and B can be unsorted. Example Inputs: ...
38 views

### Average number of comparison for 3 items

What is the average number of comparisons performed when sorting 3 items? The question is based on the above picture.
16 views

### change an algo to obtain optimal run time

I have an algorithm that does the reverse of partition ...
19 views

### Proof the recurrence relation of order statistics using induction

I read order statistics from the book The Design and Analysis of Computer Algorithms", by Aho, Hopcroft, Ullman, Addison-Wesley As per the algorithm the recurrence relation given T(n)<= cn for ...
1 vote
### Lower bound on comparison-based sorting of $k$-sorted arrays
In $k$-sorting array algorithms, every element is supposed to be $k$ positions from its correct positions. So with that in mind, if we used a randomized QuickSort, we will have $O(n\log{n})$. Now to ...