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
0answers
279 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
200 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
50 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
35 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
48 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
20 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 ...
2
votes
0answers
60 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
106 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
79 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
338 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
122 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
113 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
517 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
41 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
74 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
82 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
539 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
162 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
77 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 ...
2
votes
3answers
427 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
86 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
88 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
35 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
859 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
583 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 ...
0
votes
0answers
125 views

Sorting using AI / neural net

I have a search operation taking place on a server that essentially queries images using OpenCV against other images from a database. Since each image query ...
2
votes
1answer
69 views

How to reduce number of move operations in an array?

Say I have an array of numbers, e.g. [0, 1, 2, 3, 4, 5] and I want to end up with an array, e.g. [2, 1, 4, 0, 5, 3]. At my ...
0
votes
0answers
31 views

Does this algorithm exhibit the same behavior as Selection Sort?

This is a homework question. I have been asked to identify what sort this code below implements. ...
2
votes
0answers
54 views

A binning (sorting) algorithm

Rules: A conveyor belt is giving you little boxes. They are labeled for your convenience: Box $1$, Box $2$,... For your inconvenience, though, you can't see the number (from $1...n$) hidden in it. You ...
3
votes
1answer
88 views

Why is finding minimum number of comparisons to sort $n$ elements so difficult?

In The Art of Computer Programming 2nd Ed, Vol 3, Section 5.3.1 then discuss a function $S(n)$ which is define as: $S(n)$ : The minimum number of comparisons that suffice to sort $n$ elements. ...
1
vote
1answer
32 views

Recurrence Relation Mergesort

I was reading Algorithms 4th Edition by Sedgewick et al. and I found this statement when discussing about the analysis of mergesort: The number of compares is at most n and no less than $\lfloor n/...
0
votes
1answer
65 views

How to find examples of best cases for sorting algorithms?

I am asked to give a table of 8 elements that are to be sorted by the following algorithms and to produce their best cases. 1) Selection sort 2) Bubble sort 3) Insertion sort 4) Fusion sort If I give ...
2
votes
1answer
36 views

Consensus/ranked ordering algorithm

Say I have a set of numbers, for example {1, 2, 3, 4, 5}. Is there an algorithm that allows these numbers to be put into a consensus ordering based on a ranked vote?...
2
votes
1answer
178 views

Expected number of iterations for bozo sort opt algorithm

I'm trying to figure out the upper bound for the number of iterations of the bozo sort opt algorithm, described in this paper on section 3.2: http://www.hermann-gruber.com/pdf/fun07-final.html I know ...
0
votes
1answer
43 views

Whats the best way to sort a dataset into groups by using a facial recognition algorithm that compares only 2 images at a time?

I have a facial recognition algorithm that compares two images A and B and returns the likelihood that they match. I also have 50,000 images, and I would like to sort these images into groups. Here'...
1
vote
2answers
60 views

Find m smallest elements in an array of size n where m = n/2

So we have an unsorted array, we need to find the first $m$ elements in ascending order (or $m$ smallest elements) where $m = \mathrm{array.size}/2$ (or $n/2$). How would we do this in linear $O(n)$ ...
2
votes
1answer
1k views

How to best maintain a sorted list from a stream of integers?

If I have an incoming stream of integers how can I best maintain a sorted list of them? The only way I can think of is to binary search for the position and shifting the remaining elements to the ...
1
vote
2answers
130 views

Is this algorithm bubble sort or selection sort?

...
4
votes
1answer
52 views

Sorting strings with “before” and “after” constraints

I'm trying to solve a constraint-satisfaction problem for a project of mine that seems like it should have a well-known solution, but I can't for the life of me seem to find it described anywhere. I'...
3
votes
1answer
57 views

Are comparison sort algos appropriate for SUBJECTIVE sorting?

I've been tasked with creating an online feature that ranks 50 fantasy characters from a variety of domains based on combat acumen and polls users one which one is the most powerful based on their ...
2
votes
0answers
269 views

Worst case for linear-time k'th smallest element algorithm?

There's an algorithm for finding the k'th smallest element in an unsorted array similar to quickselect: kthSmallest(arr[0..n-1], k) 1) Divide arr[] into ⌈n/5⌉ groups where size of each group is ...
0
votes
0answers
29 views

Bubble sort that ignores rightmost sorted parts

Initial Bubble sort pseudocode(Typical): 1)foreach Element in array 2) initialise a flag that flips whenever a swap is done 3) Starting from the element, attempt to swap and update flag 4) If ...
1
vote
1answer
5k views

Implementation of QuickSort to handle duplicates

I have this past year question based on the following scenario: When the list of items to be sorted contains a lot of duplicate values, we can improve QuickSort by grouping all the values that are ...
3
votes
1answer
50 views

Random observations of a total ordering, how much they tell us?

Suppose we have a total ordering over elements $a_1,a_2, ..., a_n$, meaning there is permutation $\pi$ such that $a_{\pi(1)}<a_{\pi(2)}<...<a_{\pi(n)}$. But we don't know $\pi$. What we know ...
-2
votes
2answers
63 views

For sorting 10^9 unique 9-digit numbers, would radix sort or counting sort be faster, and why?

For sorting $10^9$ unique 9-digit numbers, would radix sort or counting sort be faster, and why? I know that radix sort is $O(nk)$ and counting sort is $O(n+k)$, but can’t understand how to apply ...
4
votes
2answers
167 views

Sorting “almost sorted” array in $O(n\log\log n)$

Given array $A$ of length $n$, we call it almost sorted if there are at most $\log n$ indices satisfying $A[i] > A[i+1]$. Find an algorithm that sorts the array in $O(n\log\log n)$. My ...
0
votes
2answers
448 views

Time complexity of quicksort for arrays in increasing or descreasing order

Two $n$-size arays are given: $n_1$ is in decreasing order and $n_2$ is in increasing order. Let $c_1$ be the time complexity for $n_1$ using quicksort, and $c_2$ the time complexity for $n_2$ using ...
0
votes
1answer
99 views

Quicksort T(n)=2T(n/2)+n

In Quicksort we devide the array in to about an half (not worst case) and we have left and right sides so it is 2T(n/2), now why in the end it is T(n)=2T(n/2)+n as we may need to go over all the array ...
0
votes
1answer
21 views

Sorting on non-linear topology

Disclaimer. What I'm going to ask about below may seem to be "Topological sorting". To my understanding, it is not. The latter runs in linear time, while I'm looking for a modification of the regular ...

1 2
3
4 5
14