# Questions tagged [sorting]

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

729 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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-...
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 ...
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 ...
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 ...
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, ...
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: ...
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 ...
56 views

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 $\... 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,... 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 ... 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.... 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 &... 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 (... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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.... 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 ... 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.... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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: ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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) ... 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 ... 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 ... 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$. ... 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 ... 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$\...
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 ...