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

Find the average number of steps to sort an array by randomly selecting two elements

I have sequence of an unique numbers from 1 to 10 in randomly order (for example: list = [7, 5, 3, 4, 2, 6, 10, 1, 9, 8]). I can choose two random number and if the list from left number larger then ...
3
votes
2answers
34 views

Nielsen & Chuang Exercise 3.15: Lower bound for compare-and-swap based sorts

From Nielsen & Chuang (page 138): Suppose an $n$ element list is sorted by applying some sequence of compare-and-swap operations to the list. There are $n!$ possible initial orderings of the list....
1
vote
1answer
17 views

Looking for a subjective ranking algorithm

I'm interested in learning about ranking algorithms that sort items based on preference. For example: If a person was food taster/judge and had 10 small bowls of chili that they had to rank in order ...
0
votes
0answers
16 views

In CDC 6600 6-bit encoding, why does it matter what value space character is given?

How does this affect sorting such that sort function result in: FOO BAR FOO while expecting: FOO FOO BAR Reference https://en....
1
vote
1answer
26 views

Bottom-up Mergesort vs Natural Merge Sort

I ran into natural mergesort in this Wikipedia page: https://en.wikipedia.org/wiki/Merge_sort#Natural_merge_sort However, I can't find much information regarding: The algorithm(s) to achieve natural ...
0
votes
0answers
46 views

Algorithm for sorting arrays of arrays

I have a problem where I need to sort array of arrays. For A being a array arrays (a1,a2,a3,...an) were each a = {0...d} d=fixed number of elements. *The assumption all sublists will have fixed ...
0
votes
0answers
28 views

How do we sort the chunk in the first pass of external merge sort?

Referring to the 9th page of a slide, when we use multi-pass multi-way external merge sort on a file with $N$ pages using $B$ buffer pages, in "pass 0" we'll read a chunk of $B$ pages into ...
0
votes
0answers
41 views

Why do we need MinHeap for Meeting Rooms 2 Leetcode problem

I came across this problem online which is a Leetcode premium problem. Most of the people are solving this using Minheap. To me using minHeap for this seems like repetitive way to solve a problem if ...
1
vote
2answers
55 views

Why decision tree method for lower bound on finding a minimum doesn't work

(Motivated by this question. Also I suspect that my question is a bit too broad) We know $\Omega(n \log n)$ lower bound for sorting: we can build a decision tree where each inner node is a comparison ...
1
vote
1answer
32 views

Why selection sort is a stable sort algorithm?

One of the specifications of sort algorithms is stability, which means items with the same value in different indices are not replaced after applying sort algorithm. Why selection sort is unstable and ...
0
votes
0answers
48 views

simplyfing common data values (parts of a string) in an array - by merging same attributes (data values)

I have arrays comprised of string elements like the following 2 examples. Each of the following lines is a string element of the array. example1: ...
2
votes
1answer
42 views

Error in pivot selection algorithm for merge phase [Sorting]

In the paper Comparison Based Sorting for Systems with Multiple GPUs, the authors describe the selection of a pivot element with respect to the partition on the first GPU (and its mirrored counterpart ...
2
votes
0answers
18 views

approximate line segments from array of unsorted points

The polygon above is actually a collection of a lot of black points closely packed together. I want to approximate these black points as straight line segments. The black points are not sorted in any ...
1
vote
1answer
27 views

Why do we should not to use simple count instead of cumulative count in Counting Sort?

I have this piece of code for counting sort and it is "counting" sort, because it actually counts occurrences. And it doesn't use cumulative sum. I want to ask why it is bad to not to use ...
0
votes
0answers
21 views

Sorting idea - using little buckets (Not BucketSort)

I am recently been doodling with sorting, thought about writing my own ideas, and what I am about to write here came to my mind, and I am writing it here because I do not know if such sorting idea ...
0
votes
1answer
28 views

Fast hashing algorithm for mapping/quantizing a collection of floats onto a small set of sorted floats

With my application, I have Collection X: thousands of floating-point numbers with the value range [0, 1], not sorted. Collection Y: 11 floats ranging from [0, 1], sorted. The size of X is known. Let ...
0
votes
1answer
33 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
29 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 ...
2
votes
1answer
36 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
2answers
33 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

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
24 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$. ...
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 ...
-1
votes
1answer
55 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
28 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
52 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
62 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
29 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
37 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
66 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
15 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
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
30 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
19 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
39 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
27 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 ...
0
votes
0answers
20 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 ...
2
votes
3answers
107 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
74 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
170 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
68 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
125 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
217 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
28 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
30 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
45 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
49 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
444 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

1
2 3 4 5
15