Stack Exchange Network

Stack Exchange network consists of 174 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]

For questions about sorting algorithms and their speed and complexity.

2
votes
2answers
35 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 ...
-4
votes
0answers
27 views

Linked List update priority

So i have created a linkedlist from scratch which inserts and sorts via priority. The last method i need to add is an update priority method. I have a findNodeByID method which finds a node based on ...
2
votes
2answers
109 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: ...
0
votes
0answers
80 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 ...
0
votes
0answers
32 views

Combine n-Linear Series into DataGrid

I'm scratching my head at this, I really need to redesign the schema of an old existing data concept we have in our db. The more I work on it, the more I see why they took an easy way out. Currently, ...
6
votes
3answers
749 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 ...
1
vote
0answers
21 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....
0
votes
1answer
48 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 ...
5
votes
2answers
208 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 ...
3
votes
3answers
703 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 ...
10
votes
2answers
700 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
votes
2answers
131 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 ...
2
votes
2answers
89 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 ...
0
votes
1answer
100 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 ...
2
votes
3answers
156 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 ...
3
votes
2answers
238 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 ...
0
votes
1answer
1k 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 ...
1
vote
1answer
71 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 ...
-1
votes
2answers
111 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}...
1
vote
3answers
334 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 ...
0
votes
3answers
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 ...
0
votes
1answer
249 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 ...
0
votes
1answer
526 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 ...
2
votes
5answers
596 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, ...
0
votes
1answer
49 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 ...
1
vote
1answer
57 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 ...
3
votes
2answers
832 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 ...
2
votes
8answers
3k 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 ...
1
vote
0answers
66 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 ...
-1
votes
2answers
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 ...
1
vote
1answer
317 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 ...
1
vote
4answers
953 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 ...
3
votes
2answers
470 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 ...
2
votes
1answer
165 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 ...
0
votes
0answers
27 views

Sort an 2D entity-diagram

Entity-relationship-diagrams can really be a mess. I am looking for a good sortion algorithm. So what is good? My current algorithm calculates the badness-factor: No lines cross (badness-factor x2). ...
4
votes
1answer
640 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 ...
2
votes
1answer
256 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 ...
1
vote
2answers
76 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 ...
1
vote
1answer
481 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 ...
-2
votes
1answer
821 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 ...
5
votes
1answer
396 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 ...
0
votes
4answers
226 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" ...
-1
votes
1answer
733 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 ...
2
votes
1answer
183 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 ...
-1
votes
2answers
813 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.
2
votes
4answers
513 views

Which programming languages provide a Schwartzian transform like interface for sorting

Introduction The Schwartzian transform -- also known as map-sort-map or decorate-sort-undecorate (DSU) --, attributed to Randal Schwartz of the Perl community, sorts elements of a list or array by a ...
1
vote
1answer
62 views

Sorting algorithm for Provides/DependsOn objects

I have a set of type rewriters, each modifies a given C# type in a different way. Examples are: Add the XYZ attribute to each property of the class Add an ID property Add two properties and some ...
2
votes
2answers
1k views

Merge sort and O(n log n) mystery

I read every explanation here but still not convinced. I think mergesort is n * n and I know I am wrong but not sure where. Here is what I think: Suppose we are sorting 8 elements and this is the ...
6
votes
4answers
2k views

Best practice for getting last record inserted in DB

Me and a couple of colleagues are having a discussion regarding the following case: In an OrderStatus table we're keeping track of all the statuses an order goes through in time, including "Pending",...
1
vote
4answers
287 views

Should I be using any algorithm to sort/find items, or use a language's built-in ways?

I'm currently a first semester IT student, and I'm wondering if it's better to write my method to find something e.g. in a C# List, or to use any built in method to do these, such as LINQ or .Find or ....