Graal Forums  

Go Back   Graal Forums > Development Forums > NPC Scripting > Code Gallery
FAQ Members List Calendar Search Today's Posts Mark Forums Read

Reply
 
Thread Tools Search this Thread Display Modes
  #1  
Old 10-11-2008, 09:00 AM
Gambet Gambet is offline
Registered User
Join Date: Oct 2003
Posts: 2,712
Gambet is on a distinguished road
Sorting Data: Selection Sort

A little over a year ago I released an example of how to use the Bubble Sort algorithm to sort a set of data, which can be found here.

I started my Freshman year at my University in the Fall, and for the Programming I course we're learning OOP via Java (going to be a CS Major). The sorting algorithm that we were taught was the Selection Sort method, which is more efficient than the Bubble Sort method; and considering the fact that I posted the Bubble Sort method, it only fits that I show you the Selection Sort method as well.

I programmed it in Java since it's the only thing that I could use at the moment to test the code, but the method itself is the same regardless of the language so it shouldn't be a problem to understand how to convert it to GScript for whomever might use it.


SelectionSort.java:

PHP Code:
/*
 *@author Gambet
*/

public class SelectionSort
{
  
double dataSet[] = {16425820100541000523};

  public 
void selectionSort()
  {
   for (
int a 0dataSet.length-1a++)
    {
     for (
int b a+1dataSet.lengthb++)
      { 
       if (
dataSet[b] < dataSet[a])
        {
         
double results dataSet[b];
         
dataSet[b] = dataSet[a];
         
dataSet[a] = results;
        } 
      }
    }    
  }

  public 
void showResults()
  {
   for(
int sorted 0sorted dataSet.lengthsorted++)
    {
     
System.out.println(dataSet[sorted]);
    } 
  }


TestSelectionSort.java:

PHP Code:
class TestSelectionSort
{
 public static 
void main(String[] args)
  {
   
SelectionSort s = new SelectionSort();
   
s.selectionSort();
   
s.showResults();
  }


Quote:
Originally Posted by Results
1.0
2.0
4.0
5.0
6.0
8.0
20.0
54.0
100.0
523.0
1000.0

The above code sorts from least to greatest. To convert from greatest to least, switch:

PHP Code:
if (dataSet[b] < dataSet[a]) 
to

PHP Code:
if (dataSet[b] > dataSet[a]) 


NOTE: I used the same set of values that I used for the Bubble Sort algorithm.

Last edited by Darlene159; 09-16-2009 at 04:06 AM..
Reply With Quote
  #2  
Old 10-11-2008, 11:59 AM
Crono Crono is offline
:pluffy:
Join Date: Feb 2002
Location: Sweden
Posts: 20,000
Crono has a reputation beyond reputeCrono has a reputation beyond reputeCrono has a reputation beyond reputeCrono has a reputation beyond reputeCrono has a reputation beyond reputeCrono has a reputation beyond reputeCrono has a reputation beyond reputeCrono has a reputation beyond reputeCrono has a reputation beyond reputeCrono has a reputation beyond reputeCrono has a reputation beyond repute
Send a message via AIM to Crono
Had to do something like this last week or so, except I went the lame way and used Collections.sort(). Of course I messed up after it sorted it by 1 12 13 2 3 4. Should re-do it using your logic here, thanks. :]
__________________
Reply With Quote
  #3  
Old 10-11-2008, 01:31 PM
xXziroXx xXziroXx is offline
Master of Puppets
xXziroXx's Avatar
Join Date: May 2004
Location: Sweden
Posts: 5,288
xXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant future
Send a message via AIM to xXziroXx Send a message via MSN to xXziroXx
I thought we were not allowed to post non-GScript scripts in the Code Library.
__________________

"A delayed game is eventually good, but a rushed game is forever bad." - Shigeru Miyamoto
Reply With Quote
  #4  
Old 10-11-2008, 03:25 PM
Programmer Programmer is offline
Coder
Programmer's Avatar
Join Date: Jan 2008
Location: -78.464422, 106.837328
Posts: 449
Programmer has a spectacular aura aboutProgrammer has a spectacular aura about
Send a message via AIM to Programmer Send a message via MSN to Programmer Send a message via Yahoo to Programmer
I converted it to GScript so that it can be tested by Graal developers.

PHP Code:
dataSet = {16425820100541000523};

echo(
dataSet);
selectionSort();
echo(
dataSet);

function 
selectionSort()
{
    for (
0dataSet.size() - 1a++)
    {
        for (
1dataSet.size(); b++)
        {
            if (
dataSet[b] < dataSet[a])
            {
                
result dataSet[b];
                
dataSet[b] = dataSet[a];
                
dataSet[a] = result;
            }
        }
    }

Very nice, Gambet.

Quote:
Originally Posted by xXziroXx View Post
I thought we were not allowed to post non-GScript scripts in the Code Library.
I did the same thing about 2 years ago when I posted the Java code for an analog clock. Skyld let it stay for the reason that the formula might help some people, and this is a similar case.
__________________
- Iᴀɴ Zɪᴍᴍᴇʀᴍᴀɴ
Reply With Quote
  #5  
Old 10-11-2008, 05:03 PM
cbk1994 cbk1994 is offline
the fake one
cbk1994's Avatar
Join Date: Mar 2003
Location: San Francisco
Posts: 10,718
cbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond repute
Send a message via AIM to cbk1994
Very nice, I will likely end up using this somewhere.
__________________
Reply With Quote
  #6  
Old 10-11-2008, 05:48 PM
Gambet Gambet is offline
Registered User
Join Date: Oct 2003
Posts: 2,712
Gambet is on a distinguished road
Quote:
Originally Posted by xXziroXx View Post
I thought we were not allowed to post non-GScript scripts in the Code Library.

My apologizes if you can't, but I haven't played Graal in quite some time so I wouldn't have a method of testing the code since GScript is fabricated and has no standalone compiler. It's not so much that I wouldn't be able to do it in GScript myself, but I'd rather release something that I was certain was error proof rather than just writing code in some text file and assuming everything in it will compile and run.


From an educational standpoint, the importance is learning the Selection Sort algorithm so that you can apply it to any programming language.


Quote:
Originally Posted by Programmer View Post
I converted it to GScript so that it can be tested by Graal developers.

Thank you.
Reply With Quote
  #7  
Old 10-11-2008, 06:44 PM
Understood Understood is offline
Registered User
Join Date: Jun 2006
Location: Orlando, FL
Posts: 120
Understood is on a distinguished road
Quote:
Originally Posted by cbk1994 View Post
Very nice, I will likely end up using this somewhere.
This is what I used for the trivia scores =p
Reply With Quote
  #8  
Old 10-11-2008, 07:49 PM
napo_p2p napo_p2p is offline
oh snaps
napo_p2p's Avatar
Join Date: Sep 2003
Location: Pismo Beach, California
Posts: 2,118
napo_p2p has a spectacular aura aboutnapo_p2p has a spectacular aura about
Send a message via AIM to napo_p2p Send a message via MSN to napo_p2p
A good example for new scripters . I have a feeling that you'll be back for one of the O(n log n) algorithms.

Quote:
Originally Posted by Crono View Post
Had to do something like this last week or so, except I went the lame way and used Collections.sort(). Of course I messed up after it sorted it by 1 12 13 2 3 4. Should re-do it using your logic here, thanks. :]
If you use List<Integer>, I believe that Collections.sort() will sort numerically.
__________________
Scito hoc super omnia.
Haec vita est tua una sola.
Dum vita superest, utere maxime quoque puncto, momento, et hora quae habes.
Tempus neminem non manet.
Noli manere tempus.
Carpe Diem

Seize the Day.
Reply With Quote
  #9  
Old 10-11-2008, 09:07 PM
cbk1994 cbk1994 is offline
the fake one
cbk1994's Avatar
Join Date: Mar 2003
Location: San Francisco
Posts: 10,718
cbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond repute
Send a message via AIM to cbk1994
Quote:
Originally Posted by Understood View Post
This is what I used for the trivia scores =p
Looking over the code, that's actually pretty much what I did on Vesporia as well.
__________________
Reply With Quote
  #10  
Old 10-11-2008, 09:38 PM
kingdom_90 kingdom_90 is offline
Registered User
Join Date: Aug 2008
Location: Norway
Posts: 8
kingdom_90 is on a distinguished road
Good efficient code there Good job
Reply With Quote
  #11  
Old 10-11-2008, 09:52 PM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to Tolnaftate2004
If you're looking for something even a bit more efficient, I would look up the quicksort algorithm.
__________________
◕‿‿◕ · pfa · check yer syntax! · src

Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/
Reply With Quote
  #12  
Old 10-11-2008, 10:10 PM
Gambet Gambet is offline
Registered User
Join Date: Oct 2003
Posts: 2,712
Gambet is on a distinguished road
Quote:
Originally Posted by Tolnaftate2004 View Post
If you're looking for something even a bit more efficient, I would look up the quicksort algorithm.


Yeah, that would also fall under the O(n log n) that napo addressed. I believe that the algorithms course that we have over here is an upper-division course, so I suppose I'll get into the higher-level sorting methods as I progress into the major.
Reply With Quote
  #13  
Old 10-11-2008, 10:34 PM
napo_p2p napo_p2p is offline
oh snaps
napo_p2p's Avatar
Join Date: Sep 2003
Location: Pismo Beach, California
Posts: 2,118
napo_p2p has a spectacular aura aboutnapo_p2p has a spectacular aura about
Send a message via AIM to napo_p2p Send a message via MSN to napo_p2p
Quote:
Originally Posted by Gambet View Post
Yeah, that would also fall under the O(n log n) that napo addressed. I believe that the algorithms course that we have over here is an upper-division course, so I suppose I'll get into the higher-level sorting methods as I progress into the major.
You might actually get to mergesort, quicksort, and heapsort sometime this year (maybe next quarter/semester), since they are not too complicated. I remember going over those in my first year.
__________________
Scito hoc super omnia.
Haec vita est tua una sola.
Dum vita superest, utere maxime quoque puncto, momento, et hora quae habes.
Tempus neminem non manet.
Noli manere tempus.
Carpe Diem

Seize the Day.
Reply With Quote
  #14  
Old 10-12-2008, 01:24 AM
Inverness Inverness is offline
Incubator
Inverness's Avatar
Join Date: Aug 2004
Location: Houston, Texas
Posts: 3,613
Inverness is a jewel in the roughInverness is a jewel in the rough
If you need an algorithm then invoke the power of Wikipedia.
__________________
Reply With Quote
  #15  
Old 10-12-2008, 01:24 AM
Gambet Gambet is offline
Registered User
Join Date: Oct 2003
Posts: 2,712
Gambet is on a distinguished road
Quote:
Originally Posted by napo_p2p View Post
You might actually get to mergesort, quicksort, and heapsort sometime this year (maybe next quarter/semester), since they are not too complicated. I remember going over those in my first year.

Well I'm taking Programming II with Discrete Math next semester (Discrete Math being a corequisite), so it's possible. I've already read through all of the notes for my Programming I course so I know that the only sorting algorithm that we're supposed to be taught in this class is the Selection Sort method, so I simply have to look on ahead and hope the next course offers a wider range of options.
Reply With Quote
Reply

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 10:35 AM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, vBulletin Solutions Inc.
Copyright (C) 1998-2019 Toonslab All Rights Reserved.