# Questions tagged [sorting]

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

685 questions
Filter by
Sorted by
Tagged with
344 views

### $O(n\log n)$ algorithm for minimizing number of inversions in leaves of complete binary tree

I'm having trouble making an algorithm to fit these specs: Given a complete binary tree ($n = 2^d$ leaves) with integers in leaves. Reading the leaves from left to right makes a sequence of integers (...
455 views

### Sorting lower bounds for almost sorted array

Can't find a good way to tackle the problem. Would appreciate any help. $A$ is an $n$ items array from an ordered set, in which every item is at most $\log n$ indices away from its position in the ...
105 views

### Greedy Solution for Selecting Prefix Sum

Given $n$ arrays. Each has size of $h$. Let $a_{i, j} \in \mathbb{I}$ be the $i$-th element of $j$-th array. You can select at most $k$ numbers from all arrays but if you pick $a_{i, j}$, you have to ...
163 views

### Sort 2D arrays so that cost of reaching new position as described at each iteration is minimized

Problem is as following: We are 8 trumpet players in an orchestra. There are for example 4 parts so there are always two players on the same part. Now, there are not always the same two players ...
238 views

### Topological sorting colored tree

EDIT: The most general case I need is not a tree but any Directed Acyclic Graph. I have a directed acyclic graph. I need to sort it in a list so that in the list every node comes after any node it ...
32 views

I have a set S of (key, value) pairs and a large number of subsets of S. I'm looking for a ...
212 views

### Minimal shift operations to sort an array

I have been stuck on this sorting problem for a while now: Given an array of length N find the minimum number of shift operations in order to sort the array. A shift operation is defined as shifting ...
468 views

### Proof of QuickSort algorithm correctness

Recently I’ve studied QuickSort and understood its general idea. Basically, we do the following: Pick an element from the array (no matter which one and how in this context) Rearrange elements in ...
42 views

### Is there an existing algorithm for this type of sorting?

This TED-ED video talks about some of the most basic sorting methods (bubble sort, insertion sort and quick sort,) in response to a scenario where a librarian ends up with a stack of 1,280 unsorted ...
2k views

### When average , worst and best case time complexity happens in quick sort?

I know recurrence relation corresponding to quick sort worst case is $T(n)=T(n-1)+T(0)+\Theta(n)$ and time complexity is $O(n^2)$. This happens when we select pivot which is either largest element ...
25 views

### Spatial index search that returns sorted results

I need to perform a spatial index search while also sort the results by one of the dimensions. Backstory: I have a map with lots of 2D objects and when the user interacts with the map I need to ...
412 views

### Minimum number of adjacent swaps needed to sort a circle of elements

I have been thinking about some problems in combinatorics and I came across a problem I'm having trouble with. Suppose you have a list $L$ of length $n$ (wlog the elements of the list are 1,2,3,...,n)...
62 views

### MergeSort k arbitrary words in linear time

Given $k$ arbitrary words, such as $\{\text{"fjqke"}, \text{"gbqig"}, \text{"a"}\}$, is there a way to mergesort these words in linear time so that the final output would be "abefgggijkq"? I tried to ...
322 views

109 views

### Why do you need at least ln(n!) many comparison to sort a list?

"If every element comparison (testing whether $a_i \le a_j$ ) provides at most one bit of information, argue that you need at least on the order of $\ln(n!)$ many tests/comparisons to sort the list." ...
955 views

### How to compare an element with other elements within an array efficiently for a condition

I need to compare each index with one another and associated array value as well. For example, ...
1k views

### Why does Radix sort require stable digit sorts?

I'm reading the CLRS book and have a question about the following quote from the book. In order for radix sort to work correctly, the digit sorts must be stable. Why is stability required? Wouldn'...
314 views

### In this implementation of Hoare-partitioning Quicksort, why are additional checks for $i \leq j$ needed?

I am looking at the following implementation of Quicksort that uses Hoare partition scheme (two approaching indices $i$ and $j$ starting from either end of the array). I am having trouble seeing why ...
69 views

### Upper bound on the average-case runtime of shell sort

I found that shell sort with the gaps of Fibonacci sequence has the lower bound complexity $\Omega(N \log N)$ in average cases. I want to know the upper bound complexity in average cases, so I write ...
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[...
338 views

### What is the real reason that Bubble Sort runs at O(n) in best case?

In this link https://techdifferences.com/difference-between-bubble-sort-and-selection-sort.html it says that the best case of bubble sort is order of n due to the fact that there would be only ...
62 views

### Sort arrays $A$ and $B$ of the same elements using only comparisons between an element of $A$ and one of $B$

Premise: Let $A := [ k(1), k(2), ..., k(n) ]$ and $B:=[ l(1), l(2), ..., l(n) ]$ be two Arrays where $k$ and $l$ are permutations. (What I'm trying to express: $A$ and $B$ contain the same elements in ...
437 views

### Maximum number of segments with no intersection [duplicate]

This is an interview question. Suppose you have an array of n segments, when each segment is a pair of two integers: start point and end point. For example: ...
98 views

### findMax reduce to sort

Can I reduce the find max (or find min) problem to the sort problem? Because if so, knowing the lower bound for find max is Ω(n) I can also infer that the lower bound for sorting is Ω(n) too? I'm ...
42 views

### Is this algorithm for partial ordering of sets complete and sound?

I need to build a partial order tree of sets for analysis. Where the order is defined as A <= B <=> for all x in A, y in B, x <= y. I realized that if ...
38 views

### Algorithms / heuristics for a distributed sorting problem

The setting: There's a cluster of $k$ computers (= nodes). For simplicity, assume their hardware is identical. The network topology can be complicated, but let's simplify and assume it's a clique ...
75 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 ...
71 views

### Merge Recurrence Analysis [duplicate]

Say I have a dynamic array of the proper length $n$. A sort pivot is given. I run the sort algorithm, wait, and get $j$ unbalanced pivots. Is the time complexity $O(n\log n)$ or has it destabilized ...
76 views

### Run-time of Sorting Algorithm

Problem Consider the pseudocode for the sort algorithm below, which takes as input an unsorted array $A$ of $n$ integers with no duplicates. ...
123 views

### Is there a $O(n\frac{\log{n}}{\log{k}})$ sorting algorithm?

I am trying to figure out a sorting algorithm which can be used in $O(n\frac{\log{n}}{\log{k}})$ sorting time. I am allowed to use $k$ registers that can store key value pairs and these registers can ...
95 views

### Minimum number of comparisons to sort k elements among n

In The Art of Computer Programming D. Knuth, in section 5.3.3 Minimum Comparison Selection defines : $V_t(n)$ as the minimum number of comparisons needed to find the $t^{th}$ largest element of $n$ ...
1k views

### Hoare partitioning scheme in Quicksort

I'm reading about Quicksort algorithm, specifically using the Hoare partitioning scheme. Wikipedia page says, that when choosing a pivot element one can use both ...
172 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 ...
60 views

### Selection Sort Analysis

I'm having difficulty understanding the big-O analysis of the selection sort algorithm. Here is my pseudocode (with line numbers): ...
107 views

### Single Pass in Memory Indexing

I was reading single pass in memory indexing and had few doubts. Why is the time complexity of SPIMI O(T) where T are the token. We know that before writing blocks to Disk, we have to sort ...
299 views

### Best time complexity of sorting numbers in range [1…n log n]

given an array $A$ of $n$ numbers in range $1$ to $n\log n$, what is the time complexity of the best method to sort them? The answer is $O(n)$ but I don't understand this. of course counting sort ...
35 views

### Approximately sorting integers by many criteria

Given $k$ functions $f_0, f_1...f_k$, a large dataset of size $n$, is there an algorithm that will "approximately" sort the dataset according to all of the functions so that "most" items of the ...
37 views

### Sorting Algorithm which prevents strings with at least one identical char from being next to each other

Imagine this Table: All combinations represented in the table (1,2 ; 1,3 ; 1,4 ; etc.) are stored as strings in an array with a total of (n^2-n)/2 elements (combinations). I'm looking for an ...
I am interested to know whether the time complexity of following algorithm is $O(n^2)$ or $O(n\log n)$. Here is the implementation: ...
Why is this sort algorithm correct? Many thanks! Task: Suppose all elements in an array with length $n = 2^m$ are in descending order: $a_1 > a_2 > ... > a_n$, we need to turn them into ...