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

learn more… | top users | synonyms

2
votes
1answer
36 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
26 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
36 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, ...
-2
votes
1answer
51 views

How to design a recursive sorting given Kselect [closed]

The problem is as follows: Let A(1,...,n) be an array of distinct unsorted integers, where n is a power of 2. Your are given a linear time KSelect algorithm that you can use as a subroutine. Show how ...
5
votes
1answer
52 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
56 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
40 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
votes
0answers
12 views

Prove that double bubble sort is a Big-Theta(n^2) algorithm [duplicate]

Double bubble sort=every other run through the elements bubbles the smallest element down to the front of the list. How do I prove that it is theta n^2? Edit: other runs bubble largest elements up ...
1
vote
1answer
104 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 ...
-2
votes
0answers
23 views

Can anyone explain the Turbo Sort algorithm?

I have been trying to solve a certain coding challenge where its been asked asked to sort an array of numbers. But it gives a 'timed-out' error on submission even when I use Quick Sort technique, ...
-1
votes
1answer
64 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
52 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
79 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
78 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 ...
-5
votes
2answers
65 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
80 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
31 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 ...
12
votes
3answers
256 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
86 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
66 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
44 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
49 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
56 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
44 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 ...
1
vote
1answer
19 views

Finding a lower bound for the amount of comparisons for sorting $k$ subarrays with $\frac n k$ elements

Let the input be an array of $n$ elements, with $k$ sets $S_1,...,S_k$ such that each set has $\frac n k$ elements. The elements in each $S_i$ are larger than the elements in $S_{i-1}$. ...
5
votes
0answers
45 views

Is there any recent study about percentage that computer spend on sorting?

I came across this on Art of Computer Programming long time ago Computer manufacturers of the 1960s estimated that more than 25 percent of the running time on their computers was spent on ...
3
votes
2answers
74 views

Modified counting sort algorithm?

So I have an array $A$, already sorted with CountingSort. Now I reduce one randomly chosen element $j$ with $A[j]>0$ by $x \in \{1 \dots A[j]\}$. I still have the counting array $C$, since I have ...
0
votes
1answer
56 views

Don't understand the merge part of the mergesort

I understand how the divide part of the algorithm works and how it is meant to spread efforts. What I don't understand is how would you merge blocks [7][14] and ...
0
votes
0answers
27 views

3D Column Sort (Leighton) Algorithm

Suppose you have a matrix A (9x3) of Real numbers and want to sort in columnwise. In this case we can use Leighton ColumnSort algorithms to achieve this. But question is, how can I sort 3 dimensional ...
1
vote
1answer
37 views

$2$-sorted array. How to sort it in minimal number of comparisons ?

It is given array $2$-sorted array $a[1..n]$. $2$-sorted denotes that $a[1]\le a[3]\le...\le$ and $a[2]\le a[4]\le ..\le$ Obviously we may split array into two sorted arrays and then merge two ...
2
votes
1answer
46 views

How to understand the storing mechanism used in external merge sort

I was reading about external merge sort from the wikipedia article link, according to it: External sorting is required when the data being sorted do not fit ...
1
vote
1answer
50 views

Sorting array containing elements from $\{1,\ldots,k\}$ in place in $O(n\log k)$

An array $a[1,\ldots,n] \subseteq \{1,\ldots, k\}$ is given, where $k < \sqrt{n}$. Our goal is a project algorithm which sorts it in place and in time $O(n\log k)$. We assume that $k < \sqrt{n}$ ...
1
vote
1answer
28 views

Which pass do you look at for Radix Sort stability?

I know this is a fairly poorly worded question, but I can't think of a better way to phrase it in the title. So in Radix Sort, you go digit by digit from least significant to most significant, and ...
3
votes
1answer
52 views

Constant Shaving on known algorithms

Some problems such as sorting have famous complexity lower bounds (ex: $O(n \log (n))$ in this case) but I feel that doesn't totally remove the possibility of improving algorithms by shaving ...
1
vote
1answer
55 views

Sorting array with two elements - in place and minimal number of comparisons, lower bound

Algorithm must be in place. I would like to find lower bound for comparison algorithm. Algorithm will sort array with only two elements - without loss of generality let assume that there are only $1s$ ...
1
vote
0answers
22 views

Sorting Algorithm Existence [closed]

I have written an algorithm for sorting that I thought of, and I'm not sure if it exists. Basically, it runs through each index of an array and if the value of index n > the value of the index n+1, ...
2
votes
1answer
76 views

Quick Sort: Randomized Pivot vs Median of 3/'Ninther' Pivot vs Uniform Shuffle of Input

Is the jury still out on this or do we now know which of the above mentioned ways of randomizing Quick Sort is the most optimum as far as average case running time (averaged over all possible input ...
0
votes
3answers
110 views

How do I sort these elements in O(n) time?

So let's say I have an array of elements where each of the values can range from 0 to $n^2-1$. I'm trying to make an algorithm to sort this array in O(n) running time and I was thinking of using radix ...
6
votes
1answer
101 views

Sorting an unordered pile of items into drawers with minimal drawer movements

A while ago, I was doing my laundry late at night. When I brought my laundry back to my dorm, I started to put it away. My wardrobe is set up as follows: My drawers are categorized by the type of ...
-2
votes
1answer
77 views

Why do we use Insertion Sort in the Bucket Sort?

Bucket sort is a linear-time sort. Why do we use insertion sort in it? We know that insertion sort takes $O(n^2)$ time. Why can we not use any linear sort inside it? As we see, when in each bucket ...
2
votes
1answer
72 views

Find Minimum number of paltforms

the questions is as follows with the answer: Q) Given the arrival and departure time of various trains in a station. Calculate the minimum number of platforms required such that no train has to wait ...
1
vote
0answers
35 views

Minimum exchanges for heap sort

I'm studying heap sort and was presented with the following question. What is the minimum number of items that must be exchanged during a remove the maximum operation in a heap of size N? Give a ...
-1
votes
2answers
109 views

Sorting an array of boolean values

im looking for some guidance on how to get started with sorting an array of booleans so that the falses would be in front of the trues. so if given this: a = {true, true, false, true, false} it ...
1
vote
0answers
34 views

Efficiently comparing total values of two unsorted arrays [closed]

The general form of my question would be, what is the most efficient way to compare the total values of two different arrays to see which one is greater? Would be as simple as prefix sum ($O(n)$) for ...
3
votes
1answer
58 views

If we sort a table column-wise and then row-wise why the table is still sorted column-wise?

Say we have a $n \times n$ table which elements are sorted column-wise, for example: $$ \left( \begin{array}{ccc} 2 & 4 & 1 \\ 3 & 5 & 6 \\ 7 & 9 & 8 \end{array} \right) $$ ...
1
vote
0answers
47 views

Algorithm to find min pos difference between two integers in an array

The question I'm faced with: Let $A[1], A[2], ...,A[n]$ be an array containing $n$ very large positive integers. Describe an efficient algorithm to find the minimum positive difference ...
2
votes
1answer
29 views

Root Color of a Black Red Tree

It is required that, in a black red tree, the color for the root is always black. However, wikipedia argues that this rule can be omitted as a red root can always be changed to black but not vice ...
3
votes
1answer
55 views

Minimal number of comparisons - sorting $6$ elements

I've been thinking about sorting $6$ elements with the minimal possible number of comparisons. I can do it in $10$ comparisons but I've no idea if this is optimal. Or is there a better algorithm ? ...
-1
votes
1answer
74 views

Worst case time complexity , please check whether my solution is correct? [closed]

A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is __________. Options are $:$ ...