# Questions tagged [sorting]

For questions about sorting algorithms and their speed and complexity.

185 questions
24 views

### Quicksort Algorithm with Pivot element as Median [on hold]

I'm unable to understand the concept - Let's say our Partition Algorithm always choose median as pivot element then what will be the Time Complexity of Quicksort when inputs are as follows - Case a) ...
159 views

### When to use Quicksort instead of MergeSort? [closed]

I have the following homework question: You develop a video surveillance software that must run on real-time data. In one of the steps of the algorithm executed with each image captured by the camera, ...
89 views

### Sorting an array of ranges for display

I have an array of ranges with start and end timestamps. I want to display those ranges on a graph. Right now, my naive algorithm gets an array of ranges sorted by their start timestamp and iterate ...
50 views

### Compare two arrays by the number of occurances

I have the following dictionary: { "Drama": 8, "Adventure": 8, "Action": 4, "Comedy": 3, "Thriller": 1 } This dictionary is like a representation of a user's preferences in movies. (in the past he ...
376 views

### Is this a sorting algorithm faster than O(n*log(n))

If there are n variables each with m possible values. (For integer, m is 2 billion something.) First, map every possible value to an integer from 0 to m-1 in order. And define the mapping functions. ...
272 views

### Why is stability considered a desirable trait of a sorting algorithm?

The common argument for stability in a sorting algorithm typically involves an example where a list is sorted by two criteria. For example: 1,4,5,7,2,6,8,9,15,65,24,27 sort by evenness/oddness and ...
81 views

### PHP Sort question

I have a camera based security system that uploads all its images via FTP to a folder in one of my hosting accounts. (FYI, I use it to watch my cats when I'm traveling). So I created a PHP file to ...
370 views

### Can nested loop have linear time complexity

I was going through the traditional quick sort algorithm. I had a look on the partition algorithm in a couple of places and the implementation difference was very subtle. Here are the 2 approaches: ...
345 views

### Google Search: Results Ordered by Relational Position in Texts

This applies to the Google API for situations where there are many (thousands of) hits in Web text searches. When searching large text sources, typically books, the default display order of results of ...
969 views

### Algorithm to sort ten million 7-digit integers in ascending order with just 1.5Mb RAM?

Given a file containing at most ten million 7-digit integers with no duplicates. What is an efficient way to print these numbers in ascending order using just 1.5MB RAM and reading the data just ...
27 views

### Sorting a list of objects with re-ordering and different views

The problem I have is this: I have a list of items. Each item has multiple properties. I have a view where I display all items and I have a view where I display the items based on values in properties....
49 views

### Question about memory handling of trees and certain sorts on large data sets.

If data structures such as trees and certain sorts(quick sort, merge sort) work using recursive algorithms and recursive algorithms take up a lot of memory space in the stack and can only work on a ...
250 views

### Grouping objects according to a set of fields

I would like to sort a list of people into buckets, as duplicates, by an email comparison, but I can't seem to find an efficient way. Specifications A person has 5 email fields, so in order to know ...
1k views

### In merge sort, why not just split to individual items immediately rather than recursively splitting in half?

In learning the merge sort, the examples show the list of items being split in half over and over again and then merged again. Why not just start with iterating over the individual item pairs in the ...
1k views

### Is the IComparable interface outdated/“harmful”?

IComparable only works one way Let's say you have a Employee class. In one view, you want to show all Employees sorted by name - in another, by address. How are you going to achieve that? Not with ...
138 views

### Receive data in random order, send in order

I am facing an issue where I have a data stream that sends unordered data. I'm trying to find a way to receive the data in random order, but send it in order. As an example, I'll receive object4 and ...
106 views

### Handling sort-order / display-order integer as a field in collection/table [duplicate]

Say we have a column in table or a property in a collection called "sortOrder" which simply is an integer which denotes which order it is to appear when displayed. I am trying to figure out the ...
113 views

### Algorithm to identify differences between two sorted data sets

PROBLEM STATEMENT: Print the items that differ between the following two left and right sorted data sets: A A B C C D D E G F H EOF EOF The proposed solution ...
225 views

### Resolving foreign keys: breaking cycles to enable a topological sort

Background to avoid the X-Y problem: I'm building a database migration system that needs to resolve foreign key constraints (see here for full background). I need to determine what order I can ...
241 views

### Parallel sorting algorithm that compares all elements

I'm implementing an algorithm that needs to Sort elements, in parallel (this will be done on a GPU, but that doesn't matter much) Compute a comparison metric for every pair of elements. This ...
2k views

### Why is the optimal choice for a pivot in quicksort algorithm the median element?

Lately i have been taking an course at brilliant.org, i was exploring a lesson on QuickSort algorithm, found a question. Which of the following would provide the optimal pivot selection at each step ...
74 views

### Sorting method for music avoiding title and artist repetition

I'm looking for pseudocode suggestions for sorting my mp3 files in a way that avoids title and artist repetition. I listen to crooners - Frank Sinatra, Tony Bennett, Ella Fitzgerald etc. singing old ...
158 views

### Why in Tournament Sorting do we neglect the number of comparisons to find the Minimum?

Here the professor said that, Tournament sort needs (n-1) + 2(n-1)logn comparisons. {Where (n-1) for calculating Maximum or say creating Tournament structure and 2(n-1)logn for other elements to sort}...
471 views

### Which data structure is best for an auto complete drop down that learns?

I made an auto complete text box for an application I'm working on. The text box basically has an associated list that it searches each time you enter something in the box. If you enter something ...
2k views

### Mostly sorted arrays: Insertion sort vs insert at sorted position

I'm trying to figure out the most efficient way of maintaining a sorted ArrayList. I'm inserting items into the array one at a time. I'm deciding between two methods: inserting the item at the sorted ...
315 views

### Javascript queue-like key-pair sorted collection

I'm looking for a collection that would suit my scenario: I will be inserting key-value pairs (both integers) of ID and timestamp. The ID must be unique. At some interval I will be checking that ...
608 views

### Lower bound for finding a value in sorted array

Suppose we have a sorted array of unique elements, A[n]. I am trying to find the lower bound for finding a specific element x in the array. I suspect the lower bound to be log_2(n+1). I tried to use ...
730 views

### Fastest algorithm of dividing array into positive and negative numbers

Given array of integers I am trying to design the fastest algorithm that swaps the elements such that at the end : all negative elements are on the left and then the positive elements, for example, ...
50 views

### Simple algorithm for computing an orderable value from a string

I would like to compute a numeric value for strings containing only /[a-z0-9]/i (ignore case). Later, I want to use this value for sorting rows. For this post, I am ignoring number also. My thinking ...
62 views

### Sorting by setting a sequence property instead of rearranging the position in the list

In my project I have a list of items that should be sorted, but instead of re-arranging the positions of the items in the array I want to set a 'Sequence' property defining the item's places in the ...
984 views

### Insertion sort vs Merge sort - memory access

I am a computer science sophomore doing a data structures and algorithms course. My professor said that insertion sort requires random access, while merge sort does not. According to him, the ...
4k views

### How to make ability to order records in DB?

I need to make ability to reorder records, storing in DB (I use MS SQL, but seems it's no matter). I see possible 2 solutions: Add Order column. Then if we want to reorder 2 records, we need to ...
79 views

### Is a topological sort required here?

Say you are writing an ORM like entity framework. You write basic POCO, and then let entity framework do the job of creating equivalent structures in the database according to those objects. This ...
68 views

### A concise way of permanently sorting a bullet list on a wiki

See this link. At the moment an extension is sorting the list through a tag (using a render hook?): <sort2> * C * A * B </sort2> Outputs: A B C However, the result is temporary in ...
351 views

### Majority voting algorithm, there are n people and m candidates but m is known

The question is long, so I will paraphrase it briefly Q: There are n people voting to choose the chair of the committee. Each person can vote for one person that has unique id (it is positive integer ...
1k views

### How does the dividing Step in Merge Sort have Constant Time Complexity?

I am highly confuse while calculating time complexity of Merge Sort Algorithm. Specifically on the Dividing Step. In the dividing step we have to calculate the mid point of "n" i.e. "q = n/2". How ...
640 views

### Remove gaps between non-overlapping segments of an array of time elements

I have an array of elements, each with a start time and an end time. These form a timeline, some of which overlap, and others that do not (and have a gap between groups of overlapping elements). I ...
178 views

### Batch insert a group of elements into a sorted list and get their indices

I'm working on an update process which inserts items into a sorted list, and processes those items' indices in the sorted list. To help me with this, I created a sorted list with an "insert" method ...
764 views

### How does K&R's qsort work?

In the recursion section of K&R's ANSI C book, they demonstrate a version of quicksort [that] is not the fastest possible, but it's one of the simplest. --The C Programming Language (ANSI ...
340 views

### Sorting a Data Set with multiple 'Tie Breaks'

I'm currently working on a software project that requires several different types of sorting mechanisms. I have been searching, to no avail, to find an algorithm to do a sort with tie-breaking. In ...
78 views

### How can I efficiently add/delete/get sorted data in Java?

I am writing a telephone directory program and need to store the entries in a CSV formatted file. However, I am having difficulty keeping the entries in order when adding. I was considering reading in ...
552 views

### Should I use this very short Python Quicksort implementation?

def quicksort(N): if len(N) < 2: return N else: less = quicksort([number for number in N[1:] if number < N[0]]) more = quicksort([number for number in N[1:] if ...
1k views

### How does this recursive function exit? [closed]

In the merge_sort part, there are multiple calls to the same function within the recursive. How are the other two executed when the definition holds that till a condition is false, the recursion does ...
529 views

### Why does Erlang provide built-in ordering(sorting) of the basic data types?

In Erlang, an ordering of the built-in basic data types has been established: number < atom < reference < fun < port < pid < tuple < list < bit string This means that sorting ...
232 views

### a funky interleaved sorting problem

I have an array of items. Some items have a number on both sides. I'll call these "matched pairs". I need to sort the items between the matched pairs in a particular way. There's a "from number" ...
971 views

### Data structure for storing sorted data

What's a good way to store loads of sorted string on a file so that inserts and reads are fast? I could store it up in a tree, and read/modify/store it as needed, but that seems wasteful for ...
184 views

### How to combine N non-comparable arrays up to an output limit in a fair way?

Given N non-comparable arrays of different sizes, what is the best method to combine them into one output array? Since the input arrays are non-comparable, a metric is needed to represent how ...
1k views

### Most efficient way to find top values

Let's say we're given n positive integers in random order. What's the most efficient way to find the m largest elements and what's the complexity? For example, given 1000 values, find the top 10.