Sorting issue

This is a discussion on Sorting issue within the C++ Programming forums, part of the General Programming Boards category; Greetings to all. I am trying to make a quicksort that is faster than the qsort function from the library ...

  1. #1
    Registered User
    Join Date
    May 2011
    Posts
    1

    Sorting issue

    Greetings to all. I am trying to make a quicksort that is faster than the qsort function from the library . So far, I've come to discover that if I choose the pivot at the middle of the sorting vector, my qsort beats the library qsort, but this depends on the size of the vector. At 100k elements, it's ok, but at 1kk elements, from 100 test cases, the library beast my version 100-0.
    So the problem is at larger vectors, and in choosing the proper pivot. Can somebody please give me some hints? I would very much appreciate it.
    I can provide the code I have so far if it's needed.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,968
    Quote Originally Posted by Ssalty
    Greetings to all. I am trying to make a quicksort that is faster than the qsort function from the library . So far, I've come to discover that if I choose the pivot at the middle of the sorting vector, my qsort beats the library qsort, but this depends on the size of the vector. At 100k elements, it's ok, but at 1kk elements, from 100 test cases, the library beast my version 100-0.
    So the problem is at larger vectors, and in choosing the proper pivot. Can somebody please give me some hints? I would very much appreciate it.
    To even contemplate beating a standard library implementation, you probably should be well read enough to know of other pivot selection strategies, e.g., median of three and (pseudo-)random selection. Try them. However, you may find that what constitutes an improvement with larger ranges may result in a slight loss of performance with smaller ranges (e.g., when the range is sufficiently small, you may want to switch to say, insertion sort).

    Incidentally, since this is C++, note that we would more typically use std::sort instead of qsort.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. bandwidth issue / network issue with wireless device communication
    By vlrk in forum Networking/Device Communication
    Replies: 0
    Last Post: 07-05-2010, 11:52 PM
  2. asm issue
    By DRDOS in forum Tech Board
    Replies: 8
    Last Post: 07-04-2006, 11:15 AM
  3. dll issue
    By yahn in forum C++ Programming
    Replies: 1
    Last Post: 01-20-2006, 09:40 PM
  4. compare issue while sorting
    By Micko in forum C++ Programming
    Replies: 1
    Last Post: 03-06-2004, 09:34 AM
  5. Sorting words with a fast, effincient sorting method
    By Unregistered in forum C++ Programming
    Replies: 19
    Last Post: 07-12-2002, 04:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21