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

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

0
votes
0answers
7 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
87 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
29 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
31 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
0answers
4 views

What function will allow me to pull data from a column in a data frame based on the value in the columns in R? [migrated]

I'm trying to pull data out of a dataframe from a specific column based on the value in the column. For example: ...
0
votes
3answers
63 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: ...
1
vote
2answers
78 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
31 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 ...
2
votes
1answer
43 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 ...
4
votes
2answers
68 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. ...
3
votes
2answers
43 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 ...
1
vote
1answer
37 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 ...
1
vote
1answer
44 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. ...
4
votes
1answer
47 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 ...
0
votes
3answers
61 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.
6
votes
0answers
32 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) = ...
1
vote
2answers
73 views

Which algorithm is used by STL sort? [closed]

I implemented my own shellsort, shown in plot below are the timings for it. 0 means std::sort, used for comparision 1 means single thread 2 to 12 means multi-thread (pthreads) Which algorithm is ...
1
vote
2answers
80 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.
3
votes
1answer
209 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 ...
1
vote
1answer
43 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. ...
3
votes
0answers
37 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.: ...
2
votes
1answer
49 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 ...
1
vote
2answers
30 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 ...
5
votes
0answers
110 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 ...
2
votes
0answers
17 views

Sorting Algorithm: Probability Bound For Randomized Inversion Swapping

Let $A = (a_1, a_2, \dots, a_n)$ denote an array of distinct values with an order defined. Consider the following randomized sorting algorithm. Let $m := 0$. Select a pair $(i, j)$ with $1 \le i < ...
0
votes
1answer
36 views

Can I make last part of counting sort become to be starting from lowest index?

Counting sort is originally like below code. ...
4
votes
1answer
59 views

A necessary [and sufficient?] condition for the number of comparisons required to sort $n$ elements

I am familiar with the decision tree based argument for the minimal number of comparisons required to sort $n$ distinct elements - Since there are $n!$ permutations on the $n$ elements, the decision ...
0
votes
2answers
90 views

Question regarding Hoare's partitioning scheme and a slight modification to it

This is the pseudocode on wikipedia for Hoare's partitioning scheme: ...
3
votes
0answers
47 views

How to find the top k pairwise product of in an array of integers?

Input: An array $a$ of integers $[a_{1}, \cdots, a_{n}]$, and a positive integer $k$. Output: The the top-k products of pairs in $a$. Example: $a = [7,6,5,4,3,2,1],k=3$ , output $(42,35,30)$, with ...
0
votes
0answers
17 views

Recursive insertion sort on mostly sorted data vs calling insertion sort on mostly sorted data

I'm currently doing an assignment on introsort, which does insertionsort o small data, quicksort on an data that is not too big, and heapsort if the data is too big. The assignment then asks: What ...
0
votes
1answer
36 views

Are there any estimated, imperfect or fuzzy sorting algorithms?

I'm implementing some estimation metrics that take samples of optimisation functions and estimate their properties. One of the metrics requires the data to be sorted; however, since the metric is only ...
2
votes
0answers
18 views

Anagram sorting with inversion count oracle

Given a permutation $P$ of an unknown array $U$ of length $N$ and a function $f(Q)$ that calculates the minumum number of swaps between consecutive elements of array $Q$ to reach $U$, what is the ...
-1
votes
2answers
104 views

Will we ever achieve a $O(n)$ general purpose sorting algorithm (or at least better than $O(n\log(n)))$?

I've been thinking about this question ever since I learnt about the $O(n\log(n))$ sorting algorithms such as MergeSort, QuickSort (average case is pretty much worse case with a good choice of a pivot)...
0
votes
0answers
24 views

Comb Sort Best Case

Why the best case for Comb Sort is O(nLogn) ? can someone explain why? also on other sites they state that the best case is O(n). Which is accurate?
-1
votes
1answer
43 views

Sorting by Comparisons Proof

I came across this question while solving past papers and I'm not very sure as to how to construct my proof for the second and third question. I understand the concept that can be applied here would ...
1
vote
1answer
107 views

Is the outer loop in typical bubble sort algorithm precise?

I analized the bubble sort algorithm and I cannot see why they "implemented this way". I wrote down the results as the two loops performed their works and, with my small testing arrays, the outer ...
1
vote
1answer
42 views

Efficient streaming sort

Consider following task: we have an input of N+1 lines, where first line contains N - number of items, and then we have N lines, each one contains one item, which is a tuple (number id, number m), id &...
0
votes
0answers
16 views

Lexicographic sorting algorithm for n items labeled with R,V,B

Let A be an array A[0..n-1]. The array has n items. Each item is labeled with one of these letters: {R,V,B}. For example, A[0].label=V, A[1].label=R, etc. What is the best algorithm for sorting ...
0
votes
1answer
12 views

Merge Sort meaning of a bit part of code

I am studying this part for a merge sort implementation: ...
0
votes
0answers
12 views

finding and minimizing merge sort algorithm runtime analysis

let's say I have an array of the size n,I want to divine it to k new arrays of the size n/k.-what's the running time of this step may be?**I thought since when we split an array to 2 we look at it ...
0
votes
0answers
24 views

Sorting an array of length n with k distinct elements in O(kn) [duplicate]

I have an array of the size N with K distinct elements.We don't know what the K is. I would like to sort this array in O(kn). I have found this answer and I would like to understand what does exactly @...
1
vote
2answers
45 views

Sort already sorted array - after changing several elements

Problem: Given $S$ — a sorted array where some of the elements were randomly changed, assuming that you're provided with an $S_1$ — an array of indexes of changed elements. Design an ...
2
votes
0answers
113 views

Finding unique topological ordering wrt to another vertex ordering

Given a directed acyclic graph with $n$ nodes labeled from $1$ to $n$, what is an efficient way to produce the unique topological ordering with lower labeled nodes prioritized over higher labeled? ...
1
vote
1answer
60 views

Sort binary matrix by swapping columns to make subrectangle of ones with maximum size

We have given binary matrix (matrix containing only 1 and 0) of size $n\cdot m$. We want to order the matrix such that the biggest rectangle containing only ones is with maximum size. For example if ...
1
vote
1answer
34 views

Optimal 4-input sorting network

In his paper The Bose-Nelson Sorting Problem (1973, Chapter 15 of A Survey of Combinatorial theory on page 163 available on Google books), Knuth says that the optimal bound of 5 comparators for a 4-...
2
votes
1answer
115 views

Algorithm to sort n numbers from 0 to $n^m$ in $\mathcal{O}(n)$? where m is a constant

So i came upon this question where: we have to sort $n$ numbers between $0$ and $n^3$ and the answer of time complexity is $\mathcal{O}(n)$ and the author solved it this way: first we convert the ...
1
vote
1answer
131 views

Sorting a stack using Bubble sort

How to sort a stack using bubble sort? Can use another stack if necessary.
0
votes
1answer
63 views

Is this lower bound proof for the comparison-based sorting problem correct?

Here is a lower bound proof for the comparison-based sorting problem: Any comparison-based sorting algorithm can be considered to work by putting elements into their final positions one by one (Take ...
2
votes
1answer
66 views

Exact Analysis of the Merge Sort

When doing the "inexact" analysis of the Merge Sort, the literature that I have seen usually consider that the input is an array with a even quantity of numbers and the recurrence relation is: $T(n) =...
3
votes
1answer
45 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 ...