Programming Forums - 25 ways to efficiently sort an array/list of integers

Programming Forums (http://www.programmingforums.org/forumindex.php)

- Software Design and Algorithms (http://www.programmingforums.org/forum64.html)

- - 25 ways to efficiently sort an array/list of integers (http://www.programmingforums.org/showthread.php?t=11160)

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)

.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.

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.

#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...

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

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

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

3) Perl- Mergesort

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);

        }

}

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.

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

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:

heapsort:

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;

  }

}

mergesort:

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;

  }

}