Search Results

Search found 79 results on 4 pages for 'unsorted'.

Page 2/4 | < Previous Page | 1 2 3 4  | Next Page >

• joining text files with 600M+ lines

  - by dnkb

  I have two files huge.txt and small.txt. Huge has around 600M rows and it's 14Gigs, each line has four space separated words (tokens) and finally another space separated column with a number. Small has 150K rows with a size of ~3M, a space separated word and a number. Both Files are sorted using the sort command, with no extra options. The words in both files may include apostrophes (') and dashes (-). The deisred output would contain all columns from the huge.txt and the second column (the number) from small txt where the first word of huge.txt and the first word of small.txt match. My attemtpts below failed miserably with the following error: cat huge.txt|join -o 1.1 1.2 1.3 1.4 2.2 - small.txt > output.txt join: memory exhausted What I suspect is that the sorting order isn't right somehow even though the files are pre-sorted using: sort -k1 huge.unsorted.txt > huge.txt sort -k1 small.unsorted.txt > small.txt Problems seem to appear around words that have apostrophes (') or dashes (-). I also tried dictinoary sorting using the -d option bumping into the same error at the end. I see two ways out of this but don't know how to implement any of them. 1) Any tips how to sort the files in a way that the join command considers them to be sorted properly? 2) I was thinking of calculating MD5 or some other hashes of the strings to get rid of the apostrophes and dashes, and do the sorting and joining with the hashes instead of the strings themselves an dat the "translate" back the hashes to strings, but leave the numbers intact at the end of the lines. Since there would be only 150K hashes it's not that bad. What would be a good way to calculate individual hashes for each of the strings? Some AWK magic? See file samples at the end. Thank you! sample of huge.txt had stirred me to 46 had stirred my corruption 57 had stirred old emotions 55 had stirred something in 69 had stirred something within 40 sample of small.txt caley 114881 calf 2757974 calfed 137861 calfee 71143 calflora 154624 calfskin 148347 calgary 9416465 calgon's 94846

  Read the article

• Best Upper Bound & Best Lower Bound of an Algorithm

  - by Nayefc

  I am studying for a final exam and I came past a question I had on an earlier test. The questions asks us to find the minimum value in an unsorted array of integers. We must provide the best upper bound and the best lower bound that you can for the problem in the worst case. First, in such an example, the upper and lower bound are the same (hence, we can talk in terms of Big-Theta). In the worst case, we would have to go through the whole list as the minimum value would be at the end of the list. Therefore, the answer is Big-Theta(n). Is this a correct & good explanation?

  Read the article

• vb.net using SortedDictionary as combobox datasource

  - by user228058

  I have a combobox which i am binding to a sortedDictionary list, so it displays in ascending order. My question is, I need to display "--Select--" as the first option. Is there any way to either: 1) add another item besides for the datasource or 2) add an unsorted item to the top of the sortedDictionary any other ideas welcome as well :) TIA

  Read the article

• Hadooop map reduce

  - by Aina Ari

  Im very much new to map reduce and i completed hadoop wordcount example. In that example it produces unsorted file (with key value) of word counts. So is it possible to make it sorted according to the most number of word occurrences by combining another map reduce task to the earlier one. Thanks in Advance

  Read the article

• Running time for Dijkstra's algorithm on a priority queue implemented by sorted list/array

  - by jay

  So I'm curious to know what the running time for the algorithm is on on priority queue implemented by a sorted list/array. I know for an unsorted list/array it is O((n^2+m)) where n is the number of vertices and m the number of edges. Thus that equates to O(n^2) time. But would it be faster if i used an sorted list/array...What would the running time be? I know extractmin would be constant time.

  Read the article

• find all combinations of elements for the given number N (sum upto N)

  - by webjockey

  int array [] = {1,2,3,4,5,6,7,8,9} N = 10 1,2,3,4 = 10 2,3,5 = 10 3,7 = 10 1,4,5 = 10 1,3,6 = 10 8,2 = 10 9,1 = 10 4,6 = 10 5,2,3 = 10 ... the function should return all combinations, the array may be unsorted

  Read the article

• Perl, time efficient hash

  - by Mike

  Is it possible to use a Perl hash in a manner that has O(log(n)) lookup and insertion? By default, I assume the lookup is O(n) since it's represented by an unsorted list. I know I could create a data structure to satisfy this (ie, a tree, etc) however, it would be nicer if it was built in and could be used as a normal hash (ie, with %)

  Read the article

• Need an algorithm for this problem

  - by Heisenburgor

  There are two integer sequences A[] and B[] of length N,both unsorted. Requirement: through the swapping of elements between A[] and B[], make the difference between {the sum of all elements in A[]} and {the sum of all elements in B[]} to be minimum. Many thanks

  Read the article

• Decent bookmark manager/tool for Firefox.

  - by ProfKaos

  The built in bookmarks UX for Firefox is dismall. How do I bookmark a page without opening the whole shebang and shoosing a bookmark folder? I can simply 'star' the page, but then it ends up in Unsorted Bookmarks. I can move a bookmark folder to the bookmark toolbar, where I have instant access to all bookmarks in that folder, but I can no longer bookmark a page in that folder in the normal way, because when I have to click the damned bookmark folder icon and manually type in the URL and title. What add-ins are there that can make bookmarking in Firefox humanly sane?

  Read the article

• Are Oracle Database CPU license limits enforced by software, and how do I check them?

  - by DrStalker

  I've inherited a windows VM running Oracle Database 10g. Currently the VM has only one CPU assigned to it, but I can boost this up to 4 with our VMWare licenses. What I'm not yet certain about is if the Oracle Software will get upset. Are Oracle DB CPU limits enforced by software, and if so how do I find out what they? If it's just a legal enforcement I'll hunt through the mass of unsorted paperwork I have left from previous managers to find what we're licensed for, but a quick software check would be nice.

  Read the article

• JAVA BubbleSort Output Plotting

  - by John Smith

  I'm not sure how to plot the output I get with my run time results for BubbleSort. Here's the thing: I've written a working BubbleSort algorithm that does exactly as it should. But I wish to plot the output, to show the following: Best Case, Worst Case, Average Case ... How would I go about plotting it on a graph? Here is the code: public class BubbleSort { static double bestTime = 10000000, worstTime = 0; public static void main(String[] args) { int BubArray[] = new int[]{13981, 6793, 2662, 10986, 733, ... #1000 integers}; System.out.println("Unsorted List Before Bubble Sort"); for(int a = 0; a < BubArray.length; a++){ System.out.print(BubArray[a] + " "); } System.out.println("\n Bubble Sort Execution ..."); for(int i=0; i<10000;i++) { bubbleSortTimeTaken(BubArray, i); } int itrs = bubbleSort(BubArray); System.out.println(""); System.out.println("Array After Bubble Sort"); System.out.println("Moves Taken for Sort : " + itrs + " Moves."); System.out.println("BestTime: " + bestTime + " WorstTime: " + worstTime); System.out.print("Sorted Array: \n"); for(int a = 0; a < BubArray.length; a++){ System.out.print(BubArray[a] + " "); } } private static int bubbleSort(int[] BubArray) { int z = BubArray.length; int temp = 0; int itrs = 0; for(int a = 0; a < z; a++){ for(int x=1; x < (z-a); x++){ if(BubArray[x-1] > BubArray[x]){ temp = BubArray[x-1]; BubArray[x-1] = BubArray[x]; BubArray[x] = temp; } itrs++; } } return itrs; } public static void bubbleSortTimeTaken(int[] BubArray, int n) { long startTime = System.nanoTime(); bubbleSort(BubArray); double timeTaken = (System.nanoTime() - startTime)/1000000d; if (timeTaken > 0) { worstTime = timeTaken; } else if (timeTaken < bestTime) { bestTime = timeTaken; } System.out.println(n + "," + timeTaken); } } The output are as the following ( execution number, time (nano/10^6): Unsorted List Before Bubble Sort 13981 6793 2662 .... #1000 integers Bubble Sort Execution ... 0, 18.319891 1, 4.728978 2, 3.670697 3, 3.648922 4, 4.161576 5, 3.824369 .... 9995, 4.331423 9996, 3.692473 9997, 3.709893 9998, 6.16055 9999, 4.32209 Array After Bubble Sort Moves Taken for Sort : 541320 Moves. BestTime: 1.0E7 WorstTime: 4.32209 Sorted Array: 10 11 17 24 57 60 83 128 141 145 ... #1000 integers I am looking for graphs to represent Average, Best and Worst case based on the output but my current graphs don't look correct. Any help would be appreciated, thanks.

  Read the article

• CodePlex Daily Summary for Monday, July 02, 2012

  CodePlex Daily Summary for Monday, July 02, 2012Popular ReleasesDynamicToSql: DynamicToSql 1.0.0 (beta): 1.0.0 beta versionCommonLibrary.NET: CommonLibrary.NET 0.9.8.5 - Final Release: A collection of very reusable code and components in C# 4.0 ranging from ActiveRecord, Csv, Command Line Parsing, Configuration, Holiday Calendars, Logging, Authentication, and much more. FluentscriptCommonLibrary.NET 0.9.8 contains a scripting language called FluentScript. Releases notes for FluentScript located at http://fluentscript.codeplex.com/wikipage?action=Edit&title=Release%20Notes&referringTitle=Documentation Fluentscript - 0.9.8.5 - Final ReleaseApplication: FluentScript Versio...SharePoint 2010 Metro UI: SharePoint 2010 Metro UI8: Please review the documentation link for how to install. Installation takes some basic knowledge of how to upload and edit SharePoint Artifact files. Please view the discussions tab for ongoing FAQsKwCombinatorics - Pick-Combination, Permutation, Cartesian Product classes in C#: KwCombinatorics library v2.4.0: Version 2.4.0 Optimized Combination.Rank setter. Optimized Multicombination.Rank setter. Added methods Combinatoric.BinomialCoefficient, Combinatoric.Factorial. Version 2.3.0 Added Permutation.Backtrack method. Added N-Queens example programs. Multicombination ranking constructor accepts unsorted data. Combination ranking constructor accepts unsorted data. Fixed numeric overflow bug in Combination.Rank setter. Fixed missing numeric overflow checks in Product constructors. F...Back-Propagation Neural Networks Simulation: Back-Propagation Neural Networks Simulation: This is the first release application for Back-Propagation Neural Networks Simulation. It is required .NET Framework 4.0. Check this to use http://backpronn.codeplex.comnopCommerce. Open source shopping cart (ASP.NET MVC): nopcommerce 2.60: Highlight features & improvements: • Significant performance optimization. • Use AJAX for adding products to the cart. • New flyout mini-shopping cart. • Auto complete suggestions for product searching. • Full-Text support. • EU cookie law support. To see the full list of fixes and changes please visit the release notes page (http://www.nopCommerce.com/releasenotes.aspx).THE NVL Maker: The NVL Maker Ver 3.51: http://download.codeplex.com/Download?ProjectName=nvlmaker&DownloadId=371510 ????：http://115.com/file/beoef05k#THE-NVL-Maker-ver3.51-sim.7z ????：http://www.mediafire.com/file/6tqdwj9jr6eb9qj/THENVLMakerver3.51tra.7z ======================================== ???? ======================================== 3.51 beta ???： ·?????????????????????? ·?????????，?????????0，?????????????????????? ·??????????????????????????? ·?????????????TJS????（EXP??） ·??4:3???，???????????????，??????????? ·?????????...JavApi: JavApi 2012-07-01.13631: RELEASE NOTES JavApi 0.8 base release with some base classes of ported Java API, provided under Apache License 2.0. JavApi Common Codec is a JavApi based codec framework, ported form Apache Codec 1.4.0, provided under Apache License 2.0. JavApi Common Collections is a JavApi based collection framework, ported form Apache Collections 3.2.1, provided under Apache License 2.0. JavApi Common Compress is a JavApi based collection framework, ported form Apache Compress 1.1, provided under Apache L...????: ????2.0.3: 1、???????????。 2、????????。 3、????????????。 4、bug??，????。Apworks: Apworks (v2.5.4563.21309, 30JUN2012): Installation Prerequisites: 1. Microsoft .NET Framework 4.0 SP1 2. Microsoft Visual Studio 2010 SP1 3. Other required libraries & assemblies are now included in the installation package so no more prerequisites needed Functional Updates: 1. Refactor the identity field of the IEntity interface from 'Id' to 'ID' 2. Changed the MySql Storage to use the MySql NetConnector version 6.4.4. 3. Implemented the paging support for the repositories. 4. Added the Eager Loading Property specification t...AssaultCube Reloaded: 2.5 Intrepid: Linux has Ubuntu 11.10 32-bit precompiled binaries and Ubuntu 10.10 64-bit precompiled binaries, but you can compile your own as it also contains the source. If you are using Mac or other operating systems, download the Linux package. Try to compile it. If it fails, download a virtual machine. The server pack is ready for both Windows and Linux, but you might need to compile your own for Linux (source included) You should delete /home/config/saved.cfg to reset binds/other stuff If you us...Magelia WebStore Open-source Ecommerce software: Magelia WebStore 2.0: User Right Licensing ContentType version 2.0.267.1Designing Windows 8 Applications with C# and XAML: Chapters 1 - 7 Release Preview: Source code for all examples from Chapters 1 - 7 for the Release PreviewMicrosoft Ajax Minifier: Microsoft Ajax Minifier 4.57: Fix for issue #18284: evaluating literal expressions in the pattern c1 * (x / c2) where c1/c2 is an integer value (as opposed to c2/c1 being the integer) caused the expression to be destroyed.Visual Studio ALM Quick Reference Guidance: v2 - Visual Studio 2010 (Japanese): Rex Tang (?? ??) http://blogs.msdn.com/b/willy-peter_schaub/archive/2011/12/08/introducing-the-visual-studio-alm-rangers-rex-tang.aspx, Takaho Yamaguchi (?? ??), Masashi Fujiwara (?? ??), localized and reviewed the Quick Reference Guidance for the Japanese communities, based on http://vsarquickguide.codeplex.com/releases/view/52402. The Japanese guidance is available in AllGuides and Everything packages. The AllGuides package contains guidances in PDF file format, while the Everything packag...Visual Studio Team Foundation Server Branching and Merging Guide: v1 - Visual Studio 2010 (Japanese): Rex Tang (?? ??) http://blogs.msdn.com/b/willy-peter_schaub/archive/2011/12/08/introducing-the-visual-studio-alm-rangers-rex-tang.aspx, Takaho Yamaguchi (?? ??), Hirokazu Higashino (?? ??), localized and reviewed the Branching Guidance for the Japanese communities, based on http://vsarbranchingguide.codeplex.com/releases/view/38849. The Japanese guidance is available in AllGuides and Everything packages. The AllGuides package contains guidances in PDF file format, while the Everything packag...SQL Server FineBuild: Version 3.1.0: Top SQL Server FineBuild Version 3.1.0This is the stable version of FineBuild for SQL Server 2012, 2008 R2, 2008 and 2005 Documentation FineBuild Wiki containing details of the FineBuild process Known Issues Limitations with this release FineBuild V3.1.0 Release Contents List of changes included in this release Please DonateFineBuild is free, but please donate what you think FineBuild is worth as everything goes to charity. Tearfund is one of the UK's leading relief and de...EasySL: RapidSL V2: Rewrite RapidSL UI Framework, Using Silverlight 5.0 EF4.1 Code First Ria Service SP2 + Lastest Silverlight Toolkit.SOLID by example: All examples: All solid examplesSiteMap Editor for Microsoft Dynamics CRM 2011: SiteMap Editor (1.1.1726.406): Use of new version of connection controls for a full support of OSDP authentication mechanism for CRM Online.New ProjectsBack-Propagation Neural Networks Simulation: This is simple Back-Propagation Neural Network simulation using C#. This code is a part of my "Supervised Neural Network" book written in 2006.D3API.Net: Diablo 3 API Wrapper for .NET developersEIRENE: UnknownEnterprise Library 5 Caching with ProtoBuf.NET: Implementation of Enterprise Library 5 Caching using ProtoBuf.NET Isolated Storage Backing StoreField Modeler 2012: Field Modeler 2012 was designed to allow introductory and advanced undergraduate students to get a ‘feel’ for the nature of the electromagnetic field.Fill Disk Public: Fill Disk Public is a program which be used to fill fixed hard disks by dummy temporary files. The powerful tool is easy to fill/clean disks. FluffyCloud: Diskusní server pro ceskou furry komunitu.FusionUI: ASP.NET MVC user interface frameworkHexa Question Engine: The Hexa Question Engine is the free solution for companies and persons for gathering information from his customers. We provide a solution with the latest technology and continuous development by the best team of professionals.hybgpx: One Test ProjectiBoxDB: iBoxDB is a small&smart embedded database, supports .NET4 WindowsPhone. ( OODB , NoSQL , Pure C#, WP7)IBR.StringResourceBuilder: The String Resource Builder is a Visual Studio (VS) extension to extract string literals (C#, VB.NET) from source code into resource files (ResX).iTuanju: This project is just a demo and temporary location for files. MVC Ajax Controls (MvcAjaxControls): The MvcAjaxControls project provides a set of html and javascript helpers for adding Ajax functionality to ASP.NET MVC applications.Niko Mix: Just to learn smthingPowerRedis: This project is to access a Redis server via powershell. It’s basically a wrapper around the awesome ServiceStack C# library from servicestack.org.sample1: aspSharePoint 2010 Metro UI: Need a Windows 8 Metro style UI landing page? SharePoint 2010 Metro Masterpage and Css!Source Control Selector: This project aims to address a very basic problem of developers using Visual Studio: Forcing VS to select the correct Source Control Provider.Vitual DJ Mayhem Modules: This project is an add on for Project Mayhem that allows users to control Virtual DJ through the reactionsWPFHelperTools: when test application ,we need to copy test files, if have lots of file ,this is not a good work. YiHaoDian .NET Sdk: ???SDK

  Read the article

• Space-efficient data structures for broad-phase collision detection

  - by Marian Ivanov

  As far as I know, these are three types of data structures that can be used for collision detection broadphase: Unsorted arrays: Check every object againist every object - O(n^2) time; O(log n) space. It's so slow, it's useless if n isn't really small. for (i=1;i<objects;i++){ for(j=0;j<i;j++) narrowPhase(i,j); }; Sorted arrays: Sort the objects, so that you get O(n^(2-1/k)) for k dimensions O(n^1.5) for 2d and O(n^1.67) for 3d and O(n) space. Assuming the space is 2D and sortedArray is sorted so that if the object begins in sortedArray[i] and another object ends at sortedArray[i-1]; they don't collide Heaps of stacks: Divide the objects between a heap of stacks, so that you only have to check the bucket, its children and its parents - O(n log n) time, but O(n^2) space. This is probably the most frequently used approach. Is there a way of having O(n log n) time with less space? When is it more efficient to use sorted arrays over heaps and vice versa?

  Read the article

• Sorting Algorithms

  - by MarkPearl

  General Every time I go back to university I find myself wading through sorting algorithms and their implementation in C++. Up to now I haven’t really appreciated their true value. However as I discovered this last week with Dictionaries in C# – having a knowledge of some basic programming principles can greatly improve the performance of a system and make one think twice about how to tackle a problem. I’m going to cover briefly in this post the following: Selection Sort Insertion Sort Shellsort Quicksort Mergesort Heapsort (not complete) Selection Sort Array based selection sort is a simple approach to sorting an unsorted array. Simply put, it repeats two basic steps to achieve a sorted collection. It starts with a collection of data and repeatedly parses it, each time sorting out one element and reducing the size of the next iteration of parsed data by one. So the first iteration would go something like this… Go through the entire array of data and find the lowest value Place the value at the front of the array The second iteration would go something like this… Go through the array from position two (position one has already been sorted with the smallest value) and find the next lowest value in the array. Place the value at the second position in the array This process would be completed until the entire array had been sorted. A positive about selection sort is that it does not make many item movements. In fact, in a worst case scenario every items is only moved once. Selection sort is however a comparison intensive sort. If you had 10 items in a collection, just to parse the collection you would have 10+9+8+7+6+5+4+3+2=54 comparisons to sort regardless of how sorted the collection was to start with. If you think about it, if you applied selection sort to a collection already sorted, you would still perform relatively the same number of iterations as if it was not sorted at all. Many of the following algorithms try and reduce the number of comparisons if the list is already sorted – leaving one with a best case and worst case scenario for comparisons. Likewise different approaches have different levels of item movement. Depending on what is more expensive, one may give priority to one approach compared to another based on what is more expensive, a comparison or a item move. Insertion Sort Insertion sort tries to reduce the number of key comparisons it performs compared to selection sort by not “doing anything” if things are sorted. Assume you had an collection of numbers in the following order… 10 18 25 30 23 17 45 35 There are 8 elements in the list. If we were to start at the front of the list – 10 18 25 & 30 are already sorted. Element 5 (23) however is smaller than element 4 (30) and so needs to be repositioned. We do this by copying the value at element 5 to a temporary holder, and then begin shifting the elements before it up one. So… Element 5 would be copied to a temporary holder 10 18 25 30 23 17 45 35 – T 23 Element 4 would shift to Element 5 10 18 25 30 30 17 45 35 – T 23 Element 3 would shift to Element 4 10 18 25 25 30 17 45 35 – T 23 Element 2 (18) is smaller than the temporary holder so we put the temporary holder value into Element 3. 10 18 23 25 30 17 45 35 – T 23   We now have a sorted list up to element 6. And so we would repeat the same process by moving element 6 to a temporary value and then shifting everything up by one from element 2 to element 5. As you can see, one major setback for this technique is the shifting values up one – this is because up to now we have been considering the collection to be an array. If however the collection was a linked list, we would not need to shift values up, but merely remove the link from the unsorted value and “reinsert” it in a sorted position. Which would reduce the number of transactions performed on the collection. So.. Insertion sort seems to perform better than selection sort – however an implementation is slightly more complicated. This is typical with most sorting algorithms – generally, greater performance leads to greater complexity. Also, insertion sort performs better if a collection of data is already sorted. If for instance you were handed a sorted collection of size n, then only n number of comparisons would need to be performed to verify that it is sorted. It’s important to note that insertion sort (array based) performs a number item moves – every time an item is “out of place” several items before it get shifted up. Shellsort – Diminishing Increment Sort So up to now we have covered Selection Sort & Insertion Sort. Selection Sort makes many comparisons and insertion sort (with an array) has the potential of making many item movements. Shellsort is an approach that takes the normal insertion sort and tries to reduce the number of item movements. In Shellsort, elements in a collection are viewed as sub-collections of a particular size. Each sub-collection is sorted so that the elements that are far apart move closer to their final position. Suppose we had a collection of 15 elements… 10 20 15 45 36 48 7 60 18 50 2 19 43 30 55 First we may view the collection as 7 sub-collections and sort each sublist, lets say at intervals of 7 10 60 55 – 20 18 – 15 50 – 45 2 – 36 19 – 48 43 – 7 30 10 55 60 – 18 20 – 15 50 – 2 45 – 19 36 – 43 48 – 7 30 (Sorted) We then sort each sublist at a smaller inter – lets say 4 10 55 60 18 – 20 15 50 2 – 45 19 36 43 – 48 7 30 10 18 55 60 – 2 15 20 50 – 19 36 43 45 – 7 30 48 (Sorted) We then sort elements at a distance of 1 (i.e. we apply a normal insertion sort) 10 18 55 60 2 15 20 50 19 36 43 45 7 30 48 2 7 10 15 18 19 20 30 36 43 45 48 50 55 (Sorted) The important thing with shellsort is deciding on the increment sequence of each sub-collection. From what I can tell, there isn’t any definitive method and depending on the order of your elements, different increment sequences may perform better than others. There are however certain increment sequences that you may want to avoid. An even based increment sequence (e.g. 2 4 8 16 32 …) should typically be avoided because it does not allow for even elements to be compared with odd elements until the final sort phase – which in a way would negate many of the benefits of using sub-collections. The performance on the number of comparisons and item movements of Shellsort is hard to determine, however it is considered to be considerably better than the normal insertion sort. Quicksort Quicksort uses a divide and conquer approach to sort a collection of items. The collection is divided into two sub-collections – and the two sub-collections are sorted and combined into one list in such a way that the combined list is sorted. The algorithm is in general pseudo code below… Divide the collection into two sub-collections Quicksort the lower sub-collection Quicksort the upper sub-collection Combine the lower & upper sub-collection together As hinted at above, quicksort uses recursion in its implementation. The real trick with quicksort is to get the lower and upper sub-collections to be of equal size. The size of a sub-collection is determined by what value the pivot is. Once a pivot is determined, one would partition to sub-collections and then repeat the process on each sub collection until you reach the base case. With quicksort, the work is done when dividing the sub-collections into lower & upper collections. The actual combining of the lower & upper sub-collections at the end is relatively simple since every element in the lower sub-collection is smaller than the smallest element in the upper sub-collection. Mergesort With quicksort, the average-case complexity was O(nlog2n) however the worst case complexity was still O(N*N). Mergesort improves on quicksort by always having a complexity of O(nlog2n) regardless of the best or worst case. So how does it do this? Mergesort makes use of the divide and conquer approach to partition a collection into two sub-collections. It then sorts each sub-collection and combines the sorted sub-collections into one sorted collection. The general algorithm for mergesort is as follows… Divide the collection into two sub-collections Mergesort the first sub-collection Mergesort the second sub-collection Merge the first sub-collection and the second sub-collection As you can see.. it still pretty much looks like quicksort – so lets see where it differs… Firstly, mergesort differs from quicksort in how it partitions the sub-collections. Instead of having a pivot – merge sort partitions each sub-collection based on size so that the first and second sub-collection of relatively the same size. This dividing keeps getting repeated until the sub-collections are the size of a single element. If a sub-collection is one element in size – it is now sorted! So the trick is how do we put all these sub-collections together so that they maintain their sorted order. Sorted sub-collections are merged into a sorted collection by comparing the elements of the sub-collection and then adjusting the sorted collection. Lets have a look at a few examples… Assume 2 sub-collections with 1 element each 10 & 20 Compare the first element of the first sub-collection with the first element of the second sub-collection. Take the smallest of the two and place it as the first element in the sorted collection. In this scenario 10 is smaller than 20 so 10 is taken from sub-collection 1 leaving that sub-collection empty, which means by default the next smallest element is in sub-collection 2 (20). So the sorted collection would be 10 20 Lets assume 2 sub-collections with 2 elements each 10 20 & 15 19 So… again we would Compare 10 with 15 – 10 is the winner so we add it to our sorted collection (10) leaving us with 20 & 15 19 Compare 20 with 15 – 15 is the winner so we add it to our sorted collection (10 15) leaving us with 20 & 19 Compare 20 with 19 – 19 is the winner so we add it to our sorted collection (10 15 19) leaving us with 20 & _ 20 is by default the winner so our sorted collection is 10 15 19 20. Make sense? Heapsort (still needs to be completed) So by now I am tired of sorting algorithms and trying to remember why they were so important. I think every year I go through this stuff I wonder to myself why are we made to learn about selection sort and insertion sort if they are so bad – why didn’t we just skip to Mergesort & Quicksort. I guess the only explanation I have for this is that sometimes you learn things so that you can implement them in future – and other times you learn things so that you know it isn’t the best way of implementing things and that you don’t need to implement it in future. Anyhow… luckily this is going to be the last one of my sorts for today. The first step in heapsort is to convert a collection of data into a heap. After the data is converted into a heap, sorting begins… So what is the definition of a heap? If we have to convert a collection of data into a heap, how do we know when it is a heap and when it is not? The definition of a heap is as follows: A heap is a list in which each element contains a key, such that the key in the element at position k in the list is at least as large as the key in the element at position 2k +1 (if it exists) and 2k + 2 (if it exists). Does that make sense? At first glance I’m thinking what the heck??? But then after re-reading my notes I see that we are doing something different – up to now we have really looked at data as an array or sequential collection of data that we need to sort – a heap represents data in a slightly different way – although the data is stored in a sequential collection, for a sequential collection of data to be in a valid heap – it is “semi sorted”. Let me try and explain a bit further with an example… Example 1 of Potential Heap Data Assume we had a collection of numbers as follows 1[1] 2[2] 3[3] 4[4] 5[5] 6[6] For this to be a valid heap element with value of 1 at position [1] needs to be greater or equal to the element at position [3] (2k +1) and position [4] (2k +2). So in the above example, the collection of numbers is not in a valid heap. Example 2 of Potential Heap Data Lets look at another collection of numbers as follows 6[1] 5[2] 4[3] 3[4] 2[5] 1[6] Is this a valid heap? Well… element with the value 6 at position 1 must be greater or equal to the element at position [3] and position [4]. Is 6 > 4 and 6 > 3? Yes it is. Lets look at element 5 as position 2. It must be greater than the values at [4] & [5]. Is 5 > 3 and 5 > 2? Yes it is. If you continued to examine this second collection of data you would find that it is in a valid heap based on the definition of a heap.

  Read the article

• Sorting eigenvectors by their eigenvalues (associated sorting)

  - by fbrereto

  I have an unsorted vector of eigenvalues and a related matrix of eigenvectors. I'd like to sort the columns of the matrix with respect to the sorted set of eigenvalues. (e.g., if eigenvalue[3] moves to eigenvalue[2], I want column 3 of the eigenvector matrix to move over to column 2.) I know I can sort the eigenvalues in O(N log N) via std::sort. Without rolling my own sorting algorithm, how do I make sure the matrix's columns (the associated eigenvectors) follow along with their eigenvalues as the latter are sorted?

  Read the article

• NSTableView setting the sort column?

  - by overcyn

  I have a NSTableView with multiple columns. clicking each of the columns sorts by the column like in iTunes. However when the tableview first loads the rows are unsorted and no tablecolumn is highlighted or displaying the up/down indicator image. I'm wondering if theres a simple way I can programmatically set the column the table is sorted by and set the indicator image on startup. The only solution I can think of is using [NSTableView setIndicatorImage: inTableColumn:] and [NSTableView setHighlightedColumn:], but that makes it so that clicking on the header doesnt highlight the column. I would rather not have to use tableView:mouseDownInHeaderOfTableColumn: and rewrite the whole click on header to sort thing.

  Read the article

• C++: A variation of priority queue

  - by Helltone

  I need some kind of priority queue to store pairs <key, value>. Values are unique, but keys aren't. I will be performing the following operations (most common first): random insertion; retrieving (and removing) all elements with the least key. random removal (by value); I can't use std::priority_queue because it only supports removing the head. For now, I'm using an unsorted std::list. Insertion is performed by just pushing new elements to the back (O(1)). Operation 2 sorts the list with std::sort (O(N*logN)), before performing the actual retrieval. Removal, however, is O(n), which is a bit expensive. Any idea of a better data structure?

  Read the article

• What is the better approach to find if a given set is a perfect subset of a set - If given subset is

  - by Microkernel

  Hi guys, What is the best approach to find if a given set(unsorted) is a perfect subset of a main set. I got to do some validation in my program where I got to compare the clients request set with the registered internal capability set. I thought of doing by having internal capability set sorted(will not change once registered) and do Binary search for each element in the client's request set. Is it the best I could get? I suspected that there might be better approach. Any idea? Regards, Microkernel

  Read the article

• How to access fields in JSON object by index

  - by Stefan

  I know this isn't the best way to do it, but I have no other choice :( I have to access the items in JSONObject by their index. The standard way to access objects is to just wirte this[objectName] or this.objectName. I also found a method to get all the fields inside a json object: (for (var key in p) { if (p.hasOwnProperty(key)) { alert(key + " -> " + p[key]); } } (Soruce : Loop through Json object). However there is no way of accessing the JSONfields directly by a index. The only way I see right now, is to create an array, with the function above, get the fieldname by index and then get the value by fieldname. As far as I see it, the p (in our case the JSON file must be an iteratable array to, or else the foreach loop wouldn't work. How can I access this array directly? Or is it some kind of unsorted list? Regards, Stefan

  Read the article

• Get the corresponding row in the datatable from the selection in datagridview

  - by The King

  Hi All, I have a DataTable which is bound to datagridview (Winforms)... I use the following two lines to get the DataRow that is selected in the datagridview... int l_intSelectedRow = DataGridView1.SelectedRows[0].Index; DataRow l_drwSelectedRow = ControlGroupPostedItems.Tables["PostedItems"].Rows[l_intSelectedRow]; This works fine until the DataGridView is Sorted... When the gridview is sorted by the, I get the incorrect values (1st selection of the sorted view return 1st row of unsorted Table). How could I solve this... Is looping through the datatable the only way... Thank you.

  Read the article

• Secondary keys in a B-tree

  - by Phenom

  Let's say that there is a file that contains an unsorted list of student information, which includes a student ID number as well as other information. I want to make a program that retrieves student information based on student ID number. In order to make it efficient, I store the student IDs in a B-tree. So when I enter a student ID number, it searches the B-tree to see if its there or not. It also does one more thing. If it finds the student ID number, then it also returns where in the file that student's information is. This is the secondary key. The program uses this information to locate the rest of the student's information and prints it to screen. Can this be done? Is this how a b-tree works?

  Read the article

• Find a common element within N arrays

  - by kunjaan

  If I have N arrays, what is the best(Time complexity. Space is not important) way to find the common elements. You could just find 1 element and stop. Edit: The elements are all Numbers. Edit: These are unsorted. Please do not sort and scan. This is not a homework problem. Somebody asked me this question a long time ago. He was using a hash to solve the problem. I was thinking if SO has solved similar problems.

  Read the article

• How to get the right row in a sorted DataView?

  - by ZeissS

  Hi, I have a DataGrid containing a small table. Until now, I had a double click handler on this grid which iterated over all rows to find the selected one: DataTable table = (DataTable)this.dataGrid.DataSource; int selectedRow = -1; for (int i=0; i<table.Rows.Count; i++) if (this.dataGrid.IsSelected(i)) selectedRow = i; break; } if ( selectedRow != -1 ) { DataRow row = table.Rows[selectedRow]; // More code ... } Problem: When the user clicks on a column header and sort the table, table.Rows does not return the right rows. It still contains the unsorted rows. How can I get the right column?

  Read the article

• C# 3.5 Merge 2 lists of 2 different types

  - by Ehsan

  I have 2 generic Lists List<type1> L1 , List<type2> L2 in C# 3.5 Problem: type1 has an attribute called "key1" and type2 has an attribute called "key2" How to merge L1 and L2 on key1 = key2. Both lists are unsorted but I'm welcome to any ideas on how to sort the lists based on the attribute. I'd like to be able to merge the two lists on a key. I know it's not a dictionary and it would've been nice if it was but there is a very specific reason why they are lists which I will not get in to because that is irrelevant.

  Read the article

• Assign parameters to function according to parameter names

  - by Korcholis

  I have an assoc array with a list of what are parameters to me. Here's an example: array( 'param1' => 'value1', 'param4' => 'value4', 'param3' => 'value3', 'param2' => 'value2', ); Note that they may come unsorted. Now, is there a way I can make a call (static or from an instance, using call_user_func_array or similar) and correctly pass each value to each parameter? Just to be sure, an example function I'd like to call using that parameter array is one such this: exampleFunction($param1, $param2, $param3, $param4) { ... } PS: Reflection is great, but I'm concerned about execution times (which, at least, in Java tends to increase a lot when using Reflection). If you know any other way to do so, it would be awesome.

  Read the article

< Previous Page | 1 2 3 4  | Next Page >