sorts

This is a discussion on sorts within the C++ Programming forums, part of the General Programming Boards category; I'm looking to review as many sort tutorials I can find. I'm familar with a few beginner level sorts. Please ...

  1. #1
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589

    sorts

    I'm looking to review as many sort tutorials I can find. I'm familar with a few beginner level sorts. Please post sites you have found on sorts. Thank you.
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  2. #2
    #include<xErath.h> xErath's Avatar
    Join Date
    Jun 2004
    Posts
    722
    http://en.wikipedia.org/wiki/Sort_algorithm

    and my favorite :: BogoSort!!!

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,546
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589
    question on the sorts.
    I'm looking to show the efficiency difference in the different sorts.
    I have taken the algorithms and placed them in my own Java program.
    http://thedigitalevolution.com/program4.txt
    I'm trying to place a counter in the different sorts to prove one is more efficient then the other. My results have been unexpected. My teacher said to place the counters in the locations were the comparisons are made. I did this, but it keeps giving me unexpected results. For instance lets look at the quick sort. The sorts work. So the code was transposed correctly.
    (1)Are the incrementations placed in the best logical location to track efficiency?
    This code is primarily non-language specific
    Code:
    	void QuickSort(int a[], int lo0, int hi0)
    	{
    		int lo = lo0;
    		int hi = hi0;
    		if (lo >= hi) 
    		{
    			return;
    		}
    		else if( lo == hi - 1 ) 
    		{			
    			if (a[lo] > a[hi]) 
    			{
    				int T = a[lo];
    				a[lo] = a[hi]; //I believe this should be 1 of 2 spots that increment
    				a[hi] = T;
    				comparison++;
    			}
    			return;
    		}
     
    		int pivot = a[(lo + hi) / 2];
    		a[(lo + hi) / 2] = a[hi];
    		a[hi] = pivot;
     
    		while( lo < hi ) 
    		{
    			while (a[lo] <= pivot && lo < hi) 
    			{	  //i do not believe this to be a valid increment
    				comparison++;
    				lo++;
    			}
    			while (pivot <= a[hi] && lo < hi ) 
    			{	 // i do not believe this is a valid increment
    				comparison++; 
    				hi--; 
    			}
    			if ( lo < hi )
    			{
    				int T = a[lo];
    				a[lo] = a[hi]; //this is 2 of 2 spots i feel should be incremented
    				a[hi] = T;
    				comparison++;
    			}
    		}
    		a[hi0] = a[hi];
    		a[hi] = pivot;
     
    		QuickSort(a, lo0, lo-1);
    		QuickSort(a, hi+1, hi0); 
    	}
    I thought the best location would be the swap location, and not the comparisons.
    The locations highlighted in red are compared shortly prior to the incrementation noted by green. The quick sort with using the comparisons type of tracking has in some cases shown me more comparisions then the other sorts. From the prior posted website I read that the quick sort is the fastest, therefore should always produce the smallest amount of comparisons? Is this a valid and logical thought?
    Last edited by xviddivxoggmp3; 10-17-2004 at 04:17 PM.
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I thought the best location would be the swap location, and not the comparisons.
    It depends on the metric you're testing. Both comparisons and swaps are important test measures for a sorting algorithm, and an inefficiency with one of them can result in using a quadratic sort instead of an nlogn sort because (for example) the nlogn sort performed too many swaps or too many comparisons and the items being sorted are compared very slowly or they are HUGE.
    My best code is written with the delete key.

  6. #6
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589
    Prelude,
    So you feel it is better to test for comparisons and swaps for a judge of efficiency.
    This sounds very logical to me.
    So given the code above would you say that if I was to check for comparisons only they are in the correct spots? the concern I have is that my attempt to place the incrementation in the actual test area has hailed. This makes the possibility that a false result on a test will not be regestered as a comparison. any suggestions to make sure the reading are as accurate as possible. on the if statements, i could place an else, but on the other loops i.e. do while, while, etc. if the comparison is false, it will not execute the loop, but will be an unrecorded comparisons.

    sorry about not having executable code for you to run, my work has issues with uploading files from their network. but if anyone has time, they could cut and paste the prior linked code.
    Last edited by xviddivxoggmp3; 10-17-2004 at 07:30 PM.
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. My bubble sort only sorts once
    By Muller in forum C Programming
    Replies: 8
    Last Post: 03-27-2009, 04:36 PM
  2. Replies: 22
    Last Post: 05-28-2008, 05:27 PM
  3. Simple Sorts Confuse ME =/
    By otchster in forum C Programming
    Replies: 5
    Last Post: 12-03-2005, 01:02 PM
  4. What is the best way to make a table of sorts.
    By Xenofizz in forum C++ Programming
    Replies: 9
    Last Post: 12-15-2003, 07:30 PM
  5. sorting of sorts....hehe
    By newbie2C++ in forum C++ Programming
    Replies: 2
    Last Post: 11-14-2001, 12:02 AM

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