Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [sorting]

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

0
votes
0answers
22 views

Quick access to top element of subsets of elements

I have a set S of (key, value) pairs and a large number of subsets of S. I'm looking for a ...
-1
votes
1answer
28 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 ...
0
votes
1answer
57 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 ...
1
vote
1answer
24 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 ...
2
votes
3answers
44 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 ...
0
votes
0answers
15 views

How to sort a woven shuffled stack

Say you have sort of a "woven shuffling situation" going on, sort of like this. Or that just looks like a regular shuffle for the most part. I'm trying to show the situation where something can be ...
1
vote
0answers
17 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 ...
2
votes
1answer
41 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)...
1
vote
1answer
51 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 ...
2
votes
2answers
48 views

Finding the k-th smallest ternary sum of elements from three different arrays

The problem goes like this: Given arrays $\{ a_i: 0\leq i \leq n-1 \},\{ b_i: 0\leq i \leq n-1 \} $ and $\{ c_i: 0\leq i \leq n-1 \}$, we want to know what is the $k$-th smallest combination $a_r+...
1
vote
1answer
44 views

Sorting n element using Fibonacci Heap

How can I design a sorting algorithm of n elements using a Fibonacci Heap? Will it be a flavoured version of heap-sort where I replace the heap data-structure with Fibonacci Heap? Your help is ...
-2
votes
1answer
18 views

Few questions about Mergesort and Recirsion algorithms

Can we use recursive algorithm to find the greatest element of a finite list when numbers are unsorted. How to use recursive algorithm to find the least element of a finite list of unsorted numbers ...
0
votes
0answers
15 views

Merge Sort Recurrence analysis for list of strings [duplicate]

I saw this question and tried to find out what the time complexity was: Using the recurrence relation for Merge Sort: $$T(n)\; =\; merge\_time\; +\; 2T(n/2)$$ Here, since we have a list of strings, ...
0
votes
1answer
47 views

Quick Sort - 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 (...
0
votes
2answers
36 views

Sorting in a Priority Queue

Does a priority queue Queue<K,V> always sort its elements based on the value of each element or its key? I know than the priority in the queue is based on ...
1
vote
2answers
64 views

Smallest possible sorting network for given permutation

I need to build a sorting (comparator) network using comparators for a specific permutation on a set $x_1, \dots, x_n$. The solution should not be a general sorting network that sorts every ...
5
votes
3answers
123 views

Can we remove duplicates faster than we can sort?

The problem is (integer) duplicate removal, which can also be perceived as producing the image of an evaluated function (of integers): Given a sequence $S_\text{in}$ of $n$ integers, produce a ...
1
vote
1answer
38 views

Optimize sorting matrix entries by row and column

I am writing a routine to store an $M$-by-$N$ sparse matrix in a balanced binary tree. The insertion routine calls a comparison function to determine where a new matrix entry $(i,j)$ should be ...
1
vote
0answers
55 views

How does prefix summing the count histogram in counting sort result in an array of output indices?

My implementation of counting sort is based on the description I found here. I've also included my code in this REPL, but here it is: ...
2
votes
1answer
28 views

Does simultaneously finding max/min in array of coordinates by x and y increase comparisons?

I have an unsorted array of (x,y) coordinates and need to find the min/max for both (x) and (y) separately so that I can build a bounding box using $O(\frac{3n}{2})$ comparisons. If I use this ...
0
votes
1answer
70 views

Sorting n elements in worst case of $\sqrt{n}\log n$

Can $n$ elements be sorted in a worst case time of $\sqrt{n}\log n$? Why or why not? I've seen algorithms being sorted in the worst case of $n\log n$, so why can they be or cannot be sorted in $\sqrt{...
-1
votes
2answers
70 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." ...
0
votes
1answer
31 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, ...
1
vote
1answer
42 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'...
0
votes
0answers
21 views

Algorithm for gaps in coverage of half-closed intervals

I have a collection of pairs of half-closed intervals of reals (actually datetimes, but fairly close to continuous). I need to determine if there are any gaps in the coverage of that datetime. They ...
1
vote
1answer
52 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 ...
1
vote
0answers
36 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 ...
0
votes
2answers
524 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[...
1
vote
2answers
55 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 ...
2
votes
0answers
55 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 ...
2
votes
1answer
44 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: ...
-1
votes
0answers
13 views

Lower Bound of a K-element Comparison sort

I'm trying to find the lower bound of a comparison sort, if I can find the minimum of k elements in one comparison. I'm not sure how to set up a decision tree to solve this problem.
1
vote
2answers
37 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 ...
0
votes
1answer
32 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 ...
1
vote
0answers
24 views

Algorithms / heuristics for a distributed sorting problem

The setting: There's a cluster of $k$ computers (= node). For simplicity, assume their hardware is identical. The network topology can be complicated, but let's simplify and assume it's a clique ...
0
votes
2answers
54 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
56 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 ...
1
vote
1answer
50 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. ...
2
votes
1answer
78 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 ...
2
votes
0answers
55 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$ ...
4
votes
1answer
190 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 ...
0
votes
2answers
52 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
37 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): ...
1
vote
0answers
32 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 ...
1
vote
2answers
123 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 ...
5
votes
1answer
31 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 ...
2
votes
1answer
32 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 ...
0
votes
3answers
72 views

Big O notation for Sorting Algorithm

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: ...
2
votes
2answers
107 views

An algorithm to turn descending order into ascending order, but why correct?

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 ...
-1
votes
1answer
95 views

Finding recurrence equation for a variant of insertion sort [closed]

I have a variant of Insertion sort (recursive version) that we call split insertion sort because there are two kinds of input. The input array has both numbers and alphabets, hence we have to sort ...