# Search Results

• ### Merge sort versus quick sort performance

##### - by Giorgio
I have implemented merge sort and quick sort using C (GCC 4.4.3 on Ubuntu 10.04 running on a 4 GB RAM laptop with an Intel DUO CPU at 2GHz) and I wanted to compare the performance of the two algorithms. The prototypes of the sorting functions are: void merge_sort(const char **lines, int start, int end); void quick_sort(const char **lines, int start, int end); i.e. both take an array of pointers to strings and sort the elements with index i : start <= i <= end. I have produced some files containing random strings with length on average 4.5 characters. The test files range from 100 lines to 10000000 lines. I was a bit surprised by the results because, even though I know that merge sort has complexity O(n log(n)) while quick sort is O(n^2), I have often read that on average quick sort should be as fast as merge sort. However, my results are the following. Up to 10000 strings, both algorithms perform equally well. For 10000 strings, both require about 0.007 seconds. For 100000 strings, merge sort is slightly faster with 0.095 s against 0.121 s. For 1000000 strings merge sort takes 1.287 s against 5.233 s of quick sort. For 5000000 strings merge sort takes 7.582 s against 118.240 s of quick sort. For 10000000 strings merge sort takes 16.305 s against 1202.918 s of quick sort. So my question is: are my results as expected, meaning that quick sort is comparable in speed to merge sort for small inputs but, as the size of the input data grows, the fact that its complexity is quadratic will become evident? Here is a sketch of what I did. In the merge sort implementation, the partitioning consists in calling merge sort recursively, i.e. merge_sort(lines, start, (start + end) / 2); merge_sort(lines, 1 + (start + end) / 2, end); Merging of the two sorted sub-array is performed by reading the data from the array lines and writing it to a global temporary array of pointers (this global array is allocate only once). After each merge the pointers are copied back to the original array. So the strings are stored once but I need twice as much memory for the pointers. For quick sort, the partition function chooses the last element of the array to sort as the pivot and scans the previous elements in one loop. After it has produced a partition of the type start ... {elements <= pivot} ... pivotIndex ... {elements > pivot} ... end it calls itself recursively: quick_sort(lines, start, pivotIndex - 1); quick_sort(lines, pivotIndex + 1, end); Note that this quick sort implementation sorts the array in-place and does not require additional memory, therefore it is more memory efficient than the merge sort implementation. So my question is: is there a better way to implement quick sort that is worthwhile trying out? If I improve the quick sort implementation and perform more tests on different data sets (computing the average of the running times on different data sets) can I expect a better performance of quick sort wrt merge sort? EDIT Thank you for your answers. My implementation is in-place and is based on the pseudo-code I have found on wikipedia in Section In-place version: function partition(array, 'left', 'right', 'pivotIndex') where I choose the last element in the range to be sorted as a pivot, i.e. pivotIndex := right. I have checked the code over and over again and it seems correct to me. In order to rule out the case that I am using the wrong implementation I have uploaded the source code on github (in case you would like to take a look at it). Your answers seem to suggest that I am using the wrong test data. I will look into it and try out different test data sets. I will report as soon as I have some results.

• ### How is counting sort a stable sort?

##### - by eSKay
Suppose my input is (a,b and c to distinguish between equal keys) 1 6a 8 3 6b 0 6c 4 My counting sort will save as (discarding the a,b and c info!!) 0(1) 1(1) 3(1) 4(1) 6(3) 8(1) which will give me the result 0 1 3 4 6 6 6 8 So, how is this stable sort? I am not sure how it is "maintaining the relative order of records with equal keys." Please explain.

• ### Quick Sort Vs Merge Sort

##### - by Ganesh M
Why might quick sort be better than merge sort ?

• ### Java Alphabetize Algorithm Insertion sort vs Bubble Sort

##### - by Chris Okyen
I am supposed to "Develop a program that alphabetizes three strings. The program should allow the user to enter the three strings, and then display the strings in alphabetical order." It's instructed that I need to use the String library compareTo()/charAt()/toLowerCase() to make all the characters lowercase so the Lexicon comparison is also a alphabetical comparison. Input Pseudo Code: String input[3]; Scanner keyboard = new Scanner(System.in); System.out.println("Enter three strings: "); for(byte i = 0; i < 3; i++) input[i] = keyboard.next() The sorting would be Insertion Sort: 321 2 3 1 2 31 231 1 23 1 2 3 1 23 1 23 123 Bubble Sort 321 231 213 123 Which would be more efficient in this case? The bubble sort seems to be more efficient though they seem to have equal stats for worst best and avg case, but I read the Insertion Sort is quicker for small amounts of data like my case.

• ### Sort list using stl sort function

I'm trying to sort a list (part of a class) in descending containg items of a struct but it doesn't compile(error: no match for 'operator-' in '__last - __first'): sort(Result.poly.begin(), Result.poly.end(), SortDescending()); And here's SortDescending: struct SortDescending { bool operator()(const term& t1, const term& t2) { return t2.pow < t1.pow; } }; Can anyone tell me what's wrong? Thanks!

• ### Using selection sort in java to sort floats

##### - by user334046
Hey, I need to sort an array list of class house by a float field in a certain range. This is my code for the selection sort: public ArrayList<House> sortPrice(ArrayList<House> x,float y, float z){ ArrayList<House> xcopy = new ArrayList<House>(); for(int i = 0; i<x.size(); i++){ if(x.get(i).myPriceIsLessThanOrEqualTo(z) && x.get(i).myPriceIsGreaterThanOrEqualTo(y)){ xcopy.add(x.get(i)); } } ArrayList<House> price= new ArrayList<House>(); while(xcopy.size()>0){ House min = xcopy.get(0); for(int i = 1; i < xcopy.size();i++){ House current = xcopy.get(i); if (current.myPriceIsGreaterThanOrEqualTo(min.getPrice())){ min = current; } } price.add(min); xcopy.remove(min); } return price; } Here is what the house class looks like: public class House { private int numBedRs; private int sqft; private float numBathRs; private float price; private static int idNumOfMostRecentHouse = 0; private int id; public House(int bed,int ft, float bath, float price){ sqft = ft; numBathRs = bath; numBedRs = bed; this.price = price; idNumOfMostRecentHouse++; id = idNumOfMostRecentHouse; } public boolean myPriceIsLessThanOrEqualTo(float y){ if(Math.abs(price - y)<0.000001){ return true; } return false; } public boolean myPriceIsGreaterThanOrEqualTo(float b){ if(Math.abs(b-price)>0.0000001){ return true; } return false; } When i call looking for houses in range 260000.50 to 300000 I only get houses that are at the top of the range even though I have a lower value at 270000. Can someone help?

• ### unexpected result from gnu sort

##### - by funkycat
when I try to sort the following text file 'input': test1 3 test3 2 test 4 with the command sort input the output is exactly the input. Here is the output of od -bc input : 0000000 164 145 163 164 061 011 063 012 164 145 163 164 063 011 062 012 t e s t 1 \t 3 \n t e s t 3 \t 2 \n 0000020 164 145 163 164 011 064 012 t e s t \t 4 \n 0000027 It's just a tab separated file with two columns. When I do sort -k 2 The output changes to test3 2 test1 3 test 4 which is what I would expect. But if I do sort -k 1 nothing changes with respect to the input, whereas I would expect 'test' to sort before 'test1'. Finally, if I do cat input | cut -f 1 | sort I get test test1 test3 as expected. Is there a logical explanation for this? What exactly is sort supposed to do by default, something like: sort -k 1 ? My version of sort: sort (GNU coreutils) 7.4

• ### How to UNIX sort by one column only?

##### - by ssn
I know that the -k option for the Unix sort allow us to sort by a specific column and all of the following. For instance, given the input file: 2 3 2 2 1 2 2 1 1 1 Using sort -n -k 1, I get an output sorted by the 1st column and then by the 2nd: 1 1 1 2 2 1 2 2 2 3 However, I want to keep the 2nd column ordering, like this: 1 2 1 1 2 3 2 2 2 1 Is this possible with the sort command?

• ### function to org-sort by three (3) criteria: due date / priority / title

##### - by lawlist
Is anyone aware of an org-sort function / modification that can refile / organize a group of TODO so that it sorts them by three (3) criteria: first sort by due date, second sort by priority, and third sort by by title of the task? EDIT: If anyone can please help me to modify this so that undated TODO are sorted last, that would be greatly appreciated -- at the present time, undated TODO are not being sorted: ;; multiple sort (defun org-sort-multi (&rest sort-types) "Multiple sorts on a certain level of an outline tree, or plain list items. SORT-TYPES is a list where each entry is either a character or a cons pair (BOOL . CHAR), where BOOL is whether or not to sort case-sensitively, and CHAR is one of the characters defined in `org-sort-entries-or-items'. Entries are applied in back to front order. Example: To sort first by TODO status, then by priority, then by date, then alphabetically (case-sensitive) use the following call: (org-sort-multi '(?d ?p ?t (t . ?a)))" (interactive) (dolist (x (nreverse sort-types)) (when (char-valid-p x) (setq x (cons nil x))) (condition-case nil (org-sort-entries (car x) (cdr x)) (error nil)))) ;; sort current level (defun lawlist-sort (&rest sort-types) "Sort the current org level. SORT-TYPES is a list where each entry is either a character or a cons pair (BOOL . CHAR), where BOOL is whether or not to sort case-sensitively, and CHAR is one of the characters defined in `org-sort-entries-or-items'. Entries are applied in back to front order. Defaults to \"?o ?p\" which is sorted by TODO status, then by priority" (interactive) (when (equal mode-name "Org") (let ((sort-types (or sort-types (if (or (org-entry-get nil "TODO") (org-entry-get nil "PRIORITY")) '(?d ?t ?p) ;; date, time, priority '((nil . ?a)))))) (save-excursion (outline-up-heading 1) (let ((start (point)) end) (while (and (not (bobp)) (not (eobp)) (<= (point) start)) (condition-case nil (outline-forward-same-level 1) (error (outline-up-heading 1)))) (unless (> (point) start) (goto-char (point-max))) (setq end (point)) (goto-char start) (apply 'org-sort-multi sort-types) (goto-char end) (when (eobp) (forward-line -1)) (when (looking-at "^\\s-*\$") ;; (delete-line) ) (goto-char start) ;; (dotimes (x ) (org-cycle)) )))))

• ### Sort files in folders by size (Mac OS X)

##### - by Željko Filipin
I have a folder full of folders and files. I want to sort files by size (so I could remove the largest files). I know how to do that in Windows Explorer, but I can not find a way to do it in Mac OS X Finder. Windows 2003: open folder in Windows Explorer click button Search leave Search for files or folders named and Containing text text fields empty click button Search Now sort by size Is there a way to do something like this in Finder on Mac OS X?

• ### Merging and sorting multiple files with "sort"

##### - by NewbiZ
Hello, I have a bunch of text logfiles in the following format: ID (17 characters) Timestamp (14 characters YYYYmmddHHMMSS e.g. "20060210100040" -> 2006/02/10 10:00:40) Random data (? characters) end of line The files are already sorted by timestamp. I need to get 1 log file with all the logs from multiple logs files, sorted by timestamp. Note that the log files are really huge, around 3-4G each (and there are dozens of them) I tried the following command: sort -s -m -t '|' -k1n,1n +17 -o data_sort.txt *.TXT Here is how I ended up with this command: -s : don't bother with tie results -m : merge all logs files -t '|' : there is no | in my logs, so the whole line should be field 1 -k1n,1n: sort on the first field as a numeric value +17 : the timestamp starts at index 17 -o : output file Actually... it fails miserably. The output file data_sort.txt is just the concatenation of all files, not sorted at all :( I would greatly appreciate if anyone could provide any help on this problem! Thanks

• ### List.Sort in C#: comparer being called with null object

##### - by cbp
I am getting strange behaviour using the built-in C# List.Sort function with a custom comparer. For some reason it sometimes calls the comparer class's Compare method with a null object as one of the parameters. But if I check the list with the debugger there are no null objects in the collection. My comparer class looks like this: public class DelegateToComparer<T> : IComparer<T> { private readonly Func<T,T,int> _comparer; public int Compare(T x, T y) { return _comparer(x, y); } public DelegateToComparer(Func<T, T, int> comparer) { _comparer = comparer; } } This allows a delegate to be passed to the List.Sort method, like this: mylist.Sort(new DelegateToComparer<MyClass>( (x, y) => { return x.SomeProp.CompareTo(y.SomeProp); }); So the above delegate will throw a null reference exception for the x parameter, even though no elements of mylist are null. UPDATE: Yes I am absolutely sure that it is parameter x throwing the null reference exception! UPDATE: Instead of using the framework's List.Sort method, I tried a custom sort method (i.e. new BubbleSort().Sort(mylist)) and the problem went away. As I suspected, the List.Sort method passes null to the comparer for some reason.

• ### Template Sort In C++

##### - by wdow88
Hey all, I'm trying to write a sort function but am having trouble figuring out how to initialize a value, and making this function work as a generic template. The sort works by: Find a pair =(ii,jj)= with a minimum value = ii+jj = such at A[ii]A[jj] If such a pair exists, then swap A[ii] and A[jj] else break; The function I have written is as follows: template <typename T> void sort(T *A, int size) { T min =453; T temp=0; bool swapper = true; while(swapper) { swapper = false; int index1 = 0, index2 = 0; for (int ii = 0; ii < size-1; ii++){ for (int jj = ii + 1; jj < size; jj++){ if((min >= (A[ii]+A[jj])) && (A[ii] > A[jj])){ min = (A[ii]+A[jj]); index1 = ii; index2 = jj; swapper = true; } } } if (!swapper) return; else { temp = A[index1]; A[index1] = A[index2]; A[index2] = temp; sort(A,size); } } } This function will successfully sort an array of integers, but not an array of chars. I do not know how to properly initialize the min value for the start of the comparison. I tried initializing the value by simply adding the first two elements of the array together (min = A[0] + A[1]), but it looks to me like for this algorithm it will fail. I know this is sort of a strange type of sort, but it is practice for a test, so thanks for any input.

• ### How do I force folder view sort order to not ignore special characters?

##### - by Jason Hartley
I have many folders in my home directory that have names that begin with special characters such as _OLD_500GB_HD or !FolderIWantToSeeAtTheTop, but for some reason these folders are sorted according to their first alphanumeric character rather than the leading special character. So how can I force the folder to not ignore the special character, or how else can I make the sort view organize certain folders at the top or bottom of the sort? Thanks.

• ### How do I sort by human readable sizes numerically?

for example I have command that shows how much space folder takes du folder | sort -n it works great, however I would like to have human readable form du -h folder however if I do that than I cannot sort it as numeric. How to join du folder and du -h folder to see output sorted as du folder, but with first column from du -h folder P.S. this is just an example. this technique might be very useful for me (if its possible)

• ### How does Batcher Merge work at a high level?

##### - by Mike
I'm trying to grasp the concept of a Batcher Sort. However, most resources I've found online focus on proof entirely or on low-level pseudocode. Before I look at proofs, I'd like to understand how Batcher Sort works. Can someone give a high level overview of how Batcher Sort works(particularly the merge) without overly verbose pseudocode(I want to get the idea behind the Batcher Sort, not implement it)? Thanks!

• ### Java - Collections.sort() performance

##### - by msr
Hello, Im using Collections.sort() to sort a LinkedList whose elements implements Comparable interface, so they are sorted in a natural order. In the javadoc documentation its said this method uses mergesort algorithm wich has n*log(n) performance. My question is if there is a more efficient algorithm to sort my LinkedList? The size of that list could be very high and sort will be also very frequent. Thanks!

• ### Array.sort Sorting Stability in Different Browsers

##### - by Boushley
What is the stability of Array.sort in different browsers. I know that the ECMA Script specification does not specify which algorithm to use, nor does it specify whether the sort should be stable. I've found this information on for Firefox https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Global_Objects/Array/sort which specifies that firefox uses a stable sort. Does anyone know about IE 6/7/8, Chrome, Safari?

• ### ICollectionView.SortDescriptions sort does not work if underlying DataTable has zero rows

##### - by BigBlondeViking
We have a WPF app that has a DataGrid inside a ListView. private DataTable table_; We do a bunch or dynamic column generation ( depending on the report we are showing ) We then do the a query and fill the DataTable row by row, this query may or may not have data.( not the problem, an empty grid is expected ) We set the ListView's ItemsSource to the DefaultView of the DataTable. lv.ItemsSource = table_.DefaultView; We then (looking at the user's pass usage of the app, set the sort on the column) Sort Method below: private void Sort(string sortBy, ListSortDirection direction) { ICollectionView dataView = CollectionViewSource.GetDefaultView(lv.ItemsSource); dataView.SortDescriptions.Clear(); var sd = new SortDescription(sortBy, direction); dataView.SortDescriptions.Add(sd); dataView.Refresh(); } In the Zero DataTable rows scenario, the sort does not "hold"? and if we dynamically add rows they will not be in sorted order. If the DataTable has at-least 1 row when the sort is applied, and we dynamically add rows to the DataTable, the rows com in sorted correctly. I have built a standalone app that replicate this... It is an annoyance and I can add a check to see if the DataTable was empty, and re-apply the sort... Anyone know whats going on here, and am I doing something wrong? FYI: What we based this off if comes from the MSDN as well: http://msdn.microsoft.com/en-us/library/ms745786.aspx

• ### Sort on DataView does not work if DataTable has zero rows

##### - by BigBlondeViking
We have a WPF app that has a DataGrid insode a ListView. private DataTable table_; We do a bunch or dynamic column generation ( depending on the report we are showing ) We then do the a query and fill the DataTable row by row, this query may or may not have data.( not the problem, an empty grid is expected ) We set the ListView's ItemsSource to the DefaultView of the DataTable. lv.ItemsSource = table_.DefaultView; We then (looking at the user's pass usage of the app, set the sort on the column) Sort Method below: private void Sort(string sortBy, ListSortDirection direction) { var dataView = CollectionViewSource.GetDefaultView(lv.ItemsSource); dataView.SortDescriptions.Clear(); var sd = new SortDescription(sortBy, direction); dataView.SortDescriptions.Add(sd); dataView.Refresh(); } In the Zero DataTable rows scenario, the sort does not "hold"? and if we dynamically add rows they will not be in sorted order. If the DataTable has at-least 1 row when the sort is applied, and we dynamically add rows to the DataTable, the rows com in sorted correctly. I have built a standalone app that replicate this... It is an annoyance and I can add a check to see if the DataTable was empty, and re-sort... Anyone know whats going on here, and am I doing something wrong? FYI: What we based this off if comes from the MSDN as well: http://msdn.microsoft.com/en-us/library/ms745786.aspx

• ### Why does the Java Collections Framework offer two different ways to sort?

##### - by dvanaria
If I have a list of elements I would like to sort, Java offers two ways to go about this. For example, lets say I have a list of Movie objects and I’d like to sort them by title. One way I could do this is by calling the one-argument version of the static java.util.Collections.sort( ) method with my movie list as the single argument. So I would call Collections.sort(myMovieList). In order for this to work, the Movie class would have to be declared to implement the java.lang.Comparable interface, and the required method compareTo( ) would have to be implemented inside this class. Another way to sort is by calling the two-argument version of the static java.util.Collections.sort( ) method with the movie list and a java.util.Comparator object as it’s arguments. I would call Collections.sort(myMovieList, titleComparator). In this case, the Movie class wouldn’t implement the Comparable interface. Instead, inside the main class that builds and maintains the movie list itself, I would create an inner class that implements the java.util.Comparator interface, and implement the one required method compare( ). Then I'd create an instance of this class and call the two-argument version of sort( ). The benefit of this second method is you can create an unlimited number of these inner class Comparators, so you can sort a list of objects in different ways. In the example above, you could have another Comparator to sort by the year a movie was made, for example. My question is, why bother to learn both ways to sort in Java, when the two-argument version of Collections.sort( ) does everything the first one-argument version does, but with the added benefit of being able to sort the list’s elements based on several different criteria? It would be one less thing to have to keep in your mind while coding. You’d have one basic mechanism of sorting lists in Java to know.

• ### Sorting Scientific Number With Unix Sort

##### - by neversaint
I tried to sort these number with Unix sort, but it doesn't seem to work: 2e-13 1e-91 2e-13 1e-104 3e-19 9e-99 This is my command: sort -nr file.txt What's the right way to do it?

• ### Radix Sort in Python [on hold]

##### - by Steven Ramsey
I could use some help. How would you write a program in python that implements a radix sort? Here is some info: A radix sort for base 10 integers is a based on sorting punch cards, but it turns out the sort is very ecient. The sort utilizes a main bin and 10 digit bins. Each bin acts like a queue and maintains its values in the order they arrive. The algorithm begins by placing each number in the main bin. Then it considers the ones digit for each value. The rst value is removed and placed in the digit bin corresponding to the ones digit. For example, 534 is placed in digit bin 4 and 662 is placed in the digit bin 2. Once all the values in the main bin are placed in the corresponding digit bin for ones, the values are collected from bin 0 to bin 9 (in that order) and placed back in the main bin. The process continues with the tens digit, the hundreds, and so on. After the last digit is processed, the main bin contains the values in order. Use randint, found in random, to create random integers from 1 to 100000. Use a list comphrension to create a list of varying sizes (10, 100, 1000, 10000, etc.). To use indexing to access the digits rst convert the integer to a string. For this sort to work, all numbers must have the same number of digits. To zero pad integers with leading zeros, use the string method str.zfill(). Once main bin is sorted, convert the strings back to integers. I'm not sure how to start this, Any help is appreciated. Thank you.