Programming Forums > Application Development > Software Design and Algorithms

Jimbo · Aug 24th, 2006, 4:35 PM

Ok, this should be manageable. Only 25 solutions needed... but there's a catch. It must be efficient (i.e. better than bubblesort) and you need to explain why or how it's efficient. Algorithms can be repeated, but only if you optimize better or differently (e.g. time vs. space) than a previous entry (you need to explain what you did better or differently). Post your language just so we can tell what it is.

I'll kick it off

1) MIPS 32 - Quicksort (comments are in C-ish pseudo-code)

(Toggle Plain Text)

.text
qsort: # performs quicksort on array at $a0, with length $a1
     addi $sp,$sp,-12    # allocate stack space
     sw   $ra,12($sp)  # save return address
     slti $t0,$a1,2      # if(len <= 1)
     bne  $t0,$0,$END    # jump to end (already sorted)
     addi $t0,$0,2
     bne  $t0,$a1,$Chuck # if(len==2) compare the 2
     lw   $t1,0($a0)     # load array[0]
     lw   $t2,4($a0)     # load array[1]
     slt  $t0,$t2,$t1    # if array[1] < array[0]
     beq  $t0,$0,$END
     sw   $t1,4($a0)     # swap array[0] and array[1]
     sw   $t2,0($a0)
     j    $END     # now we're done
$Chuck: # this is where the actual quicksort happens
     srl  $t0,$a1,1      # piv = len / 2
     sll  $t0,$t0,2      # align to word size
     add  $t0,$a0,$t0    # mem addr. of pivot
     lw   $t1,0($t0)     # $t1 = mem[piv]
     addi $t2,$a1,-1     # $t2 = len - 1;
     sll  $t2,$t2,2      # align to word size
     add  $t2,$a0,$t2    # mem addr. of end
     lw   $t3,0($t2)     # t3 = mem[end]
     sw   $t3,0($t0)     # swap pivot and end value
     sw   $t1,0($t2)
     # pivot value is in $t1
     add  $t5,$t2,$0     # j = piv - 1
     add  $t3,$a0,$0   # i = 0
     slt  $t7,$t3,$t5  # while(i < j)
     beq  $t7,$0,$Kick
$Norris: # while(array[i] < array[piv]) i++;
     lw   $t4,0($t3)
     slt  $t7,$t4,$t1    # if(array[i] < array[piv])
     beq  $t7,$0,$Round
     addi $t3,$t3,4      # move to next word
     j    $Norris
$Round: # while(array[j] > array[piv]) j--;
     lw   $t6,0($t5)
     slt  $t7,$t1,$t6    # if(array[j] > array[piv])
     beq  $t7,$0,$House
     addi $t5,$t5,-4     # move to next word
     j    $Round
$House: # if (i < j)
     slt  $t7,$t3,$t5
     beq  $t7,$0,$Kick
     sw   $t6,0($t3)   # swap(array[i],array[j])
     sw   $t4,0($t5)
     j    $Norris        # loop through again
$Kick: # now reset pivot and recurse
     lw   $t7,0($t3)   # $t7 = array[i]
     sw   $t1,0($t3)     # array[i] = array[piv]
     sw   $t7,0($t2)     # array[piv] = array[i]
     addi $t8,$t3,4      # address of [i+1] (for 2nd call)
     sw   $t8,4($sp)   # save to stack for later
     sub  $t9,$t3,$a0  # mem offset of i from $a0
     srl  $t9,$t9,2      # value of i
     sub  $t0,$a1,$t9    # len - i
     addi $t0,$t0,-1     # len - i - 1
     sw   $t0,8($sp)   # save to stack for later
     addi $a1,$t9,-1     # len = i-1 = j
     jal  qsort          # qsort(array,len)
     lw   $t8,4($sp)     # reload ptr to 2nd partition
     lw   $t9,8($sp)     # reload length of 2nd partition
     add  $a0,$t8,$0   # save to $a0
     add  $a1,$t9,$0   # save to $a1
     jal  qsort    # qsort(array+i+1,len-i-1)
$END:
     lw   $ra,12($sp)  # reload return address
     addi $sp,$sp,12   # deallocate stack space
     jr   $ra            # return from function

.text
qsort: # performs quicksort on array at $a0, with length $a1
     addi $sp,$sp,-12    # allocate stack space
     sw   $ra,12($sp)  # save return address
     slti $t0,$a1,2      # if(len <= 1)
     bne  $t0,$0,$END    # jump to end (already sorted)
     addi $t0,$0,2
     bne  $t0,$a1,$Chuck # if(len==2) compare the 2
     lw   $t1,0($a0)     # load array[0]
     lw   $t2,4($a0)     # load array[1]
     slt  $t0,$t2,$t1    # if array[1] < array[0]
     beq  $t0,$0,$END
     sw   $t1,4($a0)     # swap array[0] and array[1]
     sw   $t2,0($a0)
     j    $END     # now we're done
$Chuck: # this is where the actual quicksort happens
     srl  $t0,$a1,1      # piv = len / 2
     sll  $t0,$t0,2      # align to word size
     add  $t0,$a0,$t0    # mem addr. of pivot
     lw   $t1,0($t0)     # $t1 = mem[piv]
     addi $t2,$a1,-1     # $t2 = len - 1;
     sll  $t2,$t2,2      # align to word size
     add  $t2,$a0,$t2    # mem addr. of end
     lw   $t3,0($t2)     # t3 = mem[end]
     sw   $t3,0($t0)     # swap pivot and end value
     sw   $t1,0($t2)
     # pivot value is in $t1
     add  $t5,$t2,$0     # j = piv - 1
     add  $t3,$a0,$0   # i = 0
     slt  $t7,$t3,$t5  # while(i < j)
     beq  $t7,$0,$Kick
$Norris: # while(array[i] < array[piv]) i++;
     lw   $t4,0($t3)
     slt  $t7,$t4,$t1    # if(array[i] < array[piv])
     beq  $t7,$0,$Round
     addi $t3,$t3,4      # move to next word
     j    $Norris
$Round: # while(array[j] > array[piv]) j--;
     lw   $t6,0($t5)
     slt  $t7,$t1,$t6    # if(array[j] > array[piv])
     beq  $t7,$0,$House
     addi $t5,$t5,-4     # move to next word
     j    $Round
$House: # if (i < j)
     slt  $t7,$t3,$t5
     beq  $t7,$0,$Kick
     sw   $t6,0($t3)   # swap(array[i],array[j])
     sw   $t4,0($t5)
     j    $Norris        # loop through again
$Kick: # now reset pivot and recurse
     lw   $t7,0($t3)   # $t7 = array[i]
     sw   $t1,0($t3)     # array[i] = array[piv]
     sw   $t7,0($t2)     # array[piv] = array[i]
     addi $t8,$t3,4      # address of [i+1] (for 2nd call)
     sw   $t8,4($sp)   # save to stack for later
     sub  $t9,$t3,$a0  # mem offset of i from $a0
     srl  $t9,$t9,2      # value of i
     sub  $t0,$a1,$t9    # len - i
     addi $t0,$t0,-1     # len - i - 1
     sw   $t0,8($sp)   # save to stack for later
     addi $a1,$t9,-1     # len = i-1 = j
     jal  qsort          # qsort(array,len)
     lw   $t8,4($sp)     # reload ptr to 2nd partition
     lw   $t9,8($sp)     # reload length of 2nd partition
     add  $a0,$t8,$0   # save to $a0
     add  $a1,$t9,$0   # save to $a1
     jal  qsort    # qsort(array+i+1,len-i-1)
$END:
     lw   $ra,12($sp)  # reload return address
     addi $sp,$sp,12   # deallocate stack space
     jr   $ra            # return from function

Quicksort runs in O(n*log(n)) time on average (worst case is O(n^2)). Memory usage is simply the original array plus a some overhead per function call (which can add up, as it is recursive), which comes out to O(n) where n is the length of the array. This particular implementation uses all temporary registers (to reduce access to memory for variables), and 3 words of stack space per call.

glimmy · Aug 24th, 2006, 5:51 PM

Maybe this could help some people: http://en.wikipedia.org/wiki/Sorting...ing_algorithms

I will try to implement one when the storm here passes.

andro · Aug 24th, 2006, 7:32 PM

 cpp Syntax (Toggle Plain Text) 
#include <iostream>
#include <algorithm>
 
int main()
{
    int array[] = {9, 7, 5, 4, 1, 7, 3, 2, 8, 0};
    const int size = sizeof(array)/sizeof(int);
 
    std::sort(array, array+size);
 
    for (int i = 0; i < size; i++)
        std::cout << array[i];
 
    return 0;
}
#include <iostream>
#include <algorithm>

int main()
{
    int array[] = {9, 7, 5, 4, 1, 7, 3, 2, 8, 0};
    const int size = sizeof(array)/sizeof(int);

    std::sort(array, array+size);

    for (int i = 0; i < size; i++)
        std::cout << array[i];

    return 0;
}

O(n log N) - I think I read that std::sort uses introsort nowadays...

EDIT: did some reading, it looks like just the SGI C++ STL uses introsort, I guess the regular C++ STL still uses quicksort...

DaWei · Aug 24th, 2006, 7:52 PM

Introsort is a variant of quicksort. Maybe I'll do a heapsort. Maybe I'll go to the dentist, too, lol.

andro · Aug 24th, 2006, 8:52 PM

Oh, I thought it was the efficient parts of quicksort and heapsort combined.

DaWei · Aug 25th, 2006, 7:30 AM

I wasn't suggesting it wasn't a valid entry, just characterizing it.

glimmy · Aug 25th, 2006, 8:10 PM

3) Perl- Mergesort

(Toggle Plain Text)

sub merge {
	my ($left, $right) = @_; 
	my @merged;

	while ((scalar(@$left) > 0) && (scalar(@$right))) {

		if ($left->[0] <= $right->[0]) {
			push @merged, shift(@$left);
		} else {
			push @merged, shift(@$right);
		}
	}

	if (scalar(@$left) > 0) {
		push @merged, shift(@$left);
	}
	
	if (scalar(@$right) > 0) {
		push @merged, shift(@$right);
	}

	return @merged;
}
		 

sub mergesort {
	my @list = @_;
	my (@left,@right);


	if (scalar(@list) <= 1) {
		return @list;
	} else {

		my $middlin = scalar(@list) / 2;

		foreach (0..($middlin - 1)) {
			push @left, $list[$_];
		}

		foreach ($middlin..(scalar(@list) - 1)) {
			push @right, $list[$_];
		}

		@left = mergesort(@left);
		@right = mergesort(@right);

		return &merge(\@left,\@right);
	}
}

DaWei · Sep 13th, 2006, 12:30 PM

This is a heapsort. Rather than just pluck a function from the library and inexplicably illustrate the sort, I have implemented the sort. This approach uses an array representation for the tree. There are interesting things about the heapsort which aren't illustrated here, such as sorting in-place and the implications that has on the min/max nature of the heap. Google will be more than happy to satisfy your curiosity.

A heap may be either a min heap or a max heap. The requirements for a heap are that every parent is less (greater) than its children. The tree must also be complete; that is, every level is filled with the possible exception of the last, which is packed to the "left". The sort is accomplished by plucking out the root and placing it in the output list. It is then replaced by the most extreme element, which almost certainly breaks the heapness. The tree is then re-heaped and it's all done again. Obviously, the tree shrinks as the sort progresses. This storage may be used to accomplish the (quasi) in-place sort mentioned above. In re-heaping, one finds that only half the tree needs to be adjusted. Moving into this half, one finds that only half of the sub-hive needs to be adjusted. This is the "divide and conquer" approach that also makes sorts like quicksort effective.

As for time complexity, forming a heap from a wild tree requires, worst case, 3N comparisons. The sort, which requires re-heaping (quicker than the heapify), needs, worst case, Nlog(N) comparisons.

(Toggle Plain Text)

class Heap:
    
    def __init__ (I, theHeap = [], desc = False):
        '''
        Initializes a newly instantiated heap.  If data is passed
        in the tree will be heapified on construction.
        '''
        I.theHeap = theHeap
        I.nGoodies = len (theHeap)
        I.desc = desc
        if I.nGoodies > 0: I.heapify ()
        
    def theWinnah (I, a, b):
        '''
        Comparison function that adapts to whether or not the sort
        is ascending or descending.
        '''
        if I.desc == False: return (a < b)
        else: return (b <= a)
        
    def showHive (I):
        '''
        Arrange the tree in a visual hive.  The tree must have sixteen
        or fewer members.
        '''
        if I.nGoodies > 16: 
            print "Hive too large to show"
            return
        i = 0
        level = 0
        lineLength = 80
        while i < I.nGoodies:
            pcount = 2**level
            cellWidth = lineLength / pcount
            line = ""
            while pcount > 0:
                word = I.theHeap [i]
                line += word.center (cellWidth, ' ')
                pcount -= 1
                i += 1
                if i >= I.nGoodies: break
            print line
            level += 1
    
    def heapify (I, iParent = 0):
        '''
        This adjusts the tree so that it qualifies as a heap.  That is,
        it is a complete tree and any parent is smaller (larger, for
        descending sorts) than either of its children.  This is not as
        efficient as the reheap process, because the entire tree must
        be examined.
        '''
        if I.iLeft (iParent) < I.nGoodies:
            # Left child exists
            if I.iLeft (I.iLeft (iParent)) < I.nGoodies:
                # And has a child
                I.heapify (I.iLeft (iParent))
            if I.theWinnah (I.theHeap [I.iLeft (iParent)].lower (),
                            I.theHeap [iParent].lower ()):
                # Left child less (greater) than parent, 
                # swap and reaheapify the hive
                I.swap (iParent, I.iLeft (iParent))
                I.heapify (I.iLeft (iParent))
                #I.heapify (iParent)
        if I.iRight (iParent) < I.nGoodies:
            # Right child exists
            if I.iRight (I.iRight (iParent)) < I.nGoodies:
                # And has a child
                #print I.theHeap [I.iRight (iParent)], I.iRight (iParent)
                I.heapify (I.iRight (iParent))
            if I.theWinnah (I.theHeap [I.iRight (iParent)].lower (), 
                            I.theHeap [iParent].lower ()):
                # Right child less (greater) than parent
                I.swap (iParent, I.iRight (iParent))
                I.heapify (I.iRight (iParent))
                #I.heapify (iParent)
    
    def reHeap (I, iParent = 0):
        '''
        Reheaps the tree after the root is removed and replaced by the
        most extreme (positionally) value.  Beginning at the root, only
        one of the child hives needs to be adjusted.  When the child hive
        is adjusted, only one of its child hives has to be adjusted.  This
        divide and conquer approach is where the efficiency arises.
        '''
        if I.iLeft (iParent) < I.nGoodies:
            # Left child exists
            if I.theWinnah (I.theHeap [I.iLeft (iParent)].lower (), 
                            I.theHeap [iParent].lower ()):
                # Not a heap, left child greater (smaller) than parent
                if I.iRight (iParent) < I.nGoodies \
                   and\
                   I.theWinnah (I.theHeap [I.iRight (iParent)].lower (), 
                                I.theHeap [I.iLeft (iParent)].lower ()):
                    # Right child lesser (greater) of the three
                    I.swap (iParent, I.iRight (iParent))
                    I.reHeap (I.iRight (iParent))
                else:
                    # Left child lesser (greater) of the three
                    I.swap (iParent, I.iLeft (iParent))
                    I.reHeap (I.iLeft (iParent))
            elif I.iRight (iParent) < I.nGoodies \
                 and\
                 I.theWinnah (I.theHeap [I.iRight (iParent)].lower (), 
                              I.theHeap [iParent].lower ()):
                # Not a heap, right child less (greater) than parent
                I.swap (iParent, I.iRight (iParent))
                I.reHeap (I.iRight (iParent))
                
    def iLeft (I, iParent): return 2 * iParent + 1
    
    def iRight (I, iParent): return 2 * iParent + 2
        
    def swap (I, srcIndex, dstIndex):
        '''
        Exchanges the two values at the specified indexes.
        '''
        temp = I.theHeap [srcIndex]
        I.theHeap [srcIndex] = I.theHeap [dstIndex]
        I.theHeap [dstIndex] = temp
    
    def sort (I):
        '''
        Sorts the heap by removing the root (the most extreme value)
        to the output list and replacing the root with the value at
        the most extreme position.
        '''
        
        unsorted = Heap (I.theHeap [:], I.desc)
        sorted = []
        while unsorted.nGoodies > 0:
            sorted.append (unsorted.theHeap [0])
            unsorted.nGoodies -= 1
            unsorted.theHeap [0] = unsorted.theHeap [unsorted.nGoodies]
            unsorted.reHeap ()
        I.theHeap = sorted [:]
        

def main():
    ''' Illustrate a heapsort.  If a list is passed in,
        it is heapified on construction.'''
    
    theThangs = ["This", "is", "an", "illustration",
                 "of", "a", "heapsort. ",
                 "Its", "time", "complexity", "is", 
                 "usually", "expressed", "as", "O(blah)"]
    
    print "The stuff: ",
    for i in theThangs: print i,
    print
    heap = Heap (theThangs)
    print "\nHeapified on construction: "
    heap.showHive ()
    heap.sort ()
    print
    print "Sorted (ascending): ",
    for i in heap.theHeap: print i,
    print
    print
    print "Set mode to descending"
    heap.desc = True;
    heap.heapify ()
    print "Heapified: "
    heap.showHive ()
    heap.sort ()
    print
    print "Sorted (descending): ",
    for i in heap.theHeap: print i,
    print
    raw_input ("\nPress ENTER to exit: ")

if __name__ == '__main__':
    main()

class Heap:
    
    def __init__ (I, theHeap = [], desc = False):
        '''
        Initializes a newly instantiated heap.  If data is passed
        in the tree will be heapified on construction.
        '''
        I.theHeap = theHeap
        I.nGoodies = len (theHeap)
        I.desc = desc
        if I.nGoodies > 0: I.heapify ()
        
    def theWinnah (I, a, b):
        '''
        Comparison function that adapts to whether or not the sort
        is ascending or descending.
        '''
        if I.desc == False: return (a < b)
        else: return (b <= a)
        
    def showHive (I):
        '''
        Arrange the tree in a visual hive.  The tree must have sixteen
        or fewer members.
        '''
        if I.nGoodies > 16: 
            print "Hive too large to show"
            return
        i = 0
        level = 0
        lineLength = 80
        while i < I.nGoodies:
            pcount = 2**level
            cellWidth = lineLength / pcount
            line = ""
            while pcount > 0:
                word = I.theHeap [i]
                line += word.center (cellWidth, ' ')
                pcount -= 1
                i += 1
                if i >= I.nGoodies: break
            print line
            level += 1
    
    def heapify (I, iParent = 0):
        '''
        This adjusts the tree so that it qualifies as a heap.  That is,
        it is a complete tree and any parent is smaller (larger, for
        descending sorts) than either of its children.  This is not as
        efficient as the reheap process, because the entire tree must
        be examined.
        '''
        if I.iLeft (iParent) < I.nGoodies:
            # Left child exists
            if I.iLeft (I.iLeft (iParent)) < I.nGoodies:
                # And has a child
                I.heapify (I.iLeft (iParent))
            if I.theWinnah (I.theHeap [I.iLeft (iParent)].lower (),
                            I.theHeap [iParent].lower ()):
                # Left child less (greater) than parent, 
                # swap and reaheapify the hive
                I.swap (iParent, I.iLeft (iParent))
                I.heapify (I.iLeft (iParent))
                #I.heapify (iParent)
        if I.iRight (iParent) < I.nGoodies:
            # Right child exists
            if I.iRight (I.iRight (iParent)) < I.nGoodies:
                # And has a child
                #print I.theHeap [I.iRight (iParent)], I.iRight (iParent)
                I.heapify (I.iRight (iParent))
            if I.theWinnah (I.theHeap [I.iRight (iParent)].lower (), 
                            I.theHeap [iParent].lower ()):
                # Right child less (greater) than parent
                I.swap (iParent, I.iRight (iParent))
                I.heapify (I.iRight (iParent))
                #I.heapify (iParent)
    
    def reHeap (I, iParent = 0):
        '''
        Reheaps the tree after the root is removed and replaced by the
        most extreme (positionally) value.  Beginning at the root, only
        one of the child hives needs to be adjusted.  When the child hive
        is adjusted, only one of its child hives has to be adjusted.  This
        divide and conquer approach is where the efficiency arises.
        '''
        if I.iLeft (iParent) < I.nGoodies:
            # Left child exists
            if I.theWinnah (I.theHeap [I.iLeft (iParent)].lower (), 
                            I.theHeap [iParent].lower ()):
                # Not a heap, left child greater (smaller) than parent
                if I.iRight (iParent) < I.nGoodies \
                   and\
                   I.theWinnah (I.theHeap [I.iRight (iParent)].lower (), 
                                I.theHeap [I.iLeft (iParent)].lower ()):
                    # Right child lesser (greater) of the three
                    I.swap (iParent, I.iRight (iParent))
                    I.reHeap (I.iRight (iParent))
                else:
                    # Left child lesser (greater) of the three
                    I.swap (iParent, I.iLeft (iParent))
                    I.reHeap (I.iLeft (iParent))
            elif I.iRight (iParent) < I.nGoodies \
                 and\
                 I.theWinnah (I.theHeap [I.iRight (iParent)].lower (), 
                              I.theHeap [iParent].lower ()):
                # Not a heap, right child less (greater) than parent
                I.swap (iParent, I.iRight (iParent))
                I.reHeap (I.iRight (iParent))
                
    def iLeft (I, iParent): return 2 * iParent + 1
    
    def iRight (I, iParent): return 2 * iParent + 2
        
    def swap (I, srcIndex, dstIndex):
        '''
        Exchanges the two values at the specified indexes.
        '''
        temp = I.theHeap [srcIndex]
        I.theHeap [srcIndex] = I.theHeap [dstIndex]
        I.theHeap [dstIndex] = temp
    
    def sort (I):
        '''
        Sorts the heap by removing the root (the most extreme value)
        to the output list and replacing the root with the value at
        the most extreme position.
        '''
        
        unsorted = Heap (I.theHeap [:], I.desc)
        sorted = []
        while unsorted.nGoodies > 0:
            sorted.append (unsorted.theHeap [0])
            unsorted.nGoodies -= 1
            unsorted.theHeap [0] = unsorted.theHeap [unsorted.nGoodies]
            unsorted.reHeap ()
        I.theHeap = sorted [:]
        

def main():
    ''' Illustrate a heapsort.  If a list is passed in,
        it is heapified on construction.'''
    
    theThangs = ["This", "is", "an", "illustration",
                 "of", "a", "heapsort. ",
                 "Its", "time", "complexity", "is", 
                 "usually", "expressed", "as", "O(blah)"]
    
    print "The stuff: ",
    for i in theThangs: print i,
    print
    heap = Heap (theThangs)
    print "\nHeapified on construction: "
    heap.showHive ()
    heap.sort ()
    print
    print "Sorted (ascending): ",
    for i in heap.theHeap: print i,
    print
    print
    print "Set mode to descending"
    heap.desc = True;
    heap.heapify ()
    print "Heapified: "
    heap.showHive ()
    heap.sort ()
    print
    print "Sorted (descending): ",
    for i in heap.theHeap: print i,
    print
    raw_input ("\nPress ENTER to exit: ")

if __name__ == '__main__':
    main()

Quote:

Originally Posted by Output

(Toggle Plain Text)

The stuff:  This is an illustration of a heapsort.  Its time complexity is usually ex
pressed as O(blah)

Heapified on construction:
                                       a
              illustration                                 an
        Its                  is              complexity              as
   This      time       of        is     usually  expressed heapsort.  O(blah)

Sorted (ascending):  a an as complexity expressed heapsort.  illustration is is Its O
(blah) of This time usually

Set mode to descending
Heapified:
                                    usually
                  Its                                     time
     complexity              is               O(blah)               This
    a         an    expressed     is        as    heapsort. illustration    of

Sorted (descending):  usually time This of O(blah) Its is is illustration heapsort.
expressed complexity as an a

Press ENTER to exit:

bl00dninja · Sep 14th, 2006, 2:02 AM

heapsort:

(Toggle Plain Text)

void heapSort(int numbers[], int array_size)
{
  int i, temp;

  for (i = (array_size / 2)-1; i >= 0; i--)
    siftDown(numbers, i, array_size);

  for (i = array_size-1; i >= 1; i--)
  {
    temp = numbers[0];
    numbers[0] = numbers[i];
    numbers[i] = temp;
    siftDown(numbers, 0, i-1);
  }
}


void siftDown(int numbers[], int root, int bottom)
{
  int done, maxChild, temp;

  done = 0;
  while ((root*2 <= bottom) && (!done))
  {
    if (root*2 == bottom)
      maxChild = root * 2;
    else if (numbers[root * 2] > numbers[root * 2 + 1])
      maxChild = root * 2;
    else
      maxChild = root * 2 + 1;

    if (numbers[root] < numbers[maxChild])
    {
      temp = numbers[root];
      numbers[root] = numbers[maxChild];
      numbers[maxChild] = temp;
      root = maxChild;
    }
    else
      done = 1;
  }
}

bl00dninja · Sep 14th, 2006, 2:03 AM

mergesort:

(Toggle Plain Text)

void mergeSort(int numbers[], int temp[], int array_size)
{
  m_sort(numbers, temp, 0, array_size - 1);
}

void m_sort(int numbers[], int temp[], int left, int right)
{
  int mid;

  if (right > left)
  {
    mid = (right + left) / 2;
    m_sort(numbers, temp, left, mid);
    m_sort(numbers, temp, mid+1, right);

    merge(numbers, temp, left, mid+1, right);
  }
}

void merge(int numbers[], int temp[], int left, int mid, int right)
{
  int i, left_end, num_elements, tmp_pos;

  left_end = mid - 1;
  tmp_pos = left;
  num_elements = right - left + 1;

  while ((left <= left_end) && (mid <= right))
  {
    if (numbers[left] <= numbers[mid])
    {
      temp[tmp_pos] = numbers[left];
      tmp_pos = tmp_pos + 1;
      left = left +1;
    }
    else
    {
      temp[tmp_pos] = numbers[mid];
      tmp_pos = tmp_pos + 1;
      mid = mid + 1;
    }
  }

  while (left <= left_end)
  {
    temp[tmp_pos] = numbers[left];
    left = left + 1;
    tmp_pos = tmp_pos + 1;
  }
  while (mid <= right)
  {
    temp[tmp_pos] = numbers[mid];
    mid = mid + 1;
    tmp_pos = tmp_pos + 1;
  }

  for (i=0; i <= num_elements; i++)
  {
    numbers[right] = temp[right];
    right = right - 1;
  }
}

Aug 24th, 2006, 4:35 PM	#1
Jimbo Battle Programmer Join Date: Feb 2006 Location: Bellevue, WA, USA Posts: 754 Rep Power: 3	25 ways to efficiently sort an array/list of integers Ok, this should be manageable. Only 25 solutions needed... but there's a catch. It must be efficient (i.e. better than bubblesort) and you need to explain why or how it's efficient. Algorithms can be repeated, but only if you optimize better or differently (e.g. time vs. space) than a previous entry (you need to explain what you did better or differently). Post your language just so we can tell what it is. I'll kick it off 1) MIPS 32 - Quicksort (comments are in C-ish pseudo-code) (Toggle Plain Text) .text qsort: # performs quicksort on array at $a0, with length $a1 addi $sp,$sp,-12 # allocate stack space sw $ra,12($sp) # save return address slti $t0,$a1,2 # if(len <= 1) bne $t0,$0,$END # jump to end (already sorted) addi $t0,$0,2 bne $t0,$a1,$Chuck # if(len==2) compare the 2 lw $t1,0($a0) # load array[0] lw $t2,4($a0) # load array[1] slt $t0,$t2,$t1 # if array[1] < array[0] beq $t0,$0,$END sw $t1,4($a0) # swap array[0] and array[1] sw $t2,0($a0) j $END # now we're done $Chuck: # this is where the actual quicksort happens srl $t0,$a1,1 # piv = len / 2 sll $t0,$t0,2 # align to word size add $t0,$a0,$t0 # mem addr. of pivot lw $t1,0($t0) # $t1 = mem[piv] addi $t2,$a1,-1 # $t2 = len - 1; sll $t2,$t2,2 # align to word size add $t2,$a0,$t2 # mem addr. of end lw $t3,0($t2) # t3 = mem[end] sw $t3,0($t0) # swap pivot and end value sw $t1,0($t2) # pivot value is in $t1 add $t5,$t2,$0 # j = piv - 1 add $t3,$a0,$0 # i = 0 slt $t7,$t3,$t5 # while(i < j) beq $t7,$0,$Kick $Norris: # while(array[i] < array[piv]) i++; lw $t4,0($t3) slt $t7,$t4,$t1 # if(array[i] < array[piv]) beq $t7,$0,$Round addi $t3,$t3,4 # move to next word j $Norris $Round: # while(array[j] > array[piv]) j--; lw $t6,0($t5) slt $t7,$t1,$t6 # if(array[j] > array[piv]) beq $t7,$0,$House addi $t5,$t5,-4 # move to next word j $Round $House: # if (i < j) slt $t7,$t3,$t5 beq $t7,$0,$Kick sw $t6,0($t3) # swap(array[i],array[j]) sw $t4,0($t5) j $Norris # loop through again $Kick: # now reset pivot and recurse lw $t7,0($t3) # $t7 = array[i] sw $t1,0($t3) # array[i] = array[piv] sw $t7,0($t2) # array[piv] = array[i] addi $t8,$t3,4 # address of [i+1] (for 2nd call) sw $t8,4($sp) # save to stack for later sub $t9,$t3,$a0 # mem offset of i from $a0 srl $t9,$t9,2 # value of i sub $t0,$a1,$t9 # len - i addi $t0,$t0,-1 # len - i - 1 sw $t0,8($sp) # save to stack for later addi $a1,$t9,-1 # len = i-1 = j jal qsort # qsort(array,len) lw $t8,4($sp) # reload ptr to 2nd partition lw $t9,8($sp) # reload length of 2nd partition add $a0,$t8,$0 # save to $a0 add $a1,$t9,$0 # save to $a1 jal qsort # qsort(array+i+1,len-i-1) $END: lw $ra,12($sp) # reload return address addi $sp,$sp,12 # deallocate stack space jr $ra # return from function .text qsort: # performs quicksort on array at $a0, with length $a1 addi $sp,$sp,-12 # allocate stack space sw $ra,12($sp) # save return address slti $t0,$a1,2 # if(len <= 1) bne $t0,$0,$END # jump to end (already sorted) addi $t0,$0,2 bne $t0,$a1,$Chuck # if(len==2) compare the 2 lw $t1,0($a0) # load array[0] lw $t2,4($a0) # load array[1] slt $t0,$t2,$t1 # if array[1] < array[0] beq $t0,$0,$END sw $t1,4($a0) # swap array[0] and array[1] sw $t2,0($a0) j $END # now we're done $Chuck: # this is where the actual quicksort happens srl $t0,$a1,1 # piv = len / 2 sll $t0,$t0,2 # align to word size add $t0,$a0,$t0 # mem addr. of pivot lw $t1,0($t0) # $t1 = mem[piv] addi $t2,$a1,-1 # $t2 = len - 1; sll $t2,$t2,2 # align to word size add $t2,$a0,$t2 # mem addr. of end lw $t3,0($t2) # t3 = mem[end] sw $t3,0($t0) # swap pivot and end value sw $t1,0($t2) # pivot value is in $t1 add $t5,$t2,$0 # j = piv - 1 add $t3,$a0,$0 # i = 0 slt $t7,$t3,$t5 # while(i < j) beq $t7,$0,$Kick $Norris: # while(array[i] < array[piv]) i++; lw $t4,0($t3) slt $t7,$t4,$t1 # if(array[i] < array[piv]) beq $t7,$0,$Round addi $t3,$t3,4 # move to next word j $Norris $Round: # while(array[j] > array[piv]) j--; lw $t6,0($t5) slt $t7,$t1,$t6 # if(array[j] > array[piv]) beq $t7,$0,$House addi $t5,$t5,-4 # move to next word j $Round $House: # if (i < j) slt $t7,$t3,$t5 beq $t7,$0,$Kick sw $t6,0($t3) # swap(array[i],array[j]) sw $t4,0($t5) j $Norris # loop through again $Kick: # now reset pivot and recurse lw $t7,0($t3) # $t7 = array[i] sw $t1,0($t3) # array[i] = array[piv] sw $t7,0($t2) # array[piv] = array[i] addi $t8,$t3,4 # address of [i+1] (for 2nd call) sw $t8,4($sp) # save to stack for later sub $t9,$t3,$a0 # mem offset of i from $a0 srl $t9,$t9,2 # value of i sub $t0,$a1,$t9 # len - i addi $t0,$t0,-1 # len - i - 1 sw $t0,8($sp) # save to stack for later addi $a1,$t9,-1 # len = i-1 = j jal qsort # qsort(array,len) lw $t8,4($sp) # reload ptr to 2nd partition lw $t9,8($sp) # reload length of 2nd partition add $a0,$t8,$0 # save to $a0 add $a1,$t9,$0 # save to $a1 jal qsort # qsort(array+i+1,len-i-1) $END: lw $ra,12($sp) # reload return address addi $sp,$sp,12 # deallocate stack space jr $ra # return from function Quicksort runs in O(n*log(n)) time on average (worst case is O(n^2)). Memory usage is simply the original array plus a some overhead per function call (which can add up, as it is recursive), which comes out to O(n) where n is the length of the array. This particular implementation uses all temporary registers (to reduce access to memory for variables), and 3 words of stack space per call.

Aug 24th, 2006, 7:32 PM	#3
andro Professional Programmer Join Date: Oct 2005 Location: California Posts: 294 Rep Power: 3	cpp Syntax (Toggle Plain Text) #include <iostream> #include <algorithm> int main() { int array[] = {9, 7, 5, 4, 1, 7, 3, 2, 8, 0}; const int size = sizeof(array)/sizeof(int); std::sort(array, array+size); for (int i = 0; i < size; i++) std::cout << array[i]; return 0; } #include <iostream> #include <algorithm> int main() { int array[] = {9, 7, 5, 4, 1, 7, 3, 2, 8, 0}; const int size = sizeof(array)/sizeof(int); std::sort(array, array+size); for (int i = 0; i < size; i++) std::cout << array[i]; return 0; } O(n log N) - I think I read that std::sort uses introsort nowadays... EDIT: did some reading, it looks like just the SGI C++ STL uses introsort, I guess the regular C++ STL still uses quicksort...

Aug 24th, 2006, 7:52 PM	#4
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	Introsort is a variant of quicksort. Maybe I'll do a heapsort. Maybe I'll go to the dentist, too, lol. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Aug 25th, 2006, 7:30 AM	#6
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	I wasn't suggesting it wasn't a valid entry, just characterizing it. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Aug 25th, 2006, 8:10 PM	#7
glimmy Programmer Join Date: May 2005 Location: Minnesota Posts: 42 Rep Power: 0	3) Perl- Mergesort (Toggle Plain Text) sub merge { my ($left, $right) = @_; my @merged; while ((scalar(@$left) > 0) && (scalar(@$right))) { if ($left->[0] <= $right->[0]) { push @merged, shift(@$left); } else { push @merged, shift(@$right); } } if (scalar(@$left) > 0) { push @merged, shift(@$left); } if (scalar(@$right) > 0) { push @merged, shift(@$right); } return @merged; } sub mergesort { my @list = @_; my (@left,@right); if (scalar(@list) <= 1) { return @list; } else { my $middlin = scalar(@list) / 2; foreach (0..($middlin - 1)) { push @left, $list[$_]; } foreach ($middlin..(scalar(@list) - 1)) { push @right, $list[$_]; } @left = mergesort(@left); @right = mergesort(@right); return &merge(\@left,\@right); } } sub merge { my ($left, $right) = @_; my @merged; while ((scalar(@$left) > 0) && (scalar(@$right))) { if ($left->[0] <= $right->[0]) { push @merged, shift(@$left); } else { push @merged, shift(@$right); } } if (scalar(@$left) > 0) { push @merged, shift(@$left); } if (scalar(@$right) > 0) { push @merged, shift(@$right); } return @merged; } sub mergesort { my @list = @_; my (@left,@right); if (scalar(@list) <= 1) { return @list; } else { my $middlin = scalar(@list) / 2; foreach (0..($middlin - 1)) { push @left, $list[$_]; } foreach ($middlin..(scalar(@list) - 1)) { push @right, $list[$_]; } @left = mergesort(@left); @right = mergesort(@right); return &merge(\@left,\@right); } }

Aug 24th, 2006, 5:51 PM	#2
glimmy Programmer Join Date: May 2005 Location: Minnesota Posts: 42 Rep Power: 0	Maybe this could help some people: http://en.wikipedia.org/wiki/Sorting...ing_algorithms I will try to implement one when the storm here passes.

Aug 24th, 2006, 8:52 PM	#5
andro Professional Programmer Join Date: Oct 2005 Location: California Posts: 294 Rep Power: 3	Oh, I thought it was the efficient parts of quicksort and heapsort combined.

Sep 14th, 2006, 2:02 AM	#9
bl00dninja Programming Guru Join Date: Oct 2004 Location: namespace std Posts: 1,246 Rep Power: 5	heapsort: (Toggle Plain Text) void heapSort(int numbers[], int array_size) { int i, temp; for (i = (array_size / 2)-1; i >= 0; i--) siftDown(numbers, i, array_size); for (i = array_size-1; i >= 1; i--) { temp = numbers[0]; numbers[0] = numbers[i]; numbers[i] = temp; siftDown(numbers, 0, i-1); } } void siftDown(int numbers[], int root, int bottom) { int done, maxChild, temp; done = 0; while ((root2 <= bottom) && (!done)) { if (root2 == bottom) maxChild = root * 2; else if (numbers[root * 2] > numbers[root * 2 + 1]) maxChild = root * 2; else maxChild = root * 2 + 1; if (numbers[root] < numbers[maxChild]) { temp = numbers[root]; numbers[root] = numbers[maxChild]; numbers[maxChild] = temp; root = maxChild; } else done = 1; } } void heapSort(int numbers[], int array_size) { int i, temp; for (i = (array_size / 2)-1; i >= 0; i--) siftDown(numbers, i, array_size); for (i = array_size-1; i >= 1; i--) { temp = numbers[0]; numbers[0] = numbers[i]; numbers[i] = temp; siftDown(numbers, 0, i-1); } } void siftDown(int numbers[], int root, int bottom) { int done, maxChild, temp; done = 0; while ((root2 <= bottom) && (!done)) { if (root2 == bottom) maxChild = root * 2; else if (numbers[root * 2] > numbers[root * 2 + 1]) maxChild = root * 2; else maxChild = root * 2 + 1; if (numbers[root] < numbers[maxChild]) { temp = numbers[root]; numbers[root] = numbers[maxChild]; numbers[maxChild] = temp; root = maxChild; } else done = 1; } } __________________ i put on my robe and wizard hat... Have you ever heard of Plato, Aristotle, Socrates?...Morons.

Sep 14th, 2006, 2:03 AM	#10
bl00dninja Programming Guru Join Date: Oct 2004 Location: namespace std Posts: 1,246 Rep Power: 5	mergesort: (Toggle Plain Text) void mergeSort(int numbers[], int temp[], int array_size) { m_sort(numbers, temp, 0, array_size - 1); } void m_sort(int numbers[], int temp[], int left, int right) { int mid; if (right > left) { mid = (right + left) / 2; m_sort(numbers, temp, left, mid); m_sort(numbers, temp, mid+1, right); merge(numbers, temp, left, mid+1, right); } } void merge(int numbers[], int temp[], int left, int mid, int right) { int i, left_end, num_elements, tmp_pos; left_end = mid - 1; tmp_pos = left; num_elements = right - left + 1; while ((left <= left_end) && (mid <= right)) { if (numbers[left] <= numbers[mid]) { temp[tmp_pos] = numbers[left]; tmp_pos = tmp_pos + 1; left = left +1; } else { temp[tmp_pos] = numbers[mid]; tmp_pos = tmp_pos + 1; mid = mid + 1; } } while (left <= left_end) { temp[tmp_pos] = numbers[left]; left = left + 1; tmp_pos = tmp_pos + 1; } while (mid <= right) { temp[tmp_pos] = numbers[mid]; mid = mid + 1; tmp_pos = tmp_pos + 1; } for (i=0; i <= num_elements; i++) { numbers[right] = temp[right]; right = right - 1; } } void mergeSort(int numbers[], int temp[], int array_size) { m_sort(numbers, temp, 0, array_size - 1); } void m_sort(int numbers[], int temp[], int left, int right) { int mid; if (right > left) { mid = (right + left) / 2; m_sort(numbers, temp, left, mid); m_sort(numbers, temp, mid+1, right); merge(numbers, temp, left, mid+1, right); } } void merge(int numbers[], int temp[], int left, int mid, int right) { int i, left_end, num_elements, tmp_pos; left_end = mid - 1; tmp_pos = left; num_elements = right - left + 1; while ((left <= left_end) && (mid <= right)) { if (numbers[left] <= numbers[mid]) { temp[tmp_pos] = numbers[left]; tmp_pos = tmp_pos + 1; left = left +1; } else { temp[tmp_pos] = numbers[mid]; tmp_pos = tmp_pos + 1; mid = mid + 1; } } while (left <= left_end) { temp[tmp_pos] = numbers[left]; left = left + 1; tmp_pos = tmp_pos + 1; } while (mid <= right) { temp[tmp_pos] = numbers[mid]; mid = mid + 1; tmp_pos = tmp_pos + 1; } for (i=0; i <= num_elements; i++) { numbers[right] = temp[right]; right = right - 1; } } __________________ i put on my robe and wizard hat... Have you ever heard of Plato, Aristotle, Socrates?...Morons.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Switch to Linear Mode Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
sort and swap	brad sue	C	1	Mar 25th, 2006 6:33 AM
interpolation search on a million	EverLearning	C	24	Jun 15th, 2005 2:42 PM
threaded merge sort help	AusTex	C	1	May 1st, 2005 4:58 PM

Programming Forums > Application Development > Software Design and Algorithms

25 ways to efficiently sort an array/list of integers