Questions tagged [sorting]

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

Filter by
Sorted by
Tagged with
-2
votes
1answer
22 views

Is this radix sort implementation in-place or out-place?

Below is the implementation of Radix Sort in python taken from here ...
1
vote
1answer
27 views

Recovering data from under sampled data streams

I’m trying to analyze a repeated data stream from a sensor. The data probably has events at the 100us scale, it occurs at a fairly random interval, and the signals are extremely similar. The problem ...
1
vote
1answer
26 views

Sort a $d$-sorted array

An array is $d$-sorted if every key in the array is located at a distance at most $d$ from its location in the sorted array. I need to write an algorithm that get a $d$-sorted array of length $n$ and ...
0
votes
1answer
21 views

Bucket sort has uniformly distributed data

Implementation of bucket sort is mainly useful when input is uniformly distributed over a range. So the ques here is what is the significance of having input data uniformly distributed for applying ...
1
vote
0answers
42 views

Determining number of $j$ such that $b_j \le c_i$ and $a_j \le b_i$ in time $O(\log n)$

I have an array $A$ of length $n$, containing triplets (think of it as a $3\times n$ matrix). Can I re-order the array (without reordering a triplet's inner values) in time $O(n\log n)$ so that it is ...
1
vote
1answer
50 views

Running time of heap sort, when all number are identical

Given n numbers that all are identical, then what would be the running time of heap sort? Will it be in linear time $O(n)$ or, best case $\Theta(n\log n)$?
1
vote
2answers
34 views

What is the space complexity of quicksort?

What is the space complexity of quicksort? I was doing some research and found some saying it is $O(1)$, some saying it's $O(\log n)$, and some saying $O(n)$. Not sure what to believe, even though $O(\...
0
votes
1answer
33 views

Sorting n weight disks with decision tree

I was refreshing some old tests about sorting algorithms, there was a question as follow: Question: we have n weight disks with different weights and we want to ...
1
vote
2answers
46 views

How does size of list in merge-sort, quick-sort, insertion-sort, matter?

We have been taught that: Insertion-sort will best work if we have a small list. Quick-sort will best work if we have a long list. Merge-sort will best work if we have a huge list. It is not ...
1
vote
1answer
36 views

Quickly determine if insertion sort or quick sort is better

I'm in a scenario where ~30% of the time, my array is almost completely sorted, and the other 70% of the time, it is basically completely random. I want to quickly determine if my list is almost ...
0
votes
1answer
15 views

How to split the array into two subarrays with the smallest sum difference?

Given An array of elements, all elements are positive (unsorted, but sorting is not a problem if required) The objective: To create two subarrays, so that ...
1
vote
1answer
65 views

Find minimum number of points which intersect overlapping arcs

Say I have a circle of a fixed radius, with overlapping arc intervals along its edge. I want to return a minimum set of Points which intersects all arcs in $n^2$ time. I'm having some trouble proving ...
1
vote
2answers
101 views

Sort an array that contain two sorted array in $O(n)$

Given an array $A[1..n]$. $A$ is mixed of two sorted arrays $B$ and $C$ of equal sizes, such that $B$ is in the ascending order and $C$ is in the descending order. Consider the following example: $B=[...
1
vote
1answer
31 views

Average case analysis by key comparisons of Max Sort

I'm having trouble approaching this average case analysis in terms of key comparisons. The pseudo-code is as follows: ...
0
votes
1answer
17 views

“Batch” partial sorting algorithm

I'm looking for an existing algorithm that would ensure that the first k elements after sorting are the top k elements but not ...
5
votes
1answer
98 views

Algorithms for almost sorting

I want to find a comparison sorting algorithm that can almost sort a set of data, using the least comparisons possible. What I mean by "almost" is that if the perfectly sorted data is $[x_1, ...
1
vote
1answer
40 views

Maximize $\sum_{i\equiv r \pmod{m}} a_i$ over $m,r$

Given a circle with $n$ equal segments. On each segment there is an integer. We want select segments at equal distance, maximizing the sum of integers on selected segments. I have an algorithm with ...
1
vote
1answer
35 views

Finding numbers near the median in linear time

Problem: Describe (English is enough) a linear algorithm that, given a set $S$ of $n$ distinct numbers and a positive integer $k \leq n$, returns the $k$ numbers in $S$ that are closest to the median ...
3
votes
1answer
51 views

Sorting algorithm for ranking hundreds of Images based on pairwise comparison

I am facing the task of designing an algorithm to rank some hundred of images (around 300). The ranking is to be based on pairwise comparison judged by human (done through Amazon mechanical Turk). I ...
0
votes
0answers
25 views

How to known which algorithm is the best for what situation, when sorting numbers?

Is there some kind of "universal list" of performance of different algorithms in different situations? I have different databases that save user input (numbers). However some of these sets ...
0
votes
2answers
19 views

Sorting an interval

Given that array has $k$ elements (all distributed uniformly). Its length is exactly $3$ somewhere in $[0, k)$. For example, if $k=100$ then, we have $100$ numbers and they can be in $[10,13)$, but ...
0
votes
2answers
55 views

Insertion sort on small arrays in Merge Sort

Quick question on the wording of the question from CLRS Ch2 Problems. The question goes as follows: Although merge sort runs in $\Theta(n\lg n)$ worst-case time and insertion sort runs in $\Theta(n^2)...
1
vote
2answers
42 views

Finding the size of a subset of top $N$ elements, where the minimum element is at least $N$, in linear time

I am looking for a solution for the following problem: Find the size of a subset of top $N$ elements, where the minimum element is at least $N$, in linear time. Consider the following sequence: $$ 3,...
1
vote
1answer
39 views

Loop invariance insertion sort algorithm

I have the following pseudo code for a insertion sort algorithm ...
0
votes
0answers
103 views

loop invariant of selection sort algorithm

I am asked to write an C code Selection Sort algorithm and use loop invariant to show its correctness. ...
1
vote
1answer
15 views

Sorting in computing longest increasing subsequence

I am currently reading the paper On computing the length of longest increasing subsequences by Michael L. Fredman. I'm struggling to understand parts of the proof of Theorem 3.5, especially this bit: ...
0
votes
1answer
54 views

Algorithm for sorting within windows

I am writing an app which displays speeches on various topics, with each speech having a number of attributes. I want to give the user the choice to sort a list of speeches by an attribute, even ...
1
vote
1answer
49 views

How to prove the optimality of the “patience sort” algorithm?

I was trying to understand how we can solve the Longest Increasing Subsequence (LIS) problem in O(N log N) time. I came across a sorting algorithm called the patience sort algorithm. To learn it I was ...
0
votes
0answers
36 views

In-place linear sort of integers, again

I am amazed by the many discussion regarding the existence of any linear and in-place sorting algorithm, and variants, see e.g. is-this-implementation-of-bucket-sort-considered-in-place is-counting-...
1
vote
1answer
70 views

Indexing a huge dataset (that does not fit into central memory)

The problem. Let us consider a huge file with billions of lines, each containing a string. There are $n$ different strings and $m$ lines in the file, with $m$ much greater than $n$, although both are ...
0
votes
1answer
21 views

How to (Efficiently) Sort a List of Items with Parent/Child Relationship

I have a list of items that have a parent/child/grandchild/etc. type of relationship. Each item has a list of descendants, and an _.isDescendentOf(other) member ...
0
votes
1answer
75 views

Solving the recursive equation $T(n)=T(k)+T(n-k-1)+O(n)$

The question is clear in the title. I am trying to solve this recursion as a part of showing that the worst case of quicksort algorithm occurs when $k=0$, but can't do it. I could do the following ...
3
votes
0answers
113 views

A container sort (or “Minecraft sort”)

Here's the problem: I have some $n$ ordered containers, each with $m$ slots. I have $p$ temporary slots that I can use to move items between containers. Sorting within containers is not costly, ...
1
vote
0answers
27 views

Running time of random pivot quicksort on random and sorted arrays

I don't understand why I am getting the following execution times for the quicksort with a random pivot. Times are in microseconds they are the average of five executions. Random array: ...
0
votes
1answer
38 views

What's the name of this sorting(?) algorithm?

Given the options of: Red Orange Yellow Green Blue Violet You want to find your favorite color by comparing all pairs to each other, like so: Red vs... Red vs Orange = Orange Red vs Yellow = Red ...
5
votes
1answer
61 views

Mergesort and some claims on comparison

suppose for $n$ elements we using mergesort. each number compared at most $O(\log n)$ = False in average each element compared with $O(\log n)$ elements = True there exist an element compared with $\...
0
votes
0answers
20 views

sort array using oracle computes number of elements in one partition that are smaller than given element in O(1)

excuse me for the long title. My goal is to find an algorithm to sort an array of n elements, with an oracle, which must be used O(logn) times. Given a partition of our array (resulting in two subsets,...
-1
votes
1answer
52 views

Time complexity of a machine which combines Insertion Sort and Quicksort

Given a machine that sorts an array of length $n$ with the following algorithm: Sort first $2\sqrt{n} + 1$ elements of array with Insertion Sort.(Check Insertion Sort) Select the median of the whole ...
0
votes
0answers
63 views

Distribution Sort - Split elements

I have read from the following references about Distribution Sort: https://users.cs.duke.edu/~reif/courses/alglectures/vitter.papers/Vit.IO_survey.pdf (5.1. Sorting by Distribution) https://en....
2
votes
1answer
32 views

Modified topological sort

I recently asked a related question at the theoretical CS stack exchange, but I have modification to the problem that I think is a bit tougher. This seems like a better place anyways. Let's define a &...
1
vote
1answer
81 views

Efficient algorithm for sorting objects by key that values are range from 0 to 100

Can you help me with sorting algorithm implementation for objects of Student type by rating field. This field (...
1
vote
1answer
51 views

Sort an array where $0\leq a_n\leq n^2$ and $a_n\in\mathbb{N}$

sort an array where $0\leq a_n\leq n$ sort an array where $0\leq a_n\leq n^2$(hint represent every element in base $n$) All the elements are integers for the first 1 I used counting sort and for the ...
1
vote
1answer
74 views

If there is no Hamiltonian path in a DAG then there are at least two different Topological sorts

I understand the concept that if there is no Hamiltonian path so there will be 2 smaller paths and with them I can build more then one topological sort but I am not sure how make it formal. Can you ...
0
votes
0answers
17 views

SIMD reordering permute algorithm

The question is about how to schedule the pairwise SIMD instruction to move the data in proper position. Say I n SIMD registers, each SIMD register contains n elements. If each column represent a SIMD ...
2
votes
0answers
126 views

Is there a linear sorting algorithm given an oracle that finds kth smallest item?

Given a machine that can compute the kth smallest item of an Array A in $O(\sqrt n)$ time. Find a recursive function that can sort A in linear time corresponding to $n$ which is the length of A. First ...
2
votes
1answer
50 views

Sorting $n^2$ numbers which consist of numbers from 1 to $n$

I wish to sort $n^2$ numbers which all come from the set $\{1,2,3,...,n\}$, i.e duplications are allowed. I know I can just use merge sort which has complexity $\mathcal{O}(n^2\log (n))$, but I was ...
1
vote
1answer
66 views

Calculating the Time complexity using Radix sort

Im trying to determine what is the time complexity of sorting numbers with a specific range and base. I have n numbers in the range of 1-n^10 and the base for the radix sort is n/log n. I have tried ...
2
votes
2answers
266 views

What is the requirement for bubble sort to complete in 1 pass?

I am working on a problem where you're given $n$ distinct numbers, and you want to find the number of permutations such that it takes bubble sort at most 1 pass to complete. e.g., if ...
1
vote
1answer
111 views

Complexity of Radix Sort

I am a little confused by the complexity proof of Radix Sort. For counting sort, the complexity reported is $O(n+R)$, where $n$ is the number of items and $R$ is the range. But this is not entirely ...
0
votes
1answer
57 views

How to Sort 2D array with out 1D array

Hello I am a new Computer Science student Ok, so I am trying to sort the 2D array I know you can actually sort a 2D array by copying it into a 1D array sort it using any Algorithm, and then place ...

1
2 3 4 5
16