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

learn more… | top users | synonyms

1
vote
2answers
81 views

Sort deck of cards with least no of moves

We have n cards with each card numbered from 1 to n. All cards are randomly shuffled but all cards are visible We are allowed only operation MoveCard(n) which moves the card with value n to the top ...
0
votes
0answers
11 views

how to calculate the average case efficiency of the improved bubble sort? [duplicate]

I already know that the average case efficiency for this algorithm is: $\Theta(n^2)$. But I want to know how to obtain this result. This is the algorithm that I have: ...
1
vote
1answer
72 views

Sorting an already k-sorted array

Can anybody give me some hint on how to do this? I'm not really sure where to start. The problem says: We say that an array $A[1...n]$ is $k$-sorted if it can be divided into $k$ blocks, each of ...
0
votes
0answers
37 views

Find the index of minimum number that is greater than key given of a sorted array, does these two functions return same result?

Give an array of integer has been sorted (non-decreasing order), we need find the index of minimum number number that is greater than key given, I wrote two functions, they're identical except the ...
3
votes
3answers
1k views

Why does this sort algorithm work?

The following O(n^2) sorting algorithm works but I can't figure out why. ...
1
vote
1answer
22 views

number of comparison in sort algorith with special operation

Let's define: $ a_i:a_j \Longleftrightarrow a_i < a_j;\ a_i=a_j;\ a_i > a_j $ So it is similiar to normal operation $<$, but $:$ give information when elements are equal. I want show that ...
1
vote
0answers
34 views

Sort graph nodes by density [closed]

Imagine villages (or Internet Routers) scattered all over the world (or World Wide Web) connected by roads or shipping lanes (or Cables). All villages (nodes) has the same amount of villagers which ...
1
vote
1answer
37 views

Lower bound on distinct element heapsort

I've been self-studying algorithms and am currently working on one of the starred exercises from CLRS: Exercise 6.4-5 Show that when all elements are distinct, the best-case running time of heapsort ...
6
votes
1answer
435 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
42 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 ...
5
votes
3answers
87 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
47 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
60 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
70 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
45 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
70 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 ...
12
votes
2answers
188 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
57 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
26 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
36 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
109 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
85 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
50 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
63 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
65 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
41 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
34 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
1answer
70 views

Analysis of sorting Algorithm with probably wrong comparator? [duplicate]

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
113 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
37 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 ...
0
votes
1answer
72 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
365 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
36 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
38 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
112 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
177 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
35 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
35 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
327 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
52 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
87 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
126 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
63 views

How does selection sort sort?

I've found the following algorithm for selection sort on the internet. ...
1
vote
1answer
77 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 ...