All Questions
Tagged with sorting computer-science
44
questions
0
votes
1
answer
452
views
Merge two sets, list and tree
We are given two sets $S_1$ and $S_2$.
We consider that $S_1$ is implemented, using a sorted list, and $S_2$ is implemented, using a pre-order sorted tree.
I have to write a pseudocode, that ...
- 7,879
1
vote
1
answer
103
views
correcting an invalid binary heap in $\Theta (n)$
We are given a binary max (every node is larger than its children) heap with $n$ elements.
We now change $\frac{n}{4}$ of the elements at random. We don't know which ones and to which value. And so, ...
- 12.8k
4
votes
1
answer
3k
views
SQRTSORT from Vazirani's book on algorithms
I study the Algorithm book and saw the following exercise. I couldn't solve it. This is not homework, nor exam. Just reading some material on algorithms for preparing entrance exam. Any nice idea or ...
- 44
0
votes
2
answers
97
views
The value of loop variable at the end of a loop in the insertion sort
I am looking at the algorithm of the insertion sort:
Input: $A[1 \dots n]$
...
- 7,879
6
votes
1
answer
355
views
Reference Request on Order Theory topics
I am looking for some references (especially a good recent book) that covers important topics involving partial orders such as: order polytopes, sorting/selection in partially ordered sets, upper and ...
- 917
23
votes
2
answers
11k
views
What is meaning of strict weak ordering in layman's term?
I gone through many pages using Google, but not understand exact meaning of Strict-weak Ordering term.
I have this requirement while sorting strings.
- 474
2
votes
2
answers
202
views
Could graph theory aid in the understanding of comparison sorting algorithms?
I am interested in computing the exact number of comparisons that are needed to sort a list. See this wikipedia article.
Up to $n=15$, we know how many comparisons between elements one must make to ...
- 7,148
1
vote
1
answer
713
views
Minimum number of moves to create a new permutation
Edit: Before you begin, please note that a move refers to swapping a pair of letters (thanks to ferfer93)
Ok, so I understand the title is a bit ambiguous, so I'll clarify it further below:
Let us ...
2
votes
1
answer
181
views
A question about sorting
I've always been thought that the fastest way to sort an array of numbers has complexity $O(n \log (n))$. However, radix sort has complexity $O(kn)$ where $k$ is the number of bits. There are even ...
- 1,511
0
votes
1
answer
127
views
How do I estimate the time taken? (Growth Rates)
Suppose you have a program that solves an AI problem. When the problem size is $N = 1,000$ your program takes 10 seconds to find a solution. Estimate the time it will take to solve a problem of size $...
- 171
0
votes
1
answer
346
views
Optimizing Mergesort by Parallelism
Can someone explain the math involving with the performance of a parallelized implementation of mergesort?
There's another question that talks about the performance of mergesort without parallism ...
user13327
3
votes
2
answers
992
views
Time complexity of sorting a partially sorted list
Assume a sorted list of $n$ elements followed by $f(n)$ elements in random order.
How would you sort the whole list given the following:
a) $f(n)=O(1)$
b) $f(n)=O(\log n)$
c) $f(n)=O(n^{1/2})$
d) ...
- 31
5
votes
5
answers
35k
views
7
votes
2
answers
243
views
Quicksort with Trivalued Logic
Does anyone know a way to do a quick sort with trivalued logic?
The problem I’m trying to solve is this: I’m trying to display a view of a complex 3d object from a given viewing angle. I’ve broken the ...
