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
5 views

Question: Comparison of merge sort and radix

Since Merge Sort algorithm has a time complexity of $\theta(n\times\log_2n))$. Show how Radix Sort algorithm can be more appropriate then Merge Sort when $ d < \log_2n $. $d$ equals to $\log_bk$ $...
0
votes
0answers
17 views

Sorting a list using Quick Sort

I want to use Quick-sort on this list: [17, -10, 7, 19, 21, 23, -13, 31, 59]. The pivot is the first element (17). I only want to sort until the pivot (17), is the correct position. I want to work ...
-1
votes
0answers
10 views

What am I missing from this code to sort from smallest to largest and print at all times? Then remove all even integers and print out again? [on hold]

How to store them in a singly linked list and sort them from smallest to largest and print them at all times. Then remove all even integers and reprint them? ...
1
vote
1answer
36 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
30 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
68 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[...
0
votes
0answers
50 views

Is there a name for this sorting mechanism? [duplicate]

The sorting algorithm gets an object out of a list of total objects, and then removes that object from the list, by moving the object at the end to the position where the object was, and creates the ...
1
vote
2answers
50 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
52 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 ...
1
vote
1answer
36 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: ...
0
votes
0answers
12 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
1answer
24 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 ...
-1
votes
0answers
8 views

Filling Boxes with Objects under 3 Conditions

For a Programming project i have been given a Box with Objects while having 3 Conditions that have to remain true: We have been given a box with a given number of Compartments (e. g. 3x3). Now we ...
0
votes
1answer
30 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
21 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
51 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
54 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 ...
0
votes
0answers
51 views

Inductive Proof 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. ...
1
vote
1answer
45 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
73 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
45 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
116 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
0answers
31 views

Sorting an array consisting random numbers

In this sorting animation, I saw that heap sort and merge sort works best for an array containing random numbers. But, what about if we compare these sorting algorithms with Radix and introsort? In ...
0
votes
2answers
32 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
34 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): ...
0
votes
0answers
18 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
109 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
68 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
85 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
70 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 ...
3
votes
1answer
96 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
74 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
45 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
71 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
46 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
50 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
62 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
33 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
91 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 ...
0
votes
3answers
146 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
296 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
47 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
39 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
72 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
31 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
112 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
18 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
57 views

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

Counting sort is originally like below code. ...