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]

For questions about sorting algorithms and their speed and complexity.

-2
votes
0answers
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) ...
-1
votes
2answers
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, ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
2
votes
3answers
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. ...
1
vote
2answers
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 ...
2
votes
2answers
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 ...
2
votes
2answers
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: ...
0
votes
2answers
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 ...
6
votes
3answers
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 ...
1
vote
0answers
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....
0
votes
1answer
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 ...
5
votes
2answers
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 ...
3
votes
3answers
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 ...
11
votes
2answers
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 ...
2
votes
2answers
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 ...
2
votes
2answers
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 ...
0
votes
1answer
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 ...
2
votes
3answers
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 ...
3
votes
2answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
-1
votes
2answers
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}...
1
vote
3answers
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 ...
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
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 ...
0
votes
1answer
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 ...
2
votes
5answers
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, ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
3
votes
2answers
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 ...
3
votes
8answers
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 ...
1
vote
0answers
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 ...
-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
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 ...
1
vote
4answers
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 ...
3
votes
2answers
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 ...
2
votes
1answer
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 ...
5
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
2answers
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 ...
1
vote
1answer
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 ...
-2
votes
1answer
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 ...
5
votes
1answer
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 ...
0
votes
4answers
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" ...
-1
votes
1answer
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 ...
2
votes
1answer
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 ...
-1
votes
2answers
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.
2
votes
4answers
550 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
66 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 ...