Questions tagged [sorting]

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

Filter by
Sorted by
Tagged with
-1 votes
1 answer
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 ...
user avatar
9 votes
1 answer
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&...
user avatar
  • 93
6 votes
1 answer
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 ...
user avatar
  • 161
1 vote
1 answer
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: ...
user avatar
  • 13
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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?
user avatar
1 vote
4 answers
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
2 votes
1 answer
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. ...
user avatar
0 votes
1 answer
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 ...
user avatar
0 votes
2 answers
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}$, ...
user avatar
3 votes
2 answers
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 1
1 vote
1 answer
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 101
0 votes
0 answers
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 ...
user avatar
18 votes
5 answers
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 ...
user avatar
1 vote
2 answers
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 <...
user avatar
-1 votes
1 answer
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 ...
user avatar
  • 7
1 vote
1 answer
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. ...
user avatar
  • 71
3 votes
1 answer
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 ...
user avatar
  • 149
1 vote
2 answers
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$. ...
user avatar
1 vote
0 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 409
0 votes
3 answers
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 ...
user avatar
  • 11
0 votes
1 answer
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 ...
user avatar
  • 21
0 votes
0 answers
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 ...
user avatar
1 vote
0 answers
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$ ...
user avatar
  • 121
0 votes
1 answer
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 ...
user avatar
  • 345
2 votes
1 answer
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[0] and shifts all other elements to the right. For example: array = {1,2,3,4,5,6} --> shift(array, 3)...
user avatar
  • 23
1 vote
1 answer
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 ...
user avatar
  • 283
1 vote
3 answers
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 ...
user avatar
  • 283
0 votes
2 answers
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 ...
user avatar
0 votes
0 answers
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? ...
user avatar
1 vote
0 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
0 votes
2 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 1
3 votes
1 answer
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 ...
user avatar
  • 131
2 votes
3 answers
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 ...
user avatar
1 vote
3 answers
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: ...
user avatar
0 votes
1 answer
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.
user avatar
  • 171
0 votes
0 answers
16 views

change an algo to obtain optimal run time

I have an algorithm that does the reverse of partition ...
user avatar
  • 35
0 votes
1 answer
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 ...
user avatar
  • 171
1 vote
1 answer
357 views

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 ...
user avatar
  • 459
0 votes
1 answer
31 views

Bubble sort on an already sorted collection

When I look at the following algorithm, I believe I understand how bubble sort works. ...
user avatar
  • 317

1
2 3 4 5
18