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

learn more… | top users | synonyms

1
vote
1answer
39 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 ...
-1
votes
0answers
16 views

Why do comparison-based sorting algorithms have a lower bound of Ω(n log n) for their worst-case running time? [duplicate]

I get that any comparison-based sorting algorithm has a lower bound of Ω(n log n) for its worst-case running time, but why is it so? Is there anyway I can prove it?
-2
votes
3answers
64 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
124 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 ...
-2
votes
0answers
40 views

Sorting aray of $-1$, $0$, $1$ in $O(n)$ time [duplicate]

I'm trying to come up with an algorithm to sort an array where each element is a $-1$, $0$, or $1$ in $O(n)$ time, where $n$ is the length of the list. Here is my solution (written in Python): ...
1
vote
1answer
50 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
44 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
424 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
votes
0answers
36 views

Parallel CREW algoritm for sorting n numbers between 0 and logn-1

We are given n integers in the range [0,..,log(n)-1]. How can we sort the numbers? The algorithm doesn't have to be work-efficient.
1
vote
2answers
30 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
33 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?
1
vote
2answers
43 views

Proving the lower bound of compares in comparison based sorting

I'm reading Sedgewick and Wayne's book of Algorithm. When I read the following proof in the attached picture, I don't understand why it assumed the comparison number is lg(number of leaves). Any help ...
1
vote
1answer
57 views

How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3?

How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3? (where n is a power of 3) I was told it takes: $$2(n-2) + 1 = 2n-3$$ However, I can't seem to figure out ...
3
votes
3answers
490 views

Rigorous Proof of Insertion Sort

Currently I self study CLRS book (Outside of any course, so I got no access to an instructor) And I am stuck proving Insertion Sort, The proof in CLRS book is not so formal. Here's the algorithm: ...
1
vote
1answer
32 views

Sorting with a recursive oracle

It is known that the runtime complexity of sorting is $\Theta (n \log n)$. But what if we have, for every input array of size $n$, an oracle that can sort any array of $k<n$ numbers in constant ...
2
votes
2answers
45 views

About sorting numbers in linear time

If one is given $n$ numbers picked uniformly at random from the interval $[0,1]$ then is it possible to sort them in linear time? It seems to me that some such method exists which uses binary ...
4
votes
1answer
20 views

How to order objects to minimize non-adjacency cost

I have an array of $N$ objects, each appearing exactly once. I also have a list of $M$ pairs of the objects. Each pair has a "non-adjacency cost" that must be paid if the two objects are not adjacent ...
1
vote
1answer
73 views

What is the runtime of Mergesort if we switch to Insertion Sort at logarithmic depth?

Consider the Mergesort algorithm on inputs of size $n = 2^k$. Normally, this algorithm would have a recursion depth of $k$. Suppose that we modify the algorithm so that after $k/2$ levels of ...
0
votes
1answer
65 views

Permutations in an k-sorted array

Definition of $k$-sorted array: An array in which an element is at-most $k$ places away from its sorted order. I have a question in my Algorithms assignment which asks to prove the lower bound to ...
0
votes
1answer
65 views

Showing that tournament sort requrires O(n log n) comparisons

I wish I could think of a better way to word my question. Maybe some one here could offer s suggestion for that, as well. On to my question. Before I do, this is a class question that has been asked, ...
2
votes
1answer
67 views

Top N percent elements in a queue

I implemented a queue using two stacks which gives me $O(1)$ en-queue time, $O(1)$ amortised time. Now suppose I want to find top $10\%$ elements in the queue at any time. How am I suppose to ...
-4
votes
2answers
101 views

Sort doubly linked list efficiently

How efficiently can a doubly linked list be sorted? The minimum I could get is $O(n^2)$. Can anyone suggest something better?
11
votes
2answers
309 views

Algorithm to distribute items “evenly”

I'm searching for an algorithm to distribute values from a list so that the resulting list is as "balanced" or "evenly distributed" as possible (in quotes because I'm not sure these are the best ways ...
1
vote
1answer
93 views

What is the min # of moves to sort an array from 1 to n?

Problem: You are required to sort an array with numbers from 1 to n. You can do a "move", which means choosing one element and moving it to any place you want (insert to any place, not swap). Prove ...
0
votes
0answers
23 views

Programming and evaluating sorting algorithms based on its complexity [duplicate]

I need to program and evaluate two sorting algorithms: insertion sort and merge sort I know that the complexity of insertion sort is O(n^2) and for the merge sort is O(n·log n) In this case I have a ...
1
vote
2answers
48 views

Why comparison is dominant time consumption for comparison-based sorting algorithms? [duplicate]

Comparison-based sorting algorithms does a number of different operations to accomplish the sorting, why comparisons are the dominant time consumption? While I understand the standard analyses of ...
3
votes
0answers
99 views

Sorting with gaps

Suppose we have a directory containing $N$ files whose names are numerals, but not necessarily contiguous numerals. Let's say for concreteness that each file contains an email message, each of which ...
-2
votes
1answer
110 views

Sorting when there are only O(log n) many different numbers

We have $n$ integers with lot's of repeated numbers. In this list, the number of distinct elements is $O(\log n)$. What's the best asymptotic number of comparisons for sorting this list? Any idea or ...
-2
votes
1answer
53 views

LSD and MSD sorting - which requires fixed length keys?

I am studying these sorts, but it is still unclear to me which one of these two would require fixed length keys?
-1
votes
4answers
321 views

Proving Quicksort has a worst case of O(n²)

I am sorting the following list of numbers which is in descending order. I am using QuickSort to sort and it is known that the worst case running time of QuickSort is $O(n^2)$ ...
0
votes
1answer
214 views

Can I use breadth-forst search for topological sorting?

Can I use Breadth first Search for finding topological sorting of vertices and strongly connected components in a graph? If yes how can I do that? and If not why not? I tried with a simple acyclic ...
0
votes
1answer
37 views

How to write all $r$-tuples with a certain property in a list [closed]

I have the following question: Let $a,b,c,d$ be four natural numbers with $a \leq b$ and $c\leq d$. I have written a program that produces a list, which has as entries all 2-tuples $(x,y)$ with ...
2
votes
2answers
52 views

Algorithm to partially sort list into equal-sized buckets

Suppose I have a large list of numbers that I want to divide into equal-sized buckets so that every bucket contains only larger numbers than buckets to its left. Numbers within each bucket don't need ...
3
votes
1answer
141 views

How to sort using $\texttt{SQRTSORT}$ as a subroutine which sorts $\sqrt{n}$ of consecutive elements?

I am teaching myself algorithms with the online lecture notes by Jeff Erickson and fails to solve the following problem (Problem 21 of Lecture 1). (a) Describe an algorithm that sorts an input ...
-3
votes
1answer
87 views

Min-max selection sort

Is there already modified version of selection sort that works like this pseudocode: ...
2
votes
0answers
71 views

Complexity of Sorting Integers on a Multitape Turing Machine

How expensive is sorting integers on a Multitape Turing Machine? The usual algorithms rely on indirect access, so how much does losing it cost us? Say we have $N$ integers from $[0, 2^B)$. It's not ...
1
vote
1answer
47 views

Runtime analysis of sorting an array with known number of inversions

I'm having difficulties with analyzing the worst-case runtime of this following case: I'm given an array that has $n$ natural numbers. Out of all $\binom{n}{2} = \frac{n(n-1)}{2}$ possible pairs ...
3
votes
1answer
64 views

Computing the complement of a set

Suppose I have a set $A$ of elements in $\{1, \ldots, n\}$, given as an unordered list. I would like to compute the complement of $A$, i.e., I would like to produce an unordered list of entries in ...
-2
votes
1answer
97 views

How do you return the k smallest elements of an array using Mergesort?

I'd like to create a modified mergesort algorithm to return the k smallest elements of an array. The mergesort algorithm below sorts an unordered array of size n. How do I modify the algorithm so that ...
5
votes
1answer
88 views

Difference in Sorting 32- and 64-bit Integers

In 2007, Barrack Obama was interviewed at Google. The question was, "What is the best way to sort a million 32-bit integers?" Does the fact that the size range of the integer was specified elude to a ...
6
votes
3answers
754 views

Word Frequency with Ordering in O(n) Complexity

During an interview for a Java developer position, I was asked the following: Write a function that takes two params: a String representing a text document and an integer providing the ...
2
votes
0answers
84 views

What is the average-case running time of Fun-sort?

I read this paper: http://www.sciencedirect.com/science/article/pii/S0166218X04001131?np=y (you can check the PDF online for free), and I translated section 4's Fun-sort algorithm (correct me if I'm ...
2
votes
1answer
95 views

Sorting numbers in $O(1)$

Here is an experiment I came up with (I don't have sufficient material to make it): Say that, you have a list of $n$ numbers $L = \{l_1, l_2, ..., l_n\}$. And you have bars representing those numbers ...
2
votes
1answer
69 views

is there a sorting algorithm of order $\log n!$

Is there any sorting algorithm that takes order of $\log n!$ in the worst case? I know that this is the lower bound for sorting algorithms using comparison based sorting. I know that there are ...
-2
votes
2answers
201 views

Quicksort implementation unclear

This code is taken from wikipedia: ...
3
votes
2answers
255 views

Why does introsort use heapsort rather than mergesort?

As part of a homework assignment covering implementation of introsort I'm asked why heapsort is used rather than mergesort (or other $O(n\log(n))$ algorithms for that matter). Introsort is a ...
5
votes
1answer
39 views

Linearithmic lower bound for 1-D “distinct” closest pair of points problem

The 1-D distinct closest pair of points problem is as follows: Given a set of n distinct integer points on real line, find a pair of points with the smallest distance between them, here the distance ...
1
vote
1answer
117 views

Dual-pivot Quicksort reference implementation?

Has some sort of canonical - or reference - implementation of Dual-pivot Quicksort been posted anywhere? I would like to include that algorithm in a comparison among sorting algorithms for a ...
0
votes
2answers
71 views

Why don't we calculate swaps and other steps except comparison for finding time complexity of a sorting algorithm? [duplicate]

I was learning some basic sorting techniques with their complexity. However I cannot understand why only the number of comparisons are taken into account while calculating time complexity and ...
1
vote
2answers
557 views

Find the minimum amount of swaps to sort array

When getting source array length, I want to generate the array of swaps that need to be performed in order to sort the source array. I want to make this array as small as possible. Swaps will be ...