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

learn more… | top users | synonyms

5
votes
1answer
202 views

Least number of comparisons needed to sort (order) 5 elements

Find the least number of comparisons needed to sort (order) five elements and devise an algorithm that sorts these elements using this number of comparisons. Solution: There are 5! = 120 possible ...
1
vote
0answers
37 views

How is the problem of sorting in contiguous runs called?

I am having a bit of brain fail and I can't remeber the name of the following problem (so I can find some literature around it...). Given a sequence of values, sort it in a way that equal elements ...
0
votes
0answers
28 views

How to make quick sort recursive? [migrated]

Currently I am trying to make a recursive quick sort. There are many different methods for quick sort but for my method, I have to take the first element of the array and always use the first element ...
0
votes
0answers
31 views

Sort graph nodes by density [closed]

Cyclic connected undirected graph. Every node in a graph has T value initially zero. Suppose there is a traverse via shortest path between every two nodes which increases every node's T value it ...
0
votes
0answers
51 views

Comparison analysis - Bubble Sort vs Selection Sort

For me, watching graphs, asymptotic analysis is less intuitive than below approach to compare these two sorting algorithms. For below code, ...
5
votes
3answers
74 views

How do I tell if a comparison network sorts?

I am presented with a comparison network. How can I determine if the comparison network is a sorting network? In the image below there is an example of a selection sort and insertion sort network. The ...
0
votes
1answer
44 views

Merge two series of sorted number, one much longer than the other

This is the problem: Merge two sorted series of numbers. Their lengths are $n$ and $m$, respectively, but $n \gg m$. Your algoritm should take $O(m \log(n/m))$ comparisons. I have come up ...
0
votes
1answer
54 views

How to sort fractions (small numbers) [closed]

We have 100,000 fractions: $\frac{p}{2^q}$ such that $0 \leq p,q \leq 10$. Task is about finding a fast algorithm to sort fractions. I ask you to look at my proposition and tell me your ideas. ...
1
vote
3answers
60 views

minimum subset of dominating 2D points

From an initial set $S$ of 2D points, how to efficiently compute a minimum(-size) dominating subset $M$ ? $M$ is a dominating subset of $S$ if for any $(x,y)$ in $S$ there is at least one point (a,b) ...
0
votes
1answer
44 views

position to insert element in inserionsort (equality of probablity)

prove that in algorithm insertionsort, for successively considered element a[i] there is equal probablity that element will be inserted in one of i positions: a[1] <= a[2] <= ... <= a[i-1] ...
1
vote
1answer
69 views

Getting the sorted sequence from a level-wise sorted min-heap

A heap sorted by levels is a heap which: Every parent is smaller than its children. The nodes in each level are sorted from the smallest to the greatest. I need to describe an algorithm with ...
10
votes
0answers
134 views

Is there no sorting algorithm with all specific desired properties?

On the Sorting Algorithms website, the following claim is made: The ideal sorting algorithm would have the following properties: Stable: Equal keys aren't reordered. Operates in place, ...
2
votes
2answers
56 views

Finding a segment which has equal number of segments before and after it

I got this question in a past test that I'm trying to solve but i don't have the solutions to check my self: Given a set of n segments $[a_i ,b_i]$ where $i=1,..,n$ and $a_i < b_i$. write an ...
1
vote
1answer
23 views

Extra space of MergeSort [duplicate]

Here is my implementation of mergeSort. I need n extra space for the helper array. But what about recursive calls? I call sort ...
2
votes
1answer
34 views

Radix sort and changing bases

I have recently learned about radix sort. I am aware that you can change the base of the numbers you need to sort but I don't really understand why this is good for the radix sort. Radix sort runtime ...
-1
votes
1answer
32 views

Printing the array elements sorted by repetition [closed]

I just can't figure this question out: Given an array of N elements, its values range are from 0 to 100. Write a function that prints the array's elements sorted by repetition. Time complexity : ...
1
vote
2answers
106 views

Why can't hash tables provide O(n) sorting?

Since a sufficiently large hash table takes constant time to both insert and retrieve data, should it not be possible to sort an array by simply inserting each element into the hash table, and then ...
4
votes
2answers
77 views

Algorithm to find sequence of minimum moves to sort 13 card hand

Just for fun I am trying to write a program to sort the 13 cards (from a standard pack of 52) in a Bridge hand by performing human-like moves on the hand. A sorted bridge hand is arranged by suit, ...
0
votes
1answer
40 views

d-ary heapsort analysis

I need to find a tight bound on the number of comparisons in a d-ary heapsort, in terms of d and n (the length of the array we ...
3
votes
0answers
61 views

Find a sorting procedure for seven elements that minimises the average number of comparisons performed

In The Art Of Computer Programming, Volume 3, Chapter 5.3.1, Problem 26, Knuth asks one to construct a sorting method that achieves the minimum number of average comparisons for n=7. This means that ...
3
votes
1answer
61 views

In-place “clumping-by-color” algorithm faster than sorting by color?

I don't know what to call this, so I'm calling it "clumping by color". Suppose I have an array of length $n$ where each of the items has one of $m$ "colors". I'd like to permute the elements so that ...
-2
votes
1answer
34 views

It is possible to implement insertion sort for sorting linked list ?

it is possible to implement insertion sort for sorting linked lists ? will it have the same O(n^2) efficiency as the array version ?
1
vote
1answer
39 views

Are there any theorems/formulas that apply to the height of comparison trees?

I have been drawing some binary comparison trees, which correspond to compares made to sort an array, and I was wondering if there is any formula to determine the height of a comparison tree for an ...
0
votes
1answer
45 views

Compare vs Radix

Is it better to use comparison or radix sort to sort a long sequences of java int array? I know that I should probably use mergesort (NlogN) for comparison sort, since it is one of the fastest and ...
3
votes
0answers
32 views

Is there a known worst start configuration for Ford-Johnson sorting algorithm?

By this I mean a permutation of the $n$ input items to be sorted such that the number of comparisons taken to produce the correct order is maximal over all of the possible permutations of $n$ items. ...
3
votes
0answers
55 views

Analysis of sorting Algorithm with probably wrong comparator?

It is an interesting question from an Interview, I failed it. An array has $n$ different elements $[A_1, A_2, \ldots, A_n]$ (random order). We have a comparator $C$, but it has a probability p to ...
1
vote
1answer
53 views

Variation on Insertion Sort

I'm writing insertion sort in scheme, but due to the difficulty of writing it recursively within the constraints of list processing of scheme, I made what seems like an insignificant change to the ...
3
votes
1answer
98 views

What is the worst case running time for an algorithm that combines insertionsort and mergesort?

Suppose that we have an algorithm "combination" that uses insertionsort for $n < 100$ and mergesort for $n \geq 100$. Is the worst case running time of "combination" then $n^2$ or $n\log n$? I was ...
4
votes
1answer
33 views

n closest points in a set of lat/long coordinates

Here's my problem: I have a website where people can search based on their location (which is converted to lat/long coordinates). I have many products stored in a database with their lat/long ...
1
vote
1answer
59 views

What sorting algorithm should be used for this array?

I am given an array {1, 2, 3, 5, 4, 6} and I am asked What sorting algorithm might you want to use to sort the given list, and why? Initially I think using ...
0
votes
0answers
276 views

Best- and worst case for Mergesort using Bubblesort for small lists

Problem statement: Merge sort is so modified that for array sizes below 11, instead of recursive Merge sort, the array is sorted using Bubble sort. Will there be any good and bad cases now? Give ...
0
votes
0answers
33 views

Dijkstra's Quicksort Algorithm

How does Dijkstra's Quicksort Algorithm perform better than the original Quicksort Algorithm in terms of memory usage,number of exchanges made and time taken? original quicksort refers to Tony ...
3
votes
0answers
64 views

Is integer sorting possible in O(n)?

To my knowledge there doesn't exist a $O(n)$ worst-case algorithm that solves the following problem: Given a sequence of length $n$ consisting of finite integers, find the permutation where every ...
4
votes
1answer
35 views

Average case lower bound for sorting

The $\Omega(n\lg{n})$ lower bound for sorting in the comparison model is well known. Is there a similar average case lower bound for sorting in the comparison model and if so, which random ...
4
votes
3answers
82 views

Why does this mergesort variant not do Θ(n) comparisons on average?

A comparison sort cannot require fewer than $\Theta (n\log n)$ comparisons on average. However, consider this sorting algorithm: ...
0
votes
1answer
108 views

Sort Algorithm running in O(n)

An array A holds n integers, and all integers in A belong to the set {0,1,2}. Describe an O(n) sorting algorithm for putting A in sorted order. Your algorithm may not make use of auxiliary storage ...
0
votes
1answer
147 views

Why is Comb-sort (aka Dobosiewicz-sort) faster than Cocktail-sort (aka shake-sort)?

According to wikipedia, Cocktail-sort has an average performance of $O(n^2)$, whereas Comb-sort's average performance is $Ω(n^2/2^p)$, where $p$ is the number of increments. There's no explanation ...
1
vote
0answers
34 views

Median-of-medians for sorting finger trees incrementally

Haskell's Data.Sequence uses Hinze-Paterson 2-3 finger trees to represent finite sequences. The types are defined below for concreteness. Currently, the library ...
0
votes
1answer
34 views

Do comparison sorts have to start at the beginning of the input?

Say I had an input $\langle3,17,15,9,1\rangle$, could I for example begin by comparing 1 with 3 so that 1 appeared at the start of the sorted sequence straight away or would I first have to compare 3 ...
1
vote
1answer
294 views

I can not see why MSD radix sort is theoretically as efficient as LSD radix sort

Here is the pseudocode for LSD radix sort from http://www.cs.princeton.edu/~rs/AlgsDS07/18RadixSort.pdf ...
0
votes
0answers
48 views

Analyzing the time and space requirements of a Most Significant Digit first radix sort algorithm

In a previous question of mine, I asked how efficient is the Least Significant Digit first radix sort algorithm for sorting 32-bit integers. It turns out that the bounds are: Time: $ \Theta ...
-2
votes
1answer
81 views

Shortest possible comparison sequence to determine order of elements

Supposed you have $\langle a_1,a_2,a_3,a_4,a_5\rangle$ = $\langle 6,16,13,9,6\rangle$, how would you find a shortest possible sequence of comparisons that determines the order of elements?
3
votes
2answers
120 views

Why does quicksort work well with virtual memory?

Introduction to Algorithms said that quicksort "works well even in virtual-memory environments," but didn't explain why. I've tried looking an Wikipedia and Stack Exchange, but found no reason why. Is ...
0
votes
1answer
61 views

How does selection sort sort?

I've found the following algorithm for selection sort on the internet. ...
1
vote
1answer
64 views

Expected number of random interval flips needed for sorting a random array

This question is inspired by the Bogo-Sort algorithm and the discussion of whether there are any worse sorting algorithms than Bogosort. Assume that $A$ is an array initialized by a random ...
-1
votes
1answer
100 views

Sorting tuples with respect to multiple criteria

Given $n$ rows with $k$ columns, is there a storage mechanism/data-structure and/or algorithm that enables dynamic restructuring such that I can get the top $t=\mathcal{O}(1)$ results efficiently? ...
2
votes
1answer
50 views

What type is this sorting algorithm?

I needed to sort vertices into buckets as an optimization for collision detection later. I came up with this: go over all the verts and count the size that each bucket needs to be to contain them ...
0
votes
0answers
106 views

Count comparisons in insertion sort that uses binary search to find correct postion

Assume a list $L$ is to be sorted using the following variation of insertion sort: For $2 \le i \le n$, to insert key $L[i]$ do a binary search on the list $L[1..i-1]$ to find the correct position. ...
2
votes
1answer
55 views

Generalisation of pancake sorting with arbitrary flipped slices?

In pancake sort, the primary operation is: flip all pancakes above a given position. What about flipping all pancakes between two given positions? Anybody knows if this has been studied? To ...
4
votes
3answers
923 views

Why is the optimal cut-off for switching from Quicksort to Insertion sort machine dependent?

I fail to understand why cut off value would be system dependent, and not a constant. From Princeton University website Cutoff to insertion sort. As with mergesort, it pays to switch to ...