anybody have a generic algorith to quicksort a linked list?

Discussion in 'OT Technology' started by BaZ, Jul 9, 2003.

  1. BaZ

    BaZ 2004 ACC Champions

    Joined:
    Jun 12, 2001
    Messages:
    2,005
    Likes Received:
    0
    Location:
    Hokieville, USA
  2. SLED

    SLED build an idiot proof device and someone else will

    Joined:
    Sep 20, 2001
    Messages:
    28,118
    Likes Received:
    0
    Location:
    AZ, like a bauce!
    i don't have the code handy, but my favorite sorting method was the Shell Sort
     
  3. SLED

    SLED build an idiot proof device and someone else will

    Joined:
    Sep 20, 2001
    Messages:
    28,118
    Likes Received:
    0
    Location:
    AZ, like a bauce!
    here it is in java, should be easy to convert:

    Code:
    class ShellSortAlgorithm extends SortAlgorithm {
        void sort(int a[]) throws Exception {
    	int h = 1;
            /* 
             * find the largest h value possible 
             */
            while ((h * 3 + 1) < a.length) {
    	    h = 3 * h + 1;
    	}
    
            /* 
             * while h remains larger than 0 
             */
            while( h > 0 ) {
                /* 
                 * for each set of elements (there are h sets)
                 */
                for (int i = h - 1; i < a.length; i++) {
                    /* 
                     * pick the last element in the set
                     */
                    int B = a[i];
                    int j = i;
                    /*
                     * compare the element at B to the one before it in the set
                     * if they are out of order continue this loop, moving
                     * elements "back" to make room for B to be inserted.
                     */
                    for( j = i; (j >= h) && (a[j-h] > B); j -= h) {
                        if (stopRequested) {
    		        return;
                        }
                        a[j] = a[j-h];
    		    pause(i,j);
                    }
                    /*
                     *  insert B into the correct place
                     */
                    a[j] = B;
    	        pause(j);
                }
                /* 
                 * all sets h-sorted, now decrease set size
                 */
                h = h / 3;
            }
        }
    }
    
     
  4. SLED

    SLED build an idiot proof device and someone else will

    Joined:
    Sep 20, 2001
    Messages:
    28,118
    Likes Received:
    0
    Location:
    AZ, like a bauce!
    there is always the good 'ole quick sort too:

    Code:
    class QSortAlgorithm extends SortAlgorithm {
        void sort(int a[], int lo0, int hi0) throws Exception {
    	int lo = lo0;
    	int hi = hi0;
    	pause(lo, hi);
    	if (lo >= hi) {
    	    return;
    	}
            else if( lo == hi - 1 ) {
                /*
                 *  sort a two element list by swapping if necessary 
                 */
                if (a[lo] > a[hi]) {
                    int T = a[lo];
                    a[lo] = a[hi];
                    a[hi] = T;
                }
                return;
    	}
    
    
            /*
             *  Pick a pivot and move it out of the way
             */
    	int pivot = a[(lo + hi) / 2];
            a[(lo + hi) / 2] = a[hi];
            a[hi] = pivot;
    
            while( lo < hi ) {
                /*
                 *  Search forward from a[lo] until an element is found that
                 *  is greater than the pivot or lo >= hi 
                 */
                while (a[lo] <= pivot && lo < hi) {
    		lo++;
    	    }
    
                /*
                 *  Search backward from a[hi] until element is found that
                 *  is less than the pivot, or lo >= hi
                 */
    	    while (pivot <= a[hi] && lo < hi ) {
    		hi--;
    	    }
    
                /*
                 *  Swap elements a[lo] and a[hi]
                 */
                if( lo < hi ) {
                    int T = a[lo];
                    a[lo] = a[hi];
                    a[hi] = T;
                    pause();
                }
    
    	    if (stopRequested) {
                    return;
                }
    	}
    
            /*
             *  Put the median in the "center" of the list
             */
            a[hi0] = a[hi];
            a[hi] = pivot;
    
            /*
             *  Recursive calls, elements a[lo0] to a[lo-1] are less than or
             *  equal to pivot, elements a[hi+1] to a[hi0] are greater than
             *  pivot.
             */
    	sort(a, lo0, lo-1);
    	sort(a, hi+1, hi0);
        }
    
        void sort(int a[]) throws Exception {
    	sort(a, 0, a.length-1);
        }
    }
    
    
     
  5. BaZ

    BaZ 2004 ACC Champions

    Joined:
    Jun 12, 2001
    Messages:
    2,005
    Likes Received:
    0
    Location:
    Hokieville, USA
    i know the algorithm for quick sort, i was just wondering if anybody had altered it for quick sort. i tried overloading the bracket operators but that didnt work and was the only way i could think to do it
     
  6. BaZ

    BaZ 2004 ACC Champions

    Joined:
    Jun 12, 2001
    Messages:
    2,005
    Likes Received:
    0
    Location:
    Hokieville, USA
    i was able to get it to work, if anybody would like to see it
     

Share This Page