The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [sorting]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
29 views

Idea behind using binary search to solve rolling ball?

What is the idea behind using binary search to solve this problem: There is a segment of length meters, and there are $L$ positions on it, numbered $1,2,...L$ , equally spaced by 1 meter apart ...
0
votes
1answer
23 views

Bubble sort: how to calculate amount of comparisons and swaps

For a given sequence 1, N ,2 ,N −1 ,3, N −2, ... I want to calculate the number of comparisons and swaps for bubble sort. How can I accomplish that using $\theta ()$ notation? I would know how to do ...
2
votes
1answer
54 views

Finding the fastest sorting algorithm

I was thinking about how many compares it takes to sort a list of comparable data, and I had an algorithm I was wondering the viability of. (Its not unlikely that someone has come up with this before ...
1
vote
1answer
29 views

Sorting algorithm for set of elements, when I have comparison of just some pairs not all of them

Is there some kind of algorithm for sorting of set, when there is comparison of just some pairs? Example 1: set(a, b, c, d, e) pairs(a>b, ce) Example 2: set(a, b, c, d, e) pairs(a>b, d>b, c>d, d>e)...
1
vote
1answer
48 views

Why in BFPRT (median of medians) algorithm the partition of the array by $7$ blocks would work but with the $3$ fail?

I am working with the median-median algorithm or BFPRT algorithm and I seek to understand why would the partition of the array by $7$ blocks would work but with the $3$ fail? If we divide into ...
0
votes
1answer
29 views

What is the probability of comparision between smallest and greatest element in array when quick sort randomly choose the pivot element?

Consider the recursive quick sort with random pivoting i.e. each time a random pivot element is chosen uniformly. When this ...
3
votes
2answers
66 views

How to sort a large list of elements where everything is sorted but k elements?

Assuming the list is very large, and $k$ is very small, what's the fastest algorithm to sort this list?
-1
votes
1answer
54 views

What is the Time complexity of this sorting algo?

So i was trying to write an efficient sorting algorithm and i came up with this method, Sorting an array in ascending order by flipping (exchanging) 2 adjacent integers not in the correct order ...
0
votes
0answers
9 views

Plz help me find the time complexity of this sort [duplicate]

I wrote a program of a sort that is based on mergesort but can also be done with linked list with ease. I am a beginner in evaluating time complexity so I am not being able to find the complexity here....
0
votes
0answers
33 views

Complexity of Rearranging a Prefix Tree/Alternative Data Structures

Let $S$ be a subset of $[0,1]^l$. Is there some data structure that can represent $S$ and can perform the following operations/queries efficiently*? $ADD(s \in [0,1]^l)$ - operation which updates $S$ ...
0
votes
2answers
93 views

Difference between Quick sort, Merge sort and Heap sort

We know all the above-mentioned sorting algorithms take $\mathcal{O}(\mbox{N log N})$. Merge sort and Heap sort algorithms take $\mathcal{O}(\mbox{N log N})$ time in worst-case where Quicksort takes $\...
0
votes
0answers
6 views

How to define the stability (or convergence) of a ordering of a list of node

I have a problem which requires ordering nodes in a graph based on some given statistics. However, the given statistics of each node may be very hard to compute. Thus, I will use some sampling ...
1
vote
1answer
32 views

Weird implementation of quicksort

I met a wired question from the algorithm test of my school. For the first time I thought it is a normal quick-sort problem and feel confident to solve it but as I read the algorithm carefully, it is ...
0
votes
0answers
15 views

Recurrence Formula for Bitonic Sorter Runtime

A Bitonic sorter takes a bitonic sequence as an input and the output is a sorted list. I want to analyse Bitonic Sorter by knowing its depth/runtime. Can anyone give an idea on its recurreence formula?...
0
votes
2answers
31 views

How to do a reverse topological sort using depth first search?

I'm doing a replacement for the venerable make utility that will support, among other things, automatic cleaning. The utility figures out automatically what files ...
1
vote
1answer
18 views

Lower bound for merging $m$ sorted arrays (decision tree leaves count - permutations)

I need some help understanding how to calculate the lower bound on the time complexity of merging $m$ sorted arrays of length $n$. The bound should be $nm \lg(m)$. I need to prove this using a ...
0
votes
1answer
74 views

Selection Sort vs Insertion Sort For Reversed Array

I had a question in a test, which asked me the following question: Selection sort runs faster than Insertion sort for an array in reverse order. Now, according to my knowledge, both of them have a ...
1
vote
1answer
55 views

Recursive Bubble Sort Complexity

I have this code for a recursive bubble sort: ...
-1
votes
2answers
34 views

Any array takes at least log(n!) compairs to be sorted [duplicate]

I have to prove that there is no comparison based algorithem that can sort a randomly given array in less than log(n!) steps. Lets say the array has 5 elements, it is impossible to sort it (using ...
1
vote
1answer
69 views

Is there a linear-time algorithm to determine if an array has duplicate entries that uses only constant extra space?

Determining whether or not an array has duplicate entries has two straightforward solutions: Build a hashset of entries, then search for elements in this hashset. This takes $\mathcal O(n)$ time and $...
1
vote
1answer
35 views

Algorithm Analysis of Insertion Sort

Why is the recurrence formula for insertion sort is T(n-1) + n? I understand the T(n-1) part but the why does the cost for ...
0
votes
1answer
45 views

Question about how can i determine if counting sort is the right option over other sorting algorithms

So, an exam's exercise asks me to find an alghoritm that can determine if counting sort is the best solution, otherwise use another optimal sorting algorithm. Now i find that solutions for that ...
2
votes
1answer
128 views

Sorting an array of strings by length in linear complexity

I am trying to find an algorithm to sort an array of strings by length in O(n) time complexity, and O(1) space complexity. The max length of the strings is known. Because of that, I tried using ...
2
votes
1answer
19 views

Analysis of straight insertion

I'm currently reading through N. Wirths': Algorithms + Data Structures = Programs. I'm not sure, but I think there might be an error in the analysis of the provided straight insertion sort. Screenshot ...
0
votes
0answers
74 views

How to find the “odd one out” in a list of numbers

I have an array of numbers [x1, x2, x3, etc] that is size is over 20 elements and I'm trying to put together an algorithm to sort the elements based on the "oddness" they have relative to the rest of ...
1
vote
2answers
192 views

What is the name of this sorting algorithm?

I have typeset in a Wikipedia draft this sorting algorithm. It is a comparison sort, yet can handle only numeric arrays. Basically, it marches through the input array and for each new array ...
0
votes
0answers
49 views

Number of comparisons in array where each element appears n/k times [duplicate]

Given an array of $n$ elements with $k$ distinct elements, each appearing $n/k$ times, how can I show that the number of comparisons to the sort the array in the worst case is in $\Omega(n \log k)$?
1
vote
0answers
27 views

time complexity of k-bubble sort [duplicate]

I'm a student. today I answered a question wrong, the question is this: Spouse we have a k-bubble sort, which means except sorting 2 elements each time, it has a magical function that can sort $k$ ...
2
votes
1answer
29 views

Does Google's PageRank count as a sorting algorithm?

Is it correct to assume that PageRank is a sorting algorithm or does it fall in any other category?
1
vote
0answers
19 views

Randomized Quick Selects' time complexity dependence on k - the index to be selected

I was analyzing Randomized Quick Selects' time complexity, as a function of n - the size of the input, and k - the index of the element that needs to be selected. The time complexity dependence on n ...
1
vote
0answers
30 views

Goemans' Extended Formulation of the Permutahedron And Comparator Networks that are not Sorting Networks

I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are not sorting networks. In his paper "Smallest Compact ...
4
votes
2answers
90 views

sorting with noisy but persistent answers

Given a set of elements $A$ and a probability of noise $p<0.5$. For any two elements $x,y\in A$ we can ask the oracle $O$ to know where $x$ stands w.r.t $y$ (0 means $x$ is smaller than $y$ and 1 ...
3
votes
1answer
45 views

Lower Bound for Time Complexity of Pairing Problem

Given an array X and array Y both of length n, the pairing algorithm will return the elements of the arrays matched so that the smallest element in X will be matched with the smallest element of Y, ...
3
votes
2answers
102 views

Is finding Kth largest element using selection algorithm taking O(n) only if K is fixed?

Wikipedia here https://en.m.wikipedia.org/wiki/Selection_algorithm shows an algorithm using sort of quicksort.. in order to find Kth largest or smallest element taking O(n) time only on average. The ...
3
votes
2answers
63 views

Minimum depth of a leaf in a tree that corresponds to a comparison-based sorting algorithm

The lower bound of comparisons in a comparison-based sorting algorithm is $\log_2 n!=Θ(n\log n)$. Yet there can be less comparisons needed in an algorithm. If you take a sorted array, it will take $n-...
0
votes
0answers
30 views

Least distance sorting [duplicate]

There are 10 Egyptian stone statues standing in a row in an art gallery hall. A new curator wants to move them so that the statues are ordered by their height. How should this be done to minimize the ...
2
votes
2answers
171 views

Minimum number of comparisons in comparison-based sorting algorithms [duplicate]

I've seen that every comparison-based sorting algorithm must perform at least $\log_{2}(n!)=\Omega(nlog(n))$ comparisons on some input (n being the size of the input). Why is the minimum number of ...
0
votes
0answers
37 views

Proof that this sorting algorithm sorts the input

I'm given this "sorting" algorithm and now I'm supposed to prove, that if given an array of integers of length $n$, sort(A,0,n-1) will sort it. ...
0
votes
2answers
32 views

Quicksort Algorithm with Pivot element as Median

I have read that when pivot element is choosen as Median, then QS Algorithm gets nearly balanced splits and have time complexity of O(nlogn), but my doubt is what if all the elements of the input are ...
1
vote
2answers
51 views

Quicksort where element comparison outcome is random. Probability of element being in a certain position

So we have this block of pseudocode: Monsters = [M1,M2,M3,M4,M5,M6,M7,M8]; qsort(Monsters,rand_compare); qsort() sorts the ...
1
vote
1answer
96 views

AVL Tree - Print ascending using in-order

Trying to understand how to write proof of correctness. Searched over the internet on how to write proof of correctness but can't find a good solution for it. The following sorting algorithm is ...
0
votes
1answer
47 views

Quick sort worst case complexity improvement [closed]

Can the worst case time complexity of quick sort be changed from $O(n^2)$ to $O(n\log n)$ by modifying it?
14
votes
1answer
1k views

Can the sorting of a list be verified without comparing neighbors?

A $n$-item list can be verified as sorted by comparing every item to its neighbor. In my application, I will not be able to compare every item with its neighbor: instead, the comparisons will ...
1
vote
1answer
38 views

Self-balancing binary search tree optimized for insertion

I've written a "quiz" that prompts the user for comparisons between two items of subjective value, and once the position of all of the items is determined, displays an ordered list from most valuable ...
0
votes
1answer
231 views

Can this “double pop” Heapsort variation speed up sorting on average?

For classic Heapsort (in this example using a maxheap), only the root node is extracted (popped) at each iteration and the last element in the heap is swapped into its place and then the tree is "re-...
0
votes
2answers
84 views

Is this a new sorting algorithm?

I just came up with a simple sorting algorithm that is faster than ShellSort when the range of values is smaller than the number of elements. Is this new? And if so, what should I do with it? https:/...
0
votes
0answers
64 views

Given n strings, how to output their order after k phases of the radix sort (huge constraints)?

Disclaimer This is not from an ongoing contest, this is from my course of ITMO on edx.org, which is a paid code so I cannot give you a direct link to the course. Problem You are given $\...
1
vote
1answer
29 views

Kth smallest element in an arra [duplicate]

What would be an efficient method to find the kth smallest element in an array with worst case time complexity being $ O(n) $?
0
votes
1answer
176 views

radix-sort with different bases

So i understand how to use radix-sort in base 10 and utilize mod 10 to go through the numbers. But not sure about 2,8 or 16. Does it follow the same idea? and i read somewhere that i need to pass ...
2
votes
2answers
220 views

Is there a sorting algorithm of order $n + k \log{k}$?

I'm given an integer vector which is said to contain many duplicate values (total of k distinct integers), for example ...