Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [sorting]

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

0
votes
0answers
27 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
24 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
33 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
29 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
32 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
35 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
218 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
79 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:/...
-1
votes
0answers
19 views

The worst case input for heap sort [duplicate]

What is the worst case example(input) for heap sort(for which input heap-sort behaves the worst)? Discussion When we consider a MAX-heap, then descending order sorted sequence, [ 16, 14, 10, 9, 8, 7, ...
0
votes
0answers
60 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
19 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
40 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
181 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
24 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
49 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
28 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. ...
1
vote
0answers
37 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
64 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
27 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
37 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
27 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
52 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
42 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
37 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
98 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
115 views
4
votes
1answer
30 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
20 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
55 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
26 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
312 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
48 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
47 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
94 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
63 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
37 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
18 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
vote
1answer
215 views

$O(n\log n)$ algorithm for minimizing number of inversions in leaves of complete binary tree

I'm having trouble making an algorithm to fit these specs: Given a complete binary tree ($n = 2^d$ leaves) with integers in leaves. Reading the leaves from left to right makes a sequence of integers (...
1
vote
1answer
196 views

Sorting lower bounds for almost sorted array

Can't find a good way to tackle the problem. Would appreciate any help. $A$ is an $n$ items array from an ordered set, in which every item is at most $\log n $ indices away from its position in the ...
2
votes
1answer
62 views

Greedy Solution for Selecting Prefix Sum

Given $n$ arrays. Each has size of $h$. Let $a_{i, j} \in \mathbb{I}$ be the $i$-th element of $j$-th array. You can select at most $k$ numbers from all arrays but if you pick $a_{i, j}$, you have to ...
6
votes
1answer
139 views

Sort 2D arrays so that cost of reaching new position as described at each iteration is minimized

Problem is as following: We are 8 trumpet players in an orchestra. There are for example 4 parts so there are always two players on the same part. Now, there are not always the same two players ...
4
votes
1answer
95 views

Topological sorting colored tree

EDIT: The most general case I need is not a tree but any Directed Acyclic Graph. I have a directed acyclic graph. I need to sort it in a list so that in the list every node comes after any node it ...
0
votes
0answers
32 views

Quick access to top element of subsets of elements

I have a set S of (key, value) pairs and a large number of subsets of S. I'm looking for a ...
-1
votes
1answer
41 views

Minimal shift operations to sort an array

I have been stuck on this sorting problem for a while now: Given an array of length N find the minimum number of shift operations in order to sort the array. A shift operation is defined as shifting ...
1
vote
2answers
190 views

Proof of QuickSort algorithm correctness

Recently I’ve studied QuickSort and understood its general idea. Basically, we do the following: Pick an element from the array (no matter which one and how in this context) Rearrange elements in ...
1
vote
1answer
27 views

Is there an existing algorithm for this type of sorting?

This TED-ED video talks about some of the most basic sorting methods (bubble sort, insertion sort and quick sort,) in response to a scenario where a librarian ends up with a stack of 1,280 unsorted ...
2
votes
3answers
623 views

When average , worst and best case time complexity happens in quick sort?

I know recurrence relation corresponding to quick sort worst case is $T(n)=T(n-1)+T(0)+\Theta(n)$ and time complexity is $O(n^2)$. This happens when we select pivot which is either largest element ...
0
votes
0answers
17 views

How to sort a woven shuffled stack

Say you have sort of a "woven shuffling situation" going on, sort of like this. Or that just looks like a regular shuffle for the most part. I'm trying to show the situation where something can be ...
1
vote
0answers
21 views

Spatial index search that returns sorted results

I need to perform a spatial index search while also sort the results by one of the dimensions. Backstory: I have a map with lots of 2D objects and when the user interacts with the map I need to ...