Thread: Quicksort help!

  1. #16
    Registered User
    Join Date
    Sep 2006
    Quote Originally Posted by zeronero View Post
    No it doesn't have to be done before the bucketing and infact seem easier to do before! but how can I do that if i have millions of structs as struct obj arrayname[3000000] just seg faults when I run it?
    If you declare the array of structs before main(), it will be global in scope (which is generally bad, but useful here). Global scope gives your array access to MUCH more memory than a local array would have.


    You could malloc (or calloc) the array from the "heap". Local memory comes from the "stack" which is a small (1-3 MB usually) amount of memory set aside specifically for the function to use. The heap has a MUCH bigger amount of memory that you can draw from, AND it is global, so you can use it in a function, return the location (the address) of the array you malloc, and continue using it in any other function. Just don't lose the address of the array! (Easy to do since the name of the array is the address)

    Generally, if you need to sort a bunch of linked lists, you want to use Merge sort.

    A tiered sorting approach is quite quick for huge amounts of data. With the original bins being small compared to the size of the data. So you might have several thousands of them. I used Quicksort for the initial bin sorting, but you could use Merge sort, of course. Main thing is to use Merge sort for merging all the small bins (which are themselves already sorted), into a second tier of bins (files). Then the second tier of files are merged together, to create the sorted third tier. With every tier level, you cut the number of bins needed, in half, and double their size.

    One big advantage of this, is that after the first tier bins, you don't need an array or list, to hold the data for you. You sort right off the HD, with just a few variables. It gives the HD a workout, but a HD with a large buffer will help. An SSD drive will absolutely scream through this.

    The logic is fairly simple. You count the number of bins (files) you make, at each level, and name the files such that your program can find them: bin1, bin2, etc. I included a letter, like bin1A, where the A designated the tier level of the bin, but that was not needed, since every tier level is dealt with before the next tier level merging begins. Parallel processing may require such naming schemes, however.
    Last edited by Adak; 02-17-2012 at 05:53 PM.

  2. #17
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Quote Originally Posted by zeronero View Post
    Your code does not do any sorting though
    You said you already knew how to sort an array. I was simply showing you how to use a single number to represent a given element, regardless of where it is in a column or row. With that you can sort based on a single index number instead of a pair of them, by hiding that aspect of it.

    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. quicksort
    By thescratchy in forum C Programming
    Replies: 3
    Last Post: 03-15-2010, 12:44 PM
  2. Help with quicksort
    By c++prog in forum C++ Programming
    Replies: 12
    Last Post: 11-24-2009, 11:01 PM
  3. quicksort
    By WelshGrandSlam in forum C++ Programming
    Replies: 8
    Last Post: 01-23-2008, 08:15 PM
  4. Quicksort again
    By rvanbeusichem in forum C Programming
    Replies: 3
    Last Post: 11-25-2004, 04:32 AM
  5. quicksort
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 01-12-2002, 02:07 AM