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
51 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
47 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 ...
1
vote
0answers
33 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
63 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
20 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 ...
1
vote
1answer
44 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
110 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
24 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
37 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
56 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
16 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
32 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
62 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
31 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
79 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
46 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
15 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
118 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
49 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
51 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
98 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
65 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
33 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 ...
0
votes
1answer
49 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
45 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
40 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
29 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 ...
1
vote
0answers
49 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
87 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
76 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
51 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
43 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
25 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
36 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
29 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
42 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
35 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
38 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
35 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
59 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
26 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
46 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
69 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
29 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
54 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 ...

1
2 3 4 5
15