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

learn more… | top users | synonyms

1
vote
1answer
23 views

Sort an array based on dependencies

I have an array of objects, each of them has a numeric id and another array attached to them. The array in the object contains the dependencies of that object. Each dependency is an id from the other ...
0
votes
1answer
20 views

Use of sorting in counterexamples for equations

I came across a question which asked how sorting would help in searching for counterexamples to the conjecture that $$u^6 + v^6 + w^6 + x^6 + y^6 = z^6$$ has no non trivial solutions in integers. The ...
5
votes
2answers
65 views

Online sorting without modifications

There is an array with $n$ places. There is a stream of $n$ unique numbers that arrive at a random order (permutation selected uniformly at random). Whenever a number arrives, we must put it ...
3
votes
1answer
34 views

Generalized sorting algorithm on partially ordered set generated by a relation

Assume we have a finite set $X$ of elements and any relation $\preceq$ on $X$. Such a relation may or may not generate a reflexive transitive anti-symmetric relation $\leq$ on $X$ (a partial order). ...
0
votes
2answers
26 views

Is there a standard recently-used algorithm based on time and usage count?

Everyone is familiar with most recently used files lists in software and in OSs like Windows. Some programs just sort by time. I've always been fairly annoyed at this. Others like Windows take usage ...
1
vote
1answer
59 views

On the fly manipulation of operators

Assume that you are writing sorting algorithms, and that you want the ability to select between ascending and descending order. The only change required to do this for comparison sorts is to use the ...
2
votes
1answer
64 views

Why isn't selection sort O(n log n)?

We make $n$ insertions and each insertion targets a list of size $k\le n$, so we can make a binary search which takes maximum $\log k\le \log n$. So why isn't the running time of selection sort $O(n \...
1
vote
0answers
11 views

Similarity of Objects based on multiple variables

I am working on a Simple hypothetical Allocation Problem. I have some Virtual Machines(VM) placed on a Physical Machine (PM). The VMs and PMs have 3 common variables, CPU, Memory, Network. The VMs ...
6
votes
1answer
301 views

What is the difference between oblivious and non-oblivious merging, sorting etc

Algorithms can either be oblivious or non-oblivious, but what is the actual difference between the two?
2
votes
1answer
34 views

Why %RSD of execution times, while sorting hundreds of arrays, is lower for larger arrays of random integers?

I am experimenting with the sorting of arrays and their execution times. While using bubblesort, insertsort and ...
3
votes
1answer
58 views

Why does merging two sorted arrays take 2N - 1 comparisons?

A friend of mine asked me a question on how to prove that merging two sorted arrays requires at least 2N - 1 comparisons Prove that merging two sorted arrays of N items requires at least 2N-1 ...
0
votes
0answers
21 views

Why is Knuth Sequence's slower than regular ShellSort?

I have tried running it over and over again with varying input sizes. But it keeps showing Donald Knuth's sequence as slower? Why is this? I figured it would be faster. ...
4
votes
0answers
105 views

Find the median of two sorted arrays of different size in O(min(log(n),log(m)) complexity

Given two sorted arrays of length m,n, how do I find the median of the union of these two arrays in O(min(log(n),log(m)) time? I've been trying to come up with an algorithm (and a proof) for several ...
2
votes
1answer
19 views

Transitivity of concat comparison

I am trying to solve the problem of finding the permutation, amongst all possible ones, of an array of strings, where the concatenation of them compares smallest lexicographically. I solve it with an ...
1
vote
1answer
43 views

How often can a linear speed sort succeed?

Let's say you have sorting function. It is allowed to exit with failure (but if it does not it must return a correctly sorted sequence). It is also $\mathcal O (n)$. What kind of bounds can we place ...
2
votes
0answers
55 views

Fastest in-place sorting algorithm for Epochtime

I need to sort a lot of rows (from 1GB to 3GB) by EpochTime (a single value of every row). What is the fastest in-place sorting algorithm for this task? Radix Sort? I would like the fastest sorting ...
8
votes
0answers
45 views

Efficiently inserting into list keeping number of inversions minimal

Assume two lists of comparable items: u and s. Let INV(u) be the number of inversions in u. I am looking for an efficient algorithm to insert the items of s into u with a minimal increase of INV(u). ...
0
votes
0answers
36 views

Is this sorting algorithm valid and able to run in O(range of input set) time?

I imagined a sorting algorithm that sorts an array in O(r) time, where r is the range. Is this already an algorithm (if so, which?), or have I made a mistake calculating the running time (probably). ...
3
votes
3answers
400 views

Are there adversarial inputs for randomized quicksort?

Someone recently claimed that there's an adversarial input for randomized quicksort; he referenced this paper. This defies my intuition because there are results that say that randomized quicksort ...
0
votes
1answer
18 views

How to design a top-1 select algorithm to maximize a variable and minimize other variable?

I want to implement an algorithm thats select the best group, which maximize the variable A and minimize the variable B. For instance, I have the following groups: G1 - A = 10 B = 2 G2 - A = 10 B = ...
0
votes
1answer
52 views

Difference between Binomial and Fibonacci heap (marking)

I am confused why Binomial heaps do not utilize marking. Concerning Fibonacci heap children: ...
-4
votes
1answer
45 views

How do you call this typical file name order? [closed]

log1.gz log10.gz log100.gz log101.gz log102.gz log103.gz
1
vote
1answer
38 views

Inplace sorting of variable length records

Is there an in-place algorithm for sorting variable length records? For example a vector of arbitrary length strings. Most provided in-place algorithms assume that you can switch two elements ...
15
votes
4answers
3k views

What is the most efficient constant-space sorting algorithm?

I'm looking for a sorting algorithm for int arrays that doesn't allocate any byte other than the size of the array, and is limited to two instructions: SWAP: swap the next index with the current one;...
1
vote
2answers
380 views

What is the fastest online sorting algorithm?

Quoting Online algorithm from Wikipedia: In computer science, an online algorithm[1] is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed ...
1
vote
0answers
22 views

Encroaching lists as a measure of presortedness: is it really one?

Encroaching Lists as a Measure of Presortedness is the title of a 1988 paper by Skiena that describes the concept of encroaching lists, how to generate them from a sequence, how they can be used as a ...
4
votes
1answer
66 views

Sorting array with at most two inversions

I have created an algorithm to sort an array of size $n$ with at most 2 inversions with exactly $n$ comparisons in the worst case. I have no idea how to prove that it is optimal in terms of the ...
5
votes
3answers
1k views

Complexity of sorting a 1-sorted array

A $k$-sorted array is one in which every element is at most distance $k$ from its position when the array is sorted. The complexity of sorting such array is $O(n\log k)$. But if $k=1$, then $\log k=0$...
1
vote
1answer
39 views

heapify last 3 lines

I'm following http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec04.pdf Last 3 lines of ...
1
vote
2answers
68 views

How to calculate the mergesort time complexity?

Recently while reading a book I came across the following statement: Mergesort works by dividing nodes in half at each level until the number of nodes becomes 1 hence total number of times we ...
4
votes
1answer
32 views

Combine $k$ sorted lists into one

Say I have $k$ sorted lists of the same size $n/k$, and I want to combine them into one sorted array in $O(n\log k)$ time. The solution I came up with is to recursively halve the lists until you ...
0
votes
1answer
110 views

Sorting algorithm that moves element to a 2-dimensional array

I had an idea for a sorting algorithm wich is very fast, but can (potentially) use a lot of memory. I'm not a Computer Science student/graduate, only a self-taught programmer so I don't know how to ...
3
votes
2answers
53 views

Are there sorting algorithms that take advantage of a metric space?

We know comparison sorting algorithms use the ternary information (lt, eq, gt) garnered from a single comparison to make decisions about what to do next. Is there any research into using a metric? ...
0
votes
1answer
39 views

Rank athletes by weighted criteria

I have a structure. that consist of the following: ...
0
votes
1answer
64 views

sorting a sorted array that has been inc/dec by random numbers

If given a sorted array of n distinct positive integers. And each element is incremented or decremented by a number between 0 and X. For positive integer X that is a function of n. Formulate an ...
0
votes
0answers
7 views

Which algorithm is best for random and reversely sorted data? [duplicate]

So after studying and analyzing the time complexities of few algorithms like quick sort, merge sort and insertion sort, i think quick sort is better for random and reversely sorted data.Am i correct ...
1
vote
2answers
81 views

What is the significance of a Θ-bound on the running time of Mergesort?

While studying algorithm analysis I found that there is something called tight bound and there is some mathematical formula to support it. Given: Mergesort takes $\Theta(n \log n)$ compares to ...
0
votes
1answer
50 views

Merge k sorted arrays of exponentially increasing lengths

I've seen many answers to merge identical-sized arrays, but haven't seen the answer to this question yet. Given $A_1, A_2, ..., A_k$ sorted arrays where $|A_i| = 2^i$, what is the most efficient way ...
3
votes
1answer
26 views

swapping between sorting algorithms for small input size left over

Is it suggested to swap between sorting algorithms? Merge sort certainly performs better on large input size however Insertion sort performs better on small input size Analysis based on there ...
3
votes
2answers
85 views

Insertion sort with pairs of numbers already in order

I am currently attempting to work out the number of comparisons that is done by insertion sort when the elements are already in sorted pairs, for example $$4,5,22,23,1,2,19,20, \dots$$ Currently ...
-3
votes
1answer
40 views

When to not use count sort? [closed]

If I have n integers, which are in range 1 to n^2, should I use count sort? My thought is that I shouldn't because it would be a risk if n happens to be substantial. I can't seem to figure out the ...
1
vote
1answer
60 views

Probability bounds on size of smaller partition in randomized quicksort

Let $0 < a < 0.5$ be some constant. We have an $n$-element array as input. Randomized quicksort chooses one element from array uniformly at random as a pivot and partitions. With probability $1-...
0
votes
1answer
32 views

Get the previous and next values of a string in lexicographic order [closed]

I'm working with a noSQL database and for certain reasons I can't use equality filtering in my queries e.g select all from database where id = 10 is NOT ...
-1
votes
2answers
41 views

merge sort merge phase

I'm watching a video, demonstrating merge sort, https://www.youtube.com/watch?v=EeQ8pwjQxTM At 5:42, happens something I do not understand. We are merging last 2 big arrays, ...
5
votes
1answer
84 views

Sort a list of points to form a non-self-intersecting polygon

Given a list (of arbitrary length) of 2-dimensional points, is there some algorithm that I can employ to sort this list of points into an order such that line segments sequentially drawn from $p_0 \...
0
votes
0answers
58 views

Analyzing a sorting algorithm [duplicate]

Each of n distinct values is equally likely to be put into pile 1 or in pile 2, independent of each other. These piles are then sorted from smallest to largest. The two sorted piles are then merged ...
0
votes
1answer
47 views

Differentiating between BubbleSort and InsertionSort

This is a homework I'm doing, but I couldn't find an answer, hopefully you guys can shine some light on this. The problem is this: You have two unknown sorting algorithms, one is Bubble Sort, the ...
1
vote
1answer
107 views

What does < mean in this TAOCP solution?

For our assignment we have to implement a solution given to one of the problems in The Art of Computer Programming by D.E. Knuth (Ex24; Chapter 5: Sorting; TAOCP, Vol3, 2nd). However, I fail to ...
-1
votes
1answer
74 views

How do I analyze Mergesort that uses Insertion Sort for small inputs?

I know that Insertion Sort is faster when size $N$ is a small number, hence by modifying Merge Sort to use Insertion Sort when size $N$ reaches $K$, can help improve the performance. How do I ...
0
votes
1answer
20 views

In terms of the multiplicative constant, what comparison algorithm is fastest in average complexity? [closed]

It is well-known that there is an asymptotic lower bound of $nlogn$ for comparison sorting. However, I am wondering what is the fastest known algorithm for comparison sorting, in terms of the ...