Sorting algorithms, worst-case input

This is a discussion on Sorting algorithms, worst-case input within the C++ Programming forums, part of the General Programming Boards category; One good way to generate worst-case initial ordering is to use a genetic algorithm. Unlike brute-forcing, this can find an ...

  1. #16
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    One good way to generate worst-case initial ordering is to use a genetic algorithm. Unlike brute-forcing, this can find an answer for thousands of items.
    • Each individual is an initial order
    • The fitness function is a function of the number of swaps, compares, actual time taken to sort etc
    • Swap-over could consist of choosing a cut point and swapping the portion above that point
    • Mutations are a simple swap
    Of course the worst case for the algorithms you have to implement aren't that interesting. A genetic algorithm would be more suited to finding a very bad case for median-of-three QuickSort, or a variant of ShellSort etc.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  2. #17
    Registered User
    Join Date
    Dec 2007
    Posts
    53
    Another question regarding sorting algorithms.

    I've noticed that most minHeap implementations are maxHeap with the two inequality signs regarding tree items inversed, which makes sense and seems to work.

    Can somebody put into simple words why minHeap takes so much more time than maxHeap?

    EDIT: Nope, they take the same, as long as the functions are called the same way technically. And here's a question about something I was never told during the C++ course.

    Why is...
    Code:
    //
    // MinHeaps an array, supposed to be worst-case scenario for a HeapSort.
    //
    void minHeap(int a[], int N)
    {
    	for (int k = N/2; k > 0; k--) {
    		upHeap(a, k, N);
    	}
    }
    
    void upHeap(int a[], int k, int N)
    {
    	int T = a[k - 1];
    	while (k <= N/2) { 
    		int j = k + k;
    
    		if ((j < N) && (a[j - 1] > a[j])) { 
    			j++;
    		}
    		if (T <= a[j - 1]) {
    			break;
    		} else { 
    			a[k - 1] = a[j - 1];
    			k = j;
    		}
    	}
    	a[k - 1] = T;
    }
    ...a gazillion times faster than...

    Code:
    void minHeap(int a[], int N)
    {
    	for (int k = N/2; k > 0; k--) {
    		int T = a[k - 1];
    		while (k <= N/2) { 
    			int j = k + k;
    
    			if ((j < N) && (a[j - 1] > a[j])) { 
    				j++;
    			}
    			if (T <= a[j - 1]) {
    				break;
    			} else { 
    				a[k - 1] = a[j - 1];
    				k = j;
    			}
    		}
    		a[k - 1] = T;
    	}
    }
    And yes, the only difference is that the first time whatever's inside the for loop is a separate function, the second time the function's code is copied into the for loop.
    Last edited by Leftos; 06-15-2009 at 10:22 AM.

  3. #18
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Are you sure they are being passed the same thing?
    I see no reason one would ever be slightly faster than the other, except by minor differences in the compiled code, that basically comes down to luck. For a different compiler, it may very well be the other way around, or they may be equal in speed.

    By the way, an already sorted array is a min-heap, so you could just use that as the worst case for HeapSort. Reverse sorted is correspondingly the best case.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. get keyboard and mouse events
    By ratte in forum Linux Programming
    Replies: 10
    Last Post: 11-17-2007, 05:42 PM
  2. Intel syntax on MinGW ?
    By TmX in forum Tech Board
    Replies: 2
    Last Post: 01-06-2007, 09:44 AM
  3. Keypress reading
    By geek@02 in forum Windows Programming
    Replies: 1
    Last Post: 06-16-2004, 01:16 PM
  4. error with code
    By duffy in forum C Programming
    Replies: 8
    Last Post: 10-22-2002, 10:45 PM
  5. Extra printed stmts...why?
    By mangoz in forum C Programming
    Replies: 4
    Last Post: 12-19-2001, 07:56 AM

Tags for this Thread


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