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

learn more… | top users | synonyms

2
votes
1answer
29 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
29 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
95 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
70 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
22 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
57 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
60 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
23 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
38 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
40 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
31 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
51 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
52 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
79 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
27 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
58 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
189 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
31 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
61 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
80 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
104 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
131 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
33 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
33 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
277 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
47 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
75 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
115 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
56 views

How does selection sort sort?

I've found the following algorithm for selection sort on the internet. ...
1
vote
1answer
54 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
88 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
81 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
54 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
898 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 ...
2
votes
1answer
49 views

Best sort approach for small data sets

I am working with small data sets of N elements, usually with N = 8, 16, or 32 elements; all are positive 64-bit float numbers. I need to identify the smallest N/2 elements. It is not required that ...
1
vote
2answers
2k views

Why does randomized Quicksort have O(n log n) worst-case runtime cost?

Randomized Quick Sort is an extension of Quick Sort in which pivot element is chosen randomly. What can be the worst case time complexity of this algo. According to me it should be $O(n^2)$. Worst ...
1
vote
1answer
75 views

Keep k+ties largest elements in a stream

I have $n$ numbers that come one by one, and when the last element comes, I want to output $k$ largest elements and those that are ties with the minimal element from this top-$k$ element. For ...
3
votes
3answers
64 views

Algorithm for generating sorting instructions

Let's say I am to sort a bookcase given a certain sorting condition, for instance alphabetically. I am looking for a way to generate a step-by-step guide on how to do this sorting based on the ...
3
votes
1answer
101 views

Heapsort for sorted input

What is the running time of heapsort when the input array is in increasing order? How about decreasing order? (I came across these questions in CLRS.) Here is what I have done so far ... For the ...
3
votes
1answer
47 views

Minimal complexity for pairing two comparable sets with comparability restrictions

A project at university (whose deadline has passed by now) presented the following problem: Consider two finite sequences of (not necessarily distinct) real numbers $a_1,\ldots,a_n$ and ...
1
vote
1answer
240 views

Can anybody explain intuitively why quick sort need log(n) extra space and mergesort need n?

I've searched on internet and everybody said it's stack space needed on recursion. I know log(n) extra space for quick sort happened when use in place, but still I don't get it. Anybody can explain ...
-2
votes
3answers
88 views

Does there exist $O(n)$ worst case sorting algorithm for sorting a list of integers?

When I looked on wikipedia, all the sorting algorithms listed have worst case $O(n^2)$. My question is suppose we are given a list of integers, each of which is in some fixed, finite set (i.e. $\{-1, ...
4
votes
4answers
170 views

How again do certain sorting methods use $o(n \log n)$ time?

I hope this question isn't too 'soft' for here. It's been a while $\tiny{\text{an eternity for some people's standards}}$ since I've touched this stuff, and I had a convincing explanation to this ...
1
vote
1answer
78 views

Questions on Topological Sorting

Currently learning about topological sorting. My teacher gave us this problem. The answer given to us is : B,A,C,E,D,G,F,H in lexicographical order. Why does the order go from B,A,C THEN go to E ...
1
vote
0answers
66 views

Sorting array with constant memory

Given an array of length $n$ we need at least $O(\log n)$ memory to store its length. And we need the same $O(\log n)$ memory to store index. With large $n$, index may not fit in one extra cell. So ...
5
votes
1answer
573 views

Would using the mean as pivot speed up quicksort?

Somehow I thought about quicksort last night and was reading about it on Wikipedia. The interesting part for me was: 'If we could consistently choose a pivot from the middle 50 percent, we would only ...
1
vote
2answers
35 views

Sorting a sorted array after increasing several elements

I know that most of the efficient sort algorithms can run with a complexity of $O(n\cdot log(n))$, but this is given an unsorted array. However, given that the initial array is already sorted, is ...
-1
votes
1answer
46 views

Bubblesort generalization [closed]

I was comparing and analyzing the sort algorithms thereby came across a machine which took 200 secs to sort 200 names but to generalize, in 800 secs wouldn't it sort 800 names?