Questions tagged [sorting]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
31 views

Doest sorting accept a dynamic programming solution?

Are there any known / efficient dynamic programming solutions to sorting? I understand of course that dynamic programming applies to scenarios where we have overlapping subproblems and optimal ...
-1
votes
1answer
60 views

Merging $t$ arrays of size $t$ cannot be done in $O(t^2)$

Dr. John claims that he designed a comparison-based algorithm FastMerge that can merge $t$ arrays of size $t$ at most each in $O(t^2)$ time. In Dr. John’s own words, ”Given $t$ sorted arrays $B_1,B_2,...
1
vote
2answers
40 views

Why does MergeSort have O(n) space complexity if it splits the array log(n) times?

I know this is a common algorithm with plenty of analysis, but when I searched for an answer the only one I found was "Merge Sorting has O(n) auxiliary space because it copies the array into L and R". ...
1
vote
1answer
46 views

MSD vs LSD Radix sort

I read the following in CRLS: I don't understand the text in yellow. Why would radix sort not work so well if we sort by their most significant digit? What extra "...
0
votes
2answers
27 views

Revert array shuffle faster than in O(n^2)

I want to reverse an array that was shuffled with the function ...
0
votes
0answers
23 views

Reverse of In-place algorithm for interleaving an array

How to do the reverse process of In-place algorithm for interleaving an array question?
0
votes
2answers
35 views

Need help analyzing the runtime analysis of this algorithm/algorithms in general

This is the algorithm I was trying to find the runtime of (doSomething) - ...
0
votes
1answer
46 views

How to sort objects based only on “less than” relationships?

Say I have n objects, each with an unknown value, and a n by n matrix Z. Such that Z(i,j)=1 if the value of object i is less than the value of object j, and Z(i,j)=0 otherwise. How can I sort these n ...
6
votes
2answers
432 views

Find and sort 2d array elements like radar

I don't know relevant keywords about this algorithm. I can show you visually Any ideas are appreciated
2
votes
1answer
42 views

Numerical Accuracy & Sorting Algorithms?

Sedgewick and Wayne talk about how sorting algorithms and, specifically, priority queues are used in devising ways to improve accuracy in floating-point calculations: https://algs4.cs.princeton.edu/...
3
votes
3answers
150 views

Sorting array of strings (with repetitions) according to a given ordering

We get two arrays: ordering = ["one", "two", "three"] and ...
0
votes
1answer
25 views

practise resources for basic sorting

I have to prepare for a midterm and I am looking for a resource where I can practise the three basic sorting algorithms insertion sort, bubble sort and selection sort a little. Last year they had to ...
2
votes
1answer
75 views

“Searching and sorting” algorithm to find the natural logarithim of a number?

Yeah, this is for a homework assignment, but I hope that you'll humor me anyway. I am asked to design an algorithm that finds the natural logarithm of a number. This would be straightforward, but I'm ...
0
votes
0answers
16 views

How do i tell if a network is not sorting network? [duplicate]

For most sorting network diagrams how do you work out that it is not a sorting network? What is the method to work it out ?
4
votes
2answers
190 views

Linear algorithm to measure how sorted an array is

I've just attended an algorithm course, in which I've seen many sorting algorithms performing better or worse depending on how much the elements of an array are sorted already. For example, for what I'...
2
votes
1answer
167 views

Name for sorting algorithm “while not sorted, swap the FIRST unordered pair”

A typical bubble sort steps through all pair indices until it reaches the end of the list, then starts a new pass. For a toy problem, we have a variant that just performs the first available swap in ...
1
vote
4answers
692 views

Time complexity of insertion in linked list

Apologies if this question feels like a solution verification, but this question was asked in my graduate admission test and there's a lot riding on this: What is the worst case time complexity of ...
0
votes
1answer
121 views

Sorting strings using Counting Sort in O(n), where n is the total number of characters in all the strings

Suppose, you are given an array of strings of different lengths, but the total number of characters over all the strings is n. Describe an algorithm using Counting Sort to sort the strings in ...
0
votes
1answer
15 views

Pagination of results from different sources merged by a unified scoring function

Assume a Hotel reservation scenario, given $m$ ranked lists of attribute values such as distance, price, amenities (normalized between $0$ and $1$), and a unifying linear score function $F(\cdot)=\...
0
votes
1answer
34 views

Number of permutations of set {1, 2, …, n} for which insertion sort will perform exactly n permutations

I have had the following problem at my last exam: For how many permutations of set {1, 2, ..., n} where n > 2 will insertion sort (without guard element) perform exactly n comparisons. My thinking ...
0
votes
1answer
37 views

Runtime Calculation Sort-Algortihm

I'm really struggling with the following exercise and I would really appreciate your help: I have to calculate the expected runtime of a sort Algorithm with the following variants: ...
1
vote
1answer
50 views

An algorithm to find the closest match between 2 arrays of RGB pixel tuples

So I'm looking for a bit of an abstract algorithm and I'd appreciate any references to read up on. This is a bit tough to explain but I'll try my best. Suppose we have 2 arrays of ...
1
vote
1answer
47 views

Given an array with N elements and an array of N indices find the lowest possible amounts of swaps [duplicate]

So I have two arrays $d$ and $s$ with size $n \in \mathbb{N}$. Array $d$ contains the elements and array $s$ contains indices. Array $s$ contains all numbers from $0$ upto $n$ with no duplicates. The ...
1
vote
0answers
52 views

What are the common practices to weight tags relations?

I am working on a webapp (fullstack JS) where the user create documents and attach tags to them. They also select a list of tags they are interested in and attach them to their profile. I am not a ...
1
vote
2answers
197 views

Analysing worst-case time complexity of quick-sort in different cases

I am trying to understand worst case time complexity of quick-sort for various pivots. Here is what I came across: When array is already sorted in either ascending order or descending order and we ...
0
votes
0answers
20 views

What is an $O(n \log(n))$ binary sorting algorithm with a guaranteed low scaling constant on the run-time?

Let $O_c(f(n))$ denote that $c$ is the scaling constant for the run-time (e.g. $\text{run time} \leq c\cdot f(n) + B$ if $n$ is large enough) The absolute lower limit on the run-time for a binary ...
2
votes
1answer
37 views

If I walk through list and delete every out-of-order element I come across, on average how many elements will be left?

I have a uniformly randomly permuted list of length $n$. I walk through the list element-by-element, and delete an element if it's out-of-order (compared to the previous in-order elements of the list)....
1
vote
0answers
38 views

Hypothetical Situation for sorting in $O(n)$ using median finding machine that works in $O(\sqrt{n})$

In a hypothetical world, we have a machine that can find median of $n$ numbers in $O(\sqrt{n})$. (Of course this machine is not real). Can we use this machine to sort an array in $O(n)$? I don'...
0
votes
0answers
55 views

Selection Sort vs Merge Sort

I recently wrote a written test for the recruitment of Scientists/Engineers in ISRO(Indian Space Research Organization) few days back and the following question appeared in the test. Of the following ...
1
vote
1answer
74 views

Sorting algorithm

I want to know from this picture which one is bubble sort, insertion sort and selection sort? My answer is: bubble sort algorithm, insertion sort algorithm, selection sort algorithm. Is it this ...
0
votes
1answer
42 views

Algorithm for sorting pairs of items

I have a real world problem where I have a list of nodes. Each ones contains a name and the name of the node before it in order. I am trying to devise an algorithm to sort these in order. The problem ...
9
votes
2answers
404 views

Minimum number of swaps in sorting sequence

Given an array of N integer elements (not necessarily distinct), what is the minimum number of swaps (not necessarily adjacent) needed to sort the array? I've been struggling with this problem for a ...
3
votes
1answer
101 views

Given n sorted arrays with size k select one element from every array such that the sum of the elements is minimum and the sum of their indices is k+1

So if $k = 3$ and $n = 2$ and we select the element $a_1[3]$ of the first array then we have to select $a_2[1]$ from the second array. If we select the element $a_1[2]$ then also $a_2[2]$ must be ...
2
votes
2answers
206 views

Complexity of cyclic sort

I have this algorithm ("cyclic sort") to sort an array which contains unique numbers from 1 to $n$: ...
1
vote
2answers
276 views

Sorting a large list of test scores

You have a large list (say N > 10000) of test scores which you would like to sort. The test scores are between 1 and 100. What is quickest way to sort the list? First thought. We have a O(N log N) ...
-1
votes
1answer
75 views

Formal definition of stable sorting algorithm

Suppose $a$ is an array and $cmp$ is a "compare function" that is a function which outputs $true / false$ values. I say that an algorithm $A$ which takes in input $a$ and $cmp$ is a stable sorting ...
3
votes
1answer
30 views

Given an unsorted list of $n$ items, how many random comparisons are needed on average to be able to sort the list?

There is an unsorted list of $n$ items $x_1, \ldots, x_n$. Until you can sort the list, you are given one of the ${n \choose 2}$ possible binary comparisons uniformly at random (with replacement). On ...
0
votes
1answer
113 views

Which sort algorithm to choose given two specific arrays?

Interview question: Given array A which contains only odd numbers and array B which contains only even numbers, explain which sort algorithm would you choose. I said merge sort. I thought that ...
3
votes
2answers
317 views

Minimum XOR for queries

I was asked the following question in an interview. Given an array $A$ with $n$ integers and an array $B$ with $m$ integers. For each integer $b \in B$ return and integer $a \in A$ such that $a \...
1
vote
0answers
21 views

Sort arrays with out merging

I have a data-set which contains more than two arrays. I would like to sort the data-set with out merging the arrays to a single array. Arrays may or may not be in same machine. I am looking for an ...
4
votes
1answer
95 views

Sort array of duplicate integers in place

Given an array of integers within [1, n] where n = size of array, some elements may appear more than once. Could we sort it with just 1 extra space and in O(n) time?
2
votes
1answer
50 views

Is there a well-known algorithm for arranging inputs according to their category?

Background: (I’m a complete beginner in computer science in general, so I do apologise if my question is not formulated in a sensible way. E.g. I have avoided technicalities in formulating my ...
1
vote
1answer
58 views

Space Complexity of Bottom-Up Merge Sort

What is the space complexity of Bottom-up merge sort? It uses iteration rather than recursion so it will not use stack. But will an auxiliary array be used for the merge operation? Please explain. ...
0
votes
1answer
31 views

Analysis of Pan-cake sorting

i was implementing pan-cake sorting. We can implement it by taking largest element to start and flipping it recursively (Like selection sort). However it is mentioned that the A[i] has to be a ...
1
vote
2answers
50 views

Time complexity to sort 100 elements by using selection sort?

What will be time complexity for sorting 100 elements using selection sort answer given is O(1), but selection sort time complexity is O(n^2) in every case so how O(1)?
0
votes
2answers
168 views

is AVL tree is better than heap for sorting purpose?

for sorting n elements what is better to use AVL tree or heap data structure and why? Can someone explain in brief?
0
votes
1answer
62 views

Is it possible to sort a linked list without copying its values but linking the nods?

Is there an algorithm I could use when copying the values is not allowed? My list is going to be sorted in an ascending order. Also can this be done in a quadratic time? I will be attempting this in ...
0
votes
0answers
67 views

Is there an O(n) solution for this problem?

I have found this problem on CodeForces.The problem is in the following link: https://codeforces.com/problemset/problem/729/C Problem Starts here: Vasya is currently at a car rental service, and he ...
2
votes
0answers
38 views

Find a non-minimal sequence of elements covering the support set

Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we can read, write and compare them in $O(1)$ time with arbitrary positions). Denote $\text{...

1
2 3 4 5
14