Stack Exchange Network

Stack Exchange network consists of 175 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.

1
vote
2answers
32 views

Find m smallest elements in an array of size n where m = n/2

So we have an unsorted array, we need to find the first $m$ elements in ascending order (or $m$ smallest elements) where $m = \mathrm{array.size}/2$ (or $n/2$). How would we do this in linear $O(n)$ ...
2
votes
1answer
58 views

How to best maintain a sorted list from a stream of integers?

If I have an incoming stream of integers how can I best maintain a sorted list of them? The only way I can think of is to binary search for the position and shifting the remaining elements to the ...
1
vote
2answers
108 views
4
votes
1answer
29 views

Sorting strings with “before” and “after” constraints

I'm trying to solve a constraint-satisfaction problem for a project of mine that seems like it should have a well-known solution, but I can't for the life of me seem to find it described anywhere. I'...
3
votes
1answer
18 views

Are comparison sort algos appropriate for SUBJECTIVE sorting?

I've been tasked with creating an online feature that ranks 50 fantasy characters from a variety of domains based on combat acumen and polls users one which one is the most powerful based on their ...
-1
votes
0answers
19 views

What is the time complexity for this program [duplicate]

What is the time complexity for this program. Select the right answer: A- $\Theta(n\log{n})$. B- $O(\log{n})$. ...
2
votes
0answers
36 views

Worst case for linear-time k'th smallest element algorithm?

There's an algorithm for finding the k'th smallest element in an unsorted array similar to quickselect: kthSmallest(arr[0..n-1], k) 1) Divide arr[] into ⌈n/5⌉ groups where size of each group is ...
0
votes
0answers
26 views

Bubble sort that ignores rightmost sorted parts

Initial Bubble sort pseudocode(Typical): 1)foreach Element in array 2) initialise a flag that flips whenever a swap is done 3) Starting from the element, attempt to swap and update flag 4) If ...
1
vote
1answer
62 views

Implementation of QuickSort to handle duplicates

I have this past year question based on the following scenario: When the list of items to be sorted contains a lot of duplicate values, we can improve QuickSort by grouping all the values that are ...
3
votes
1answer
47 views

Random observations of a total ordering, how much they tell us?

Suppose we have a total ordering over elements $a_1,a_2, ..., a_n$, meaning there is permutation $\pi$ such that $a_{\pi(1)}<a_{\pi(2)}<...<a_{\pi(n)}$. But we don't know $\pi$. What we know ...
-2
votes
2answers
45 views

For sorting 10^9 unique 9-digit numbers, would radix sort or counting sort be faster, and why?

For sorting $10^9$ unique 9-digit numbers, would radix sort or counting sort be faster, and why? I know that radix sort is $O(nk)$ and counting sort is $O(n+k)$, but can’t understand how to apply ...
4
votes
2answers
81 views

Sorting “almost sorted” array in $O(n\log\log n)$

Given array $A$ of length $n$, we call it almost sorted if there are at most $\log n$ indices satisfying $A[i] > A[i+1]$. Find an algorithm that sorts the array in $O(n\log\log n)$. My ...
0
votes
2answers
58 views

Time complexity of quicksort for arrays in increasing or descreasing order

Two $n$-size arays are given: $n_1$ is in decreasing order and $n_2$ is in increasing order. Let $c_1$ be the time complexity for $n_1$ using quicksort, and $c_2$ the time complexity for $n_2$ using ...
0
votes
1answer
34 views

Quicksort T(n)=2T(n/2)+n

In Quicksort we devide the array in to about an half (not worst case) and we have left and right sides so it is 2T(n/2), now why in the end it is T(n)=2T(n/2)+n as we may need to go over all the array ...
0
votes
1answer
18 views

Sorting on non-linear topology

Disclaimer. What I'm going to ask about below may seem to be "Topological sorting". To my understanding, it is not. The latter runs in linear time, while I'm looking for a modification of the regular ...
1
vote
1answer
193 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 (...
1
vote
1answer
122 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 ...
2
votes
1answer
53 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 ...
6
votes
1answer
131 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 ...
4
votes
1answer
77 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 ...
0
votes
0answers
32 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
35 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 ...
1
vote
2answers
146 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
26 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
180 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
17 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
19 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 ...
3
votes
2answers
96 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
52 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
78 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
52 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
19 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
171 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 (...
1
vote
2answers
46 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
74 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
129 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
43 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
64 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
80 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
78 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
34 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
149 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'...
1
vote
1answer
79 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
43 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
1k 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
82 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
58 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
67 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: ...