Questions tagged [sorting]
For questions about sorting algorithms and their speed and complexity.
204 questions
6
votes
2
answers
442
views
How can I keep data defragmented and sorted if it's large and often changes randomly?
This problem is very relevant to games and real-time simulations but it may have broader applications. It seems inherently difficult to solve.
The problem:
Imagine that you have a large buffer of data,...
- 69
-1
votes
1
answer
149
views
Optimizing Sorting and Order Management in CoreData
Sorting is an important feature in my app. I am using integers to represent the ordering sequence.
Items: A, B, D, E, H
Order number: 0, 1, 2, 3, 4
When I insert a new item "C", here'...
- 468
1
vote
3
answers
255
views
Merge Sort Concept Understanding
Merge Sort contains basically two important routines:
(i) split
(ii) merge.
I get the general idea. But I dont understand how this is more efficient than some random bad sort algorithm, like selection ...
- 21
2
votes
1
answer
187
views
can partial optimized Bozosort improve speed of sorting?
First of all, I am serious :)
You have array of N elements and we can compare them (e.g. operator > works).
Let's try to (unstable) sort it using following brand new sorting algorithm.
First, ...
- 305
1
vote
4
answers
313
views
During a peer evaluation of code, is it constructive to suggest changes for the sake of making the code look "pretty"?
Is it a valid code review criticism to have someone manually arrange the order of keys in a dictionary or map they created for a feature, by numerical or alphabetical order when it doesn't improve ...
- 29
8
votes
2
answers
943
views
Why are sort() and reverse() JavaScript methods in-place?
Which are the technical reasons/considerations for the sort() and reverse() JavaScript array methods to be in-place operations instead of returning a new array without modifying the original one, like ...
- 231
0
votes
1
answer
183
views
Storing Sort Order in Database: match the business logic or the application logic? [closed]
Take a profile page for a job applicant with a list of names in a form with typical CRUD:
Resume Name:
Altenrate Name 1:
Alternate Name 2:
Alternate Name 3:
Assuming we have some sort of Names table ...
- 1,389
-1
votes
1
answer
315
views
Binary search is not fast
I am trying to put in practice an algorithm for binary searching and compare it with linear searching:
linear search:
public static int linearSearch(ArrayList<Book> books, int searchedId) {
...
- 128
2
votes
0
answers
229
views
What algorithm can I use to spread a workload between two processor with fixed resources?
I need to write an algorithm to allocate x number of tasks to 2 processors per day.
I know the following:
Exact amount of time it will take to complete each task
The exact amount of time available ...
- 39
8
votes
2
answers
7k
views
Is there a sensible way to sort coordinates?
Sorting is generally used to solve problems where distance between elements matters. A sorted list/array has the convenient property that the smaller the difference between the indices of any two ...
- 1,179
1
vote
2
answers
416
views
Algorithm for rule-based sorting?
I am trying to plant a garden. Certain plants are good for some plants and bad for others, and I am trying to find the best order of plants: most adjacent friends and no adjacent foes, as defined in ...
- 119
-4
votes
1
answer
429
views
What is the worst case Time Complexity for only the Divide Portion of the Merge Sort Algorithm?
Please, consider the below merge sort algorithm. Here we start with a divide portion which splits the array into halves and we do recursive operation on each half separately. I have ignored the merge ...
- 1
8
votes
7
answers
3k
views
Best algorithm to sort tasks by priorities by a human
I have developed a task management tool. And some task lists can be very large. (I have myself more than 300 tasks to do).
I would like to do some task reviews from time to time as the tasks pile up ...
- 215
-3
votes
1
answer
284
views
How to sort a list by multiple attributes and units?
I'm trying to find a source of information to explain how to sort a list of items considering their multiple attributes and units. All I can find on the internet is code example on sorting Javascript ...
- 103
2
votes
3
answers
6k
views
What means "breaking ties" in context of sorting
As an interview assignment for software developer, I have received the task. I have a list of children, and the task is: sort children ascending by their birth_date timestamp, breaking ties by ID
The ...
user372012
-2
votes
1
answer
3k
views
Iterative Sorts vs. Recursive Sorts
Naive sorts like Bubble Sort and Insertion Sort are inefficient and hence we use more efficient algorithms such as Quicksort and Merge Sort. But then, these two sorts are recursive in nature, and ...
user351663
0
votes
0
answers
331
views
Sorting and filtering: ElasticSearch vs MongoDB
This is a problem related to a typical e-commerce requirement.
I am using ElasticSearch for all the below use cases.
I am confused about whether or not to use MongoDB for the sorting part.
I have the ...
- 153
3
votes
2
answers
572
views
Sort or data structure with fewest comparisons if list is mostly sorted
Suppose you have a list of about 50 items that are already sorted and you add three items either to the end of the list or somewhere unsorted into the middle. Now you want to re-sort the list with ...
- 345
1
vote
2
answers
858
views
Sorting a list of aggregates based on associated aggregate's properties
I am modelling a users management system, where users have a country of residence. I have modeled both User and Country as aggregate roots, and I am referencing the user's country by its ID internally....
- 251
-2
votes
2
answers
270
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, ...
- 687
1
vote
1
answer
622
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 ...
- 121
1
vote
1
answer
72
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 ...
- 121
3
votes
3
answers
2k
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.
...
- 139
0
votes
2
answers
575
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 ...
- 627
2
votes
2
answers
364
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 ...
- 139
2
votes
2
answers
4k
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:
...
- 33
0
votes
2
answers
377
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 ...
6
votes
3
answers
2k
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 ...
- 267
1
vote
0
answers
51
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....
- 272
0
votes
1
answer
64
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 ...
- 21
5
votes
2
answers
633
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 ...
- 171
4
votes
3
answers
3k
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 ...
- 161
12
votes
2
answers
2k
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 ...
- 2,598
2
votes
2
answers
263
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 ...
- 167
2
votes
2
answers
427
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 ...
user286798
0
votes
1
answer
180
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 ...
- 545
2
votes
3
answers
1k
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 ...
- 396
3
votes
2
answers
500
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 ...
- 251
1
vote
1
answer
8k
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 ...
- 131
1
vote
1
answer
117
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 ...
- 21
-1
votes
2
answers
335
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}...
- 47
1
vote
3
answers
1k
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 ...
- 129
0
votes
3
answers
5k
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 ...
- 129
0
votes
1
answer
587
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 ...
- 143
0
votes
1
answer
1k
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 ...
3
votes
4
answers
2k
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, ...
- 41
0
votes
1
answer
148
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 ...
- 121
1
vote
1
answer
80
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 ...
- 143
3
votes
2
answers
1k
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 ...
- 416
4
votes
8
answers
8k
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 change ...
- 205