# Questions tagged [sorting]

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

692 questions
Filter by
Sorted by
Tagged with
61 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): ...
109 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 ...
304 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 ...
43 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 ...
174 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: ...
380 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 ...
410 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 ...
309 views

### Median of medians: bound on pivot position

If I understand correctly (from reading Wikipedia), median-of-medians pivot selection makes quickselect $O(n)$ because the pivot is guaranteed to be in between the 30th and 70th percentiles and so at ...
181 views

### Nine-input sorting network of optimal depth with minimum number of comparators

In the research on sorting networks, two parameters are typically of interest: The number of comparators required and the depth required. They have practical implications for throughput and latency. ...
57 views

### sort n numbers in the range [0,1] without multiplying or dividing

Given an array with n real numbers, each in the range [0,1], I need to sort them. Moreover, the only operations that are allowed are comparisons or copying. It means I cannot multiply or divide the ...
257 views

### How to implement insertion sort on linked list with best case performance O(n)?

I have an almost sorted linked list containing N distinct elements with only 1 element not in it's place. Every implementation I have seen start insertion from the beginning (unlike insertion sort on ...
69 views

### Dijkstra Partitioning Algorithm : Special Case

I have been exploring Dikstra partitioning Algorithm. Below are my given: R = Red W = White B = Blue I have this unpartitioned array. ...
513 views

### Merge sort worst case running time for lexicographical sorting?

A list of n strings each of length n is being sorted in lexicographical order using the merge sort algorithm. Since we have to take care of comparison of each character in the strings so the merge ...
64 views

### Sorting some set of number

Let $U=\{1,2,3\cdots m-1\}$ and some $n$ keys from $U$. Is it possible to sort these $n$ keys in $O(n \log \log n)$ time using $O(n)$ space? Model of computation is RAM.
39 views

### Level sums, displacements: how to determine their effect efficiently?

Let $R =\mathbb{Z}/N \mathbb{Z}$. Let $f:R\to \mathbb{R}$, $\rho:R\to \lbrack 0,1\rbrack$. We assume that it takes trivial time to compute any given value $f(m)$ or $\rho(m)$. Define S(\delta,m) = ...
3k views

### In place and Out place sorting meaning?

What is the meaning of in place and out place in sorting? What are the difference of two of them? Couldn't find any good explanation in the internet.
879 views

### Fast, stable, almost in-place radix and merge sorts

I've developed LSD radix sort algorithm that is stable, about as fast as the classic LSD radix sort, require only $O(\sqrt{RN})$ extra space when we sort into R buckets. The same technique also ...
59 views

### Why is my own implementation of Bubble Sort so much slower than another one I found online?

I wrote my implementation of Bubble Sort according to my understanding of the general principle of how the algorithm works, and then compared it against another implementation I found online. ...
72 views

### Optimal ordering of items with contradictory constraints

I've got a set of items that I'd like to sort into a list. The items have two independent sets of constraints that the ordering should respect: A set of hard constraints that must be satisfied, e.g.: ...
354 views

### Why does the insertion-sort algorithm have a quadratic instead of a quasi-linear time complexity?

Can someone explain how the insertion sort have quadratic time complexity and not quasi-linear time complexity in the worst-case? Even in the case of a reversely sorted list, it's not like it'll have ...
44 views

### Efficiently find elements which are out of place in an otherwise sorted list

I have some data that includes two columns for dates, and I want to retrieve - based on these two columns - all the instances where an illegal operation has occured. An operation is illegal if the ...
123 views

### Partitioning through block moves to the end

Suppose we have a binary string $s$. We wish to partition this string in a series of $0$s followed by $1$s (alternatively: we wish to sort), using only one operation: moving three consecutive elements ...
47 views

122 views

### An algorithm for k-way array partitioning

I am trying to implement samplesort in MPI. The first step of samplesort is to partition the array with $n - 1$ splitters $s_1, s_2, \cdots, s_{n-1}$ into $n$ subsequences, where subsequence $i$ all ...
151 views

### Topological sorting and NP-hard proof

I meet a problem. I can find a sub-optimal solution, but cannot find an optimal one and cannot prove its NPC hardness. The problem can also be described as follows. Given a sequence \$X=\{x_1,x_2,...,...
174 views

### How to efficiently sort and filter a large iterator

Given an huge iterator (millions of random elements) and asked to obtain the top 10 elements in descending/ascending order. What is an efficient way or algorithm to do this? NOTE: The iterator size ...