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

learn more… | top users | synonyms

2
votes
1answer
14 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
38 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
54 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
36 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
32 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
395 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
17 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
41 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
44 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
33 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 ...
0
votes
2answers
324 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
18 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
64 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 ...
1
vote
1answer
38 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
61 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
31 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
95 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
51 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
35 views

Rank athletes by weighted criteria

I have a structure. that consist of the following: ...
0
votes
1answer
58 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
80 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
31 views

Merge k sorted arrays, each one's length is double than its' previous

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 best comparison ...
3
votes
1answer
24 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
72 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
39 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
59 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 ...
0
votes
1answer
31 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
39 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
69 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
57 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
46 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
106 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
72 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
19 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 ...
1
vote
0answers
54 views

Sort complexity in a random array

if I have an unsorted array with the length of $10^6$, which is filled with absolutely different float numbers, which sorting algorithm would be the best to use and why? And which one would be the ...
1
vote
1answer
90 views

Does Heapsort work in time o(n log n) in the best case?

Is it possible for Heapsort to work in time $o(n\log n)$ on certain inputs? For example in case of Insertion sort it is possible, however when it comes to Quickssort it is not possible. What about ...
3
votes
1answer
111 views

Merge two sorted arrays without using additional memory

We have two sorted arrays of integers. Without using additional memory we need to merge these two arrays such that the smallest numbers are in the 1st array and the remaining numbers are in the ...
-4
votes
2answers
74 views

Which sorting has a complexity of $n \log n$ if you compare two elements? [closed]

I want to ask just a quick question. If I have an array, which sorting method will have a complexity of $n \log n$ if I compare two objects in that array? I can't decide between ...
2
votes
1answer
84 views

Distribute numbers 1,N on a grid as evenly as possible

I'm working on a complex engineering problem that I've essentially reduced to this problem: I have a set of natural numbers $1,N$ and a grid (square or hexagonal) of exactly $N$ cells. I have to map ...
4
votes
1answer
46 views

Can the zero-one principle be used to prove the stability of a sorting network

When dealing with sorting networks, we can check the validity of a sorting network with only $2^n$ sequences of $0$ and $1$ (where $n$ is the size of the collection to sort) thanks to the zero-one ...
13
votes
3answers
275 views

Deterministic linear time algorithm to check if one array is a sorted version of the other

Consider the following problem: Input: two arrays $A$ and $B$ of length $n$, where $B$ is in sorted order. Query: do $A$ and $B$ contain the same items (with their multiplicity)? What is the ...
3
votes
4answers
103 views

Which sort algorithm can I use as a metaphor for this learning philosophy?

TL;DR Which sort algorithm: Works in multiple passes. Performs less and less of the total work at each subsequent pass. When visualized, makes it clear that the decreasing amount of work at each ...
3
votes
1answer
86 views

Sorting an “almost sorted” array in sub linear time

I am given an "almost sorted" array with the condition that each element is no more than k places away from its position in the sorted array. I need to show that it is impossible to sort this array in ...
0
votes
1answer
55 views

Lower Bound for Comparison-based sorting algorithms

We know that the lower bound for comparison-based sorting algorithms is Ω(nlogn), where logn being the binary logarithm of n. But what about for the best-case scenario of the bubble sort, which takes ...
3
votes
1answer
59 views

Optimal pivot selection for quick-sort

The actual runtime of applying quick-sort to an integer array heavily relies on the choice of pivots. It is well known that picking a random pivot does not work as good as taking the median of three, ...
3
votes
1answer
59 views

Enumerate all pairs, in order of increasing distance, efficiently

Given $n$ points in 2D, e.g., $p_1,p_2,....,p_n$, there are $n^2$ possible pairs of points. I want to output the list of $n^2$ pairs, but sorted according to their distance (e.g., the pair of two ...
2
votes
1answer
45 views

Efficient haircuts

I have a real vector $v$. From this vector, I want to extract a sequence of integers, $ix$. The first integer is found by, $ix_0=argmax(v)$. 1 is then subtracted from $v_{ix_0}$, and the process is ...