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

learn more… | top users | synonyms

0
votes
2answers
42 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
75 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
52 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 ...
0
votes
1answer
61 views

Why is there a 2n+1 comparison for a linear search algorithm?

Suppose an algorithm goes through a list of n integers and for every iteration of the loop it is needs to check if the current evaluated element of the list is even. If it is even, return the index of ...
6
votes
2answers
862 views
2
votes
3answers
204 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
163 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
89 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
48 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
100 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
93 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
872 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
226 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
92 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
70 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
81 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
85 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
2k 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
380 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
2k 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
79 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
118 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
102 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
82 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
58 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 ...
3
votes
1answer
178 views

Maximum number of inversions that can be removed by swapping two elements?

I have come across a question that is a bit hard to understand due to its wording, I may havecome up with a possible solution, but I don't know if it's correct. Can you please help me? Thanks in ...
1
vote
2answers
145 views

Sorting in O(n) time in a finite domain

I've been stuck with this problem for 2 weeks. Any idea of how to aproach it?. Let $L$ be a list of $n$ different integer numbers, assume that the elements of $L$ are in the range $[1,750]$. ...
1
vote
2answers
111 views

How to purge a linked list in $\mathcal{O}(n\log n)$ time?

I was wondering how to remove duplicate values from a linked list in $\mathcal{O}(n\lg n)$ time. I have an idea that by using merge sort when we want to compare elements for choosing the small one, if ...
4
votes
1answer
135 views

sock matching algorithm

There are $n$ pairs of socks, all different. They all went out of the dryer, so there are now $2n$ socks scattered around. Given two socks, the only operation I can do is to decide whether they are ...
1
vote
0answers
45 views

Finding a polygonal arc algorithm? [closed]

In class we saw the followin problem but i didnt undestand the solution. Do anybody could explain me with more detail the procedure to solve this problem or give me a better solution?: Assume that ...
4
votes
2answers
142 views

How does Grover's Quantum Sorting avoid reading the list?

It is well known now that Grover's quantum algorithm can SORT a database of $N$ entries in $O(\sqrt{N})$ time. How can an algorithm work without reading through the list of entries which needs $O(N)$ ...
2
votes
1answer
216 views

Which of the common sorting algorithms can be parallelized? [closed]

I want to know that whether which of the following algorithm can be parallelized? Bubble Sort, Insertion Sort, Selection Sort, Shell Sort, Quick Sort, Merge Sort, Radix Sort. Those which can't be, ...
4
votes
1answer
132 views

Do different variants of Mergesort have different runtime?

One of my courses introduced the following question: Given the recurrence relation for mergesort: $T(n) = 2T(n/2) + n$ How would the following parameter passing strategies influence the ...
3
votes
2answers
109 views

Probability that a uniformly random sequence is already sorted

Now I tried tackling this question from different perspectives (and already asked a couple of questions here and there), but perhaps only now can I formulate it well and ask you (since I have no good ...
2
votes
1answer
55 views

Sort algorithm input probabilities

Suppose that there is an algorithm which sorts a sequence of $n$ elements $$a_1, a_2, ..., a_n$$ Each of the $a_i$ is chosen with probability $1/k$ from a set of $k$ distinct integer numbers. Is ...
4
votes
2answers
554 views

Rearrange an array using swap with 0

This is a Google interview question. I got it from a website. You have two arrays source and target, containing two permutations of the numbers [0..n-1]. You ...
2
votes
3answers
620 views

What is the most power/energy efficient sorting algorithm?

I am writing a Android phone application that needs to be very power efficient, and I would like to use the most power efficient sorting algorithm. I will implement it in C for extra power efficiency. ...
3
votes
2answers
217 views

How should I store and sort a large number of 64-bit integers?

I have about 500,000,000 64-bit integers, so these numbers could be very large. I want to sort them as quickly as possible. I have a couple of questions: What data structure do you suggest for ...
1
vote
1answer
2k views

Recurrence for recursive insertion sort

I tried this problem from CLRS (Page 39, 2.3-4) We can express insertion sort as a recursive procedure as follows. In order to sort A[1... n], we recursively ...
0
votes
3answers
850 views

Iterative and/or tail-recursive implementations of merge sort?

I recently learned how to implement merge-sort, using a standard recursive algorithm. Can the algorithm be implemented in a way that allows for a tail-recursive implementation? Can it be implemented ...
7
votes
3answers
5k views

Why is selection sort faster than bubble sort?

It is written on Wikipedia that "... selection sort almost always outperforms bubble sort and gnome sort." Can anybody please explain to me why is selection sort considered faster than bubble sort ...
0
votes
1answer
235 views

Which are the most effective sorting algorithms for a large dataset?

A bit of background, the work that I currently and will be doing involves sorting very large amounts of data (in this case, grayscale pixels in descending order), sometimes up to 4 million. Which ...
4
votes
2answers
102 views

Longest subsequence such that A[i].x < A[i+1].y

I have an issue for which I am looking for an algorithm (if it exists) What I have: An array of items which have certain properties, e.g. item $A$ has properties $x$ and $y$. Example: $[ A(x,y), ...
3
votes
3answers
525 views

What's better for an algorithm complexity, O(log n) or amortized O(log n)?

Some context: I'm to write a program that sorts the lines of a file in C for Linux. Since I have to read all lines of the file (fgets() for example) I'm thinking ...
1
vote
1answer
41 views

Constructing a Divide and Conquer Algorithm

I'm thinking of using something similar to the Merge Sort algorithm. So the recurrence running time of Merge Sort is T(n) = 2T(n/2) + n. What should I do about if n/2 is less than or equal to m, OR ...
1
vote
0answers
357 views

Insertion sort Proof by Induction

I am reading Algorithm design manual by Skiena. It gives proof of Insertion sort by Induction. I am giving the proof described in the below. Consider the correctness of insertion sort, which we ...
10
votes
3answers
932 views

Practical Applications of Radix Sort

Radix sort is theoretically very fast when you know that the keys are in a certain limited range, say $n$ values in the range $[0\dots n^k -1]$ for example. If $k<\lg n$ you just convert the ...
2
votes
0answers
156 views

Why does Shellsort work well on Sorted and Reverse ordered lists?

I've ran some tests and found that Shellsort runs much faster on ordered and reversed lists compared to random lists and almost ordered lists. ...
5
votes
0answers
106 views

What Measure of Disorder to use when Analysing Quicksort

I'm trying to understand why quicksort using Lomuto partition and a fixed pivot is performing erratically, but overall poorly, on randomly generated inputs. I'm thinking that even though the inputs ...
14
votes
1answer
428 views

How to measure “sortedness”

I'm wondering if there is a standard way of measuring the "sortedness" of an array? Would an array which has the median number of possible inversions be considered maximally unsorted? By that I mean ...