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

learn more… | top users | synonyms

-3
votes
0answers
21 views

Performance difference between quick sort ending at empty subarrays and length-1 subarrays

I'm wondering how much difference an implementation to quicksort that terminates loops at length-0 subarrays has as compared to one that terminates at length-1 subarrays? Any way to quantitatively ...
-1
votes
0answers
20 views

Worst case scenario perform better than average case for Heap Sort [closed]

I am using Heapsort to sort two different list of numbers List ( random selection of numbers from 1 to 9999 ) List 2 ( descending order of numbers from 9999 to 1 Heapsort algorithm ...
0
votes
0answers
20 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
44 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
86 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
91 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
32 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
191 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
62 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
33 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
35 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 ...
2
votes
0answers
83 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
24 views

Min-max selection sort

Is there already modified version of selection sort that works like this pseudocode: ...
2
votes
0answers
31 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
32 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
59 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
48 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
76 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 ...
5
votes
3answers
202 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
77 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
82 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
63 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 ...
0
votes
2answers
180 views

Quicksort implementation unclear

This code is taken from wikipedia: ...
3
votes
2answers
188 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 ...
4
votes
1answer
32 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
71 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
59 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
240 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 ...
0
votes
1answer
56 views

A home assignment. C language [closed]

Help would be much appreciated. "Receive a number and reorder it from the largest to the smallest. Input: 13252 Output: 53221 Cant use arrays... Only while, for, if/else ... any idea? i'm ...
6
votes
2answers
1k views
2
votes
3answers
573 views

QuickSort Dijkstra 3-Way Partitioning: why the extra swapping?

Given the algorithm above (taken from the slides (p. 35) of the Coursera course “Algorithms Part I” by Robert Sedgewick and Kevin Wayne), look at the scenario where i is at "X", the following ...
2
votes
2answers
192 views

Proving the Bubblesort actually sorts

Say $A'$ is the output of $\mathrm{Bubblesort}(A)$ on an array of length $N$. To prove that Bubblesort works, we have to prove that it always terminates and that $$A'[0]\leq A'[1] \leq \dots \leq ...
5
votes
1answer
119 views

Given $k$ sorted lists, $O(n \log k)$ complexity, Mergesort rather than Heapsort

I was convinced that my idea for a solution to sort $k$ sorted lists into one list would work with a 'variation' on MergeSort. I was told this would not work and had to use Heapsort, but didn't get ...
1
vote
1answer
67 views

How can I quantify the number of swaps required for insertion sort?

Based on the Wikipedia implementation of insertion sort: Given an input array $A$: ...
2
votes
0answers
239 views

Choosing the optimal radix/number-of-buckets when sorting n-bit integers using radix sort

This is a popular question: What is the most efficient (in time complexity) way to sort 1 million 32-bit integers? Most answers seem to agree that one of the best ways would be to use radix ...
0
votes
0answers
101 views

On ranking (sorting) by a varying distance metric

I came across an interesting procedure that ranks (sorts) a set of tuples, not by comparisons between tuples, but by the proximity between next tuple(s) and the set of tuples already ranked. ...
0
votes
1answer
3k views

Selection Sort Time Complexity using Big O notation

I'm trying to understand why the sorting algorithm Selection Sort has a time complexity of O(n^2). Looking at the math, the time complexity is T(n) = (n-1) + (n-2) + ... + 2 + 1 And this is stated ...
7
votes
3answers
317 views

Is transitivity required for a sorting algorithm

Is it possible to use a sorting algorithm with a non-transitive comparison, and if yes, why is transitivity listed as a requirement for sorting comparators? Background: A sorting algorithm ...
1
vote
2answers
125 views

Minimum number of exchanges needed to get all negative values left of all positive ones

Suppose we want to arrange n numbers stored in an array such that all negative value occur before the positive ones. What will be the minimum number of exchanges in the worst case ?
1
vote
1answer
93 views

Is radix sort a greedy algorithm?

I was thinking of radix sort, and at a sudden thought that it uses de facto the paradigm of dynamic programming, but I soon changed my mind to greedy algorithm. Is it really a greedy algorithm?
0
votes
1answer
134 views

What is the complexity of this bubble sort algorithm? [duplicate]

I have been doing a little reading up on bubble sort and have read on wikipedia that it's complexity is measured as $\Theta(n^2)$ This bubble sort however is slightly more efficient. I thought this ...
2
votes
2answers
102 views

sorting stone Problem [closed]

My friend asked this problem recently & am not sure which sorting to use for this kind of problem:- There are 20 stones of different heights. Each stone is so heavy, we need to sort the stones ...
6
votes
4answers
6k views

What is a the fastest sorting algorithm for an array of integers?

I have come across many sorting algorithms during my high school studies. However, I never know which is the fastest (for a random array of integers). So my questions are: Which is the fastest ...
0
votes
1answer
693 views

Best and worse case inputs for heap sort and quick sort?

So given an input of lets say 10 strings, what way can we input these so we get the best or worst case for these two given sorts? ...
1
vote
1answer
3k views

Best and worse case inputs for heap sort and quick sort?

So given a input of lets say 10 strings, what way can we input these so we get the best or worst case for these two given sorts? ...
-1
votes
2answers
93 views

Algorithm for sorting with constraints

I've got 30 elements which has to be grouped/sorted into 10 ordered 3-tuple. There are several rules and constraints about grouping/sorting. For example: Element $A$ must not be in the same tuple ...
4
votes
2answers
134 views

More efficient algorithm for determining if one list is a sublist of another list

I'm trying to build an algorithm which takes two lists of natural numbers and finds if every element of the first list is displayed at least once in the second list. What if the list is sorted? An ...
2
votes
1answer
113 views

topological sort equivalence

For a given acyclic graph $G$, a topological sort is an ordering $v_1, \dots, v_n$ of the vertices such that the arrows in the graph are all directed forward under that ordering. Question: can all ...
3
votes
2answers
119 views

Enumerating weighted permutations in sorted order problem

Let $S$ be a set of $n$ integers. Consider the following weighted permutations problem. Let $m<n$ be an integer. What is an efficient algorithm to enumerate all subsets of $m$ integers of $S$ ...
1
vote
0answers
67 views

Quick Select explanation

I have been looking for a quick and easy explanation on Quick Select and stumbled upon this. It's quick and easy to follow, but there's a part which I am not following quite well: The uploader is ...