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
1answer
148 views

Finding most efficient sorting algorithm

Arr is an array that contains $ n$ numbers. Suggest the most efficient algorithm for each case and analyze the runtime. Explain why the algorithm you chose is the best one. Arr contains exactly $\...
1
vote
1answer
51 views

Quicksort Time Complexity

I am learning the Quicksort algorithm and I am struggling with understanding the time complexity. Here is the JavaScript ES6 code for the partition function that is used in the algorithm: ...
1
vote
2answers
62 views

Theoretical lower bound of finding number of occurrences of a target integer in a sorted array

Given a sorted array of integers and a target integer, find the number of occurrences of the target integer. It is well-known that a binary search has time complexity $O(\lg n) $ where $n$ is the ...
4
votes
1answer
70 views

Choose $n$ out of $2n-1$ boxes containing at least half of all white balls and half of all black balls

We are given $2n - 1$ boxes with a total of $B$ black and $W$ white balls. In the $i$-th, box there are $w_i$ white and $b_i$ black balls. It is required to choose $n$ boxes so that, the sum of the ...
1
vote
1answer
93 views

Average Case Analysis of Insertion Sort as dealt in Kenneth Rosen's “Discrete Mathemathematics and its Application”

I was going through "Discrete Mathematics and its Application" by Kenneth Rosen where I came across the following algorithm of the Insertion Sort and also its analysis. The algorithm is quite ...
1
vote
1answer
130 views

Merge $k$-sorted arrays - without heaps/AVL tree in $O(n\log(k))$?

Given $k$-sorted arrays in ascending order, is it possible to merge all $k$ arrays to a single sorted array in $O(n\log(k))$ time where $n$ denotes all the elements combined. The question is ...
1
vote
1answer
203 views

How to wiggle sort an array in linear time complexity?

The wiggle sort is nums[0] < nums[1] > nums[2] < nums[3] > nums[4] ... For an input: nums = [1, 5, 1, 1, 6, 4], the expected output is ...
0
votes
0answers
22 views

Analysis of Radix sort of $n$ $b$ bit numbers

I was reading radix sort in Introduction to Algorithms by CLRS . And it gave the following Lemma with its analysis I understood the proof of the Lemma but confused on the part where they try to ...
1
vote
0answers
20 views

Sorting with high-latency compare

My basic setup is very simple: I'm trying to sort N items now, and later on I'll need to incrementally sort more items. The unique part of the problem is that my item comparison is not a computational ...
0
votes
1answer
54 views

Radix sort slower than Quick sort?

I would like to demonstrate that sometime radix-sort is better than quick-sort. In this example I am using the program below: ...
0
votes
1answer
20 views

How to represent a recurrence that increments by one at each tree level?

I am using a merge sort like algorithm. Each level of the tree has a different Big O runtime. The runtime as a whole can be represent as follows: $$O(\sum_{i=0}^{log(n)}2^{\frac{n}{2^i}} * 2^i)$$ I ...
0
votes
1answer
48 views

Runtime of Divide and Conquer Flavored Bogo Sort

Here we propose a way to reduce Bogo Sort's runtime from factorial to exponential using a divide and conquer approach. This is something we have likely all pondered on extensively. https://en....
0
votes
2answers
39 views

“Low-High” sort divide and conquer with merge… how small to make the subproblems for good efficiency?

For a mental exercise, I decided to try out my own simple sorting algorithm which processes an array of integers in any order, and as it passes thru them all, records the highest and the lowest. So ...
1
vote
1answer
19 views

How can divide by 2 blocksize bubblesort followed by a final mergesort be optimized in a particular environment?

I am wondering if we had a large array to sort (let's say 1,048,576 random integers), chosen because it is a perfect power of 2, if we can just keep dividing those blocks into smaller and smaller half ...
2
votes
3answers
235 views

Algorithm to identify top $\log n$ elements in $O(n)$ time

Airlines has a new policy to give a first-class upgrade coupon to their customers based on the number of miles accumulated. They decided to give it to their top $\log(n)$ frequent flyers, where n is ...
2
votes
1answer
46 views

Interval sorting that avoids covering

I have a collection of intervals and I want to sort them so that the order is interpreted as a sort of "z-index". That is, a given interval may or may not be "visible" depending on whether the merge ...
1
vote
1answer
192 views

Quick Sort vs Radix Sort

In an coding exam, I was once asked this question: Assuming that you are only sorting Integers in ascending order, which algorithm do you use when you want to prioritize speed the most, but you ...
0
votes
2answers
630 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
69 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
883 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
773 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
32 views

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

I want to reverse an array that was shuffled with the function ...
0
votes
2answers
102 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
55 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
463 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
63 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
217 views

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

We get two arrays: ordering = ["one", "two", "three"] and ...
0
votes
1answer
27 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
83 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
20 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
277 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
195 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
6k 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
856 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
28 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
38 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
59 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
2answers
151 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
50 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
55 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
1k 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 ...
2
votes
1answer
40 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)....
2
votes
1answer
143 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'...
1
vote
1answer
83 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
45 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
613 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
108 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
523 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
365 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
85 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 ...

1 2
3
4 5
16