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
25 views

Proof for time complexity of Insertion (k-proximate) Sort equals O(nk)

The following is the definition for Proximate Sorting given in my paper: An array of distinct integers is k-proximate if every integer of the array is at most k places away from its place in the array ...
1
vote
1answer
24 views

What factors of the integer dataset being sorted can I change, in order to compare two sorting algorithms?

I am comparing two comparison and binary data structure based sorting algorithms, the Tree Sort, and the Heap Sort. I am measuring the time taken for both algorithms to sort an increasing size of an ...
0
votes
1answer
213 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
19 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)=\...
2
votes
1answer
35 views

How do you find all integers in a sorted array of size n that appear n/k times?

I try to find the solution to this problem: How do you find all integers in a sorted array of size n that appear n/k times in less than O(klogn) time? I could only find this question, where O(klogn) ...
1
vote
1answer
63 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
2answers
30 views

Why is there so little literature on partial order production?

Please excuse or improve the poor title of this question. My question is rather undirected, but I guess I am trying to find out if I might be missing a keyword for my problem. So there is plenty of ...
0
votes
1answer
45 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: ...
0
votes
0answers
15 views

Finding a Good Estimate for Amount of Time Computers Spend Sorting Lists of What Lengths?

I have an assignment to envision and calculate the possible effects the implementation of a general sorting algorithm that is O(n) time and O(1) space ( assuming general case ) would have on ...
0
votes
0answers
23 views

2 Questions about Topological sorting in DAG

$G = (V,E)$ is a directed graph without cycles (DAG). Let $s,t \in V$ two vertices in the graph such that: exists a path from $s$ to any other vertex, and exists a path from any vertex to $t$. ...
0
votes
3answers
9k views

Quick Sort with first element as pivot

I'm studying Quick-Sort and I am confused as to how it works when the first element is chosen as the pivot point. I am trying to trace the first step in the Quick-Sort algorithm, to move the pivot S[...
3
votes
0answers
45 views

Minimizing the sum of differences in a pair [duplicate]

You have two arrays, a and b Both contain n elements, all positive and distinct. you have to create a pair, by taking one number from each array, such that the sum of the differences of the pairs ...
6
votes
2answers
2k views

Can we create faster sort algorithm than O(N log N)

I was thinking that we can create algorithm for sorting that will work faster than $O(N\log N)$ Let's say we have given array $A$ consisting of $N$ integers, where $N = 10^6$. Our task is to sort ...
-1
votes
1answer
51 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
25 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: ...
5
votes
1answer
1k views

Is this in-place merge algorithm efficient or not?

I have trouble analyzing the characteristics of this algorithm that merges two adjacent sorted lists. Basically it looks at some number of the tail of the first list, and the same number of head ...
1
vote
2answers
51 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 ...
3
votes
1answer
53 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 ...
8
votes
2answers
5k views

Sorting a list of strings in lexicographic order of sorted strings

Let $A$ be a collection of strings over the alphabet $\{0,\ldots,m-1\}$ that in total contain $n$ symbols. Your task is to sort each of the strings internally, and then sort the resulting strings in ...
1
vote
1answer
26 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
58 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
3answers
96 views

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

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 ...
1
vote
1answer
29 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 ...
344
votes
11answers
315k views

Why is quicksort better than other sorting algorithms in practice?

In a standard algorithms course we are taught that quicksort is $O(n \log n)$ on average and $O(n^2)$ in the worst case. At the same time, other sorting algorithms are studied which are $O(n \log n)$ ...
0
votes
0answers
12 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 ...
4
votes
1answer
101 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?
1
vote
0answers
18 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
27 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: ...
2
votes
3answers
431 views

Can this “double pop” Heapsort variation speed up sorting on average?

For classic Heapsort (in this example using a maxheap), only the root node is extracted (popped) at each iteration and the last element in the heap is swapped into its place and then the tree is "re-...
0
votes
1answer
18 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
38 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
1answer
37 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 ...
0
votes
2answers
25 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 ...
0
votes
2answers
109 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 ...
0
votes
1answer
213 views
24
votes
5answers
20k views

Least number of comparisons needed to sort (order) 5 elements

Find the least number of comparisons needed to sort (order) five elements and devise an algorithm that sorts these elements using this number of comparisons. Solution: There are 5! = 120 possible ...
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
101 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 ...
0
votes
0answers
17 views

Quicksort with lomuto partition - how many repeating elements are too many?

I know that quicksort with Lomuto's partition method faces worst case run-time $\Theta(n^2)$ when there are many repeating elements in the array. However, I'm trying to figure out - how many ...
1
vote
2answers
76 views

Understanding how quicksort operates

I am having a hard time understanding the quick sort partition operation. I understand what partition is supposed to do, I just don't understand how partition does it. Specifically, I don't understand ...
1
vote
2answers
174 views

Pancake Sorting Graph Recursive Definition

I'm having trouble understanding exactly how the graph for Pn (where n = number of pancakes) is defined recursively for n>= 4. I can see obviously that, in the case of n=4, there will be 4 rough ...
2
votes
1answer
45 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
56 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 ...
3
votes
1answer
54 views

Improve algorithmic complexity

We have an array of N size. We have to perform Q queries on it, in which each Query contains and Index I for which we do: ...
0
votes
2answers
40 views
1
vote
1answer
60 views

Question about how can i determine if counting sort is the right option over other sorting algorithms

So, an exam's exercise asks me to find an alghoritm that can determine if counting sort is the best solution, otherwise use another optimal sorting algorithm. Now i find that solutions for that ...
-1
votes
1answer
67 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,...
0
votes
2answers
465 views

Time complexity of quicksort for arrays in increasing or descreasing order

Two $n$-size arays are given: $n_1$ is in decreasing order and $n_2$ is in increasing order. Let $c_1$ be the time complexity for $n_1$ using quicksort, and $c_2$ the time complexity for $n_2$ using ...
1
vote
1answer
149 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 "...
1
vote
2answers
67 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
2 3 4 5
14