Graal Forums

Graal Forums (https://forums.graalonline.com/forums/index.php)
-   Code Gallery (https://forums.graalonline.com/forums/forumdisplay.php?f=179)
-   -   Sorting Data: Selection Sort (https://forums.graalonline.com/forums/showthread.php?t=82271)

Gambet 10-11-2008 09:00 AM
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[] = {1, 6, 4, 2, 5, 8, 20, 100, 54, 1000, 523};

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

  public void showResults()
  {
   for(int sorted = 0; sorted < dataSet.length; sorted++)
    {
     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.

Crono 10-11-2008 11:59 AM
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. :]

xXziroXx 10-11-2008 01:31 PM
I thought we were not allowed to post non-GScript scripts in the Code Library. :noob:

Programmer 10-11-2008 03:25 PM
I converted it to GScript so that it can be tested by Graal developers.

PHP Code:
dataSet = {1, 6, 4, 2, 5, 8, 20, 100, 54, 1000, 523};

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

function selectionSort()
{
    for (a = 0; a < dataSet.size() - 1; a++)
    {
        for (b = a + 1; b < dataSet.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 (Post 1431705)
I thought we were not allowed to post non-GScript scripts in the Code Library. :noob:
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.

cbk1994 10-11-2008 05:03 PM
Very nice, I will likely end up using this somewhere.

Gambet 10-11-2008 05:48 PM
Quote:
Originally Posted by xXziroXx (Post 1431705)
I thought we were not allowed to post non-GScript scripts in the Code Library. :noob:

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 (Post 1431733)
I converted it to GScript so that it can be tested by Graal developers.

Thank you. :)

Understood 10-11-2008 06:44 PM
Quote:
Originally Posted by cbk1994 (Post 1431751)
Very nice, I will likely end up using this somewhere.
This is what I used for the trivia scores =p

napo_p2p 10-11-2008 07:49 PM
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 (Post 1431694)
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.

cbk1994 10-11-2008 09:07 PM
Quote:
Originally Posted by Understood (Post 1431791)
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.

kingdom_90 10-11-2008 09:38 PM
Good efficient code there :) Good job

Tolnaftate2004 10-11-2008 09:52 PM
If you're looking for something even a bit more efficient, I would look up the quicksort algorithm.

Gambet 10-11-2008 10:10 PM
Quote:
Originally Posted by Tolnaftate2004 (Post 1431875)
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.

napo_p2p 10-11-2008 10:34 PM
Quote:
Originally Posted by Gambet (Post 1431877)
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.

Inverness 10-12-2008 01:24 AM
If you need an algorithm then invoke the power of Wikipedia.

Gambet 10-12-2008 01:24 AM
Quote:
Originally Posted by napo_p2p (Post 1431881)
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.

Inverness 10-12-2008 01:32 AM
I'd suggest learning Python, its a great programming and scripting language. With Python and C++ together you can't loose.

Python is also open-source, allowing you to create C/C++ extensions for Python or embed Python into a C/C++ application which is what I'm doing.

Python Code:
PHP Code:
def SelectionSort(array):
    for a in range(len(array)):
        for b in range(a + 1, len(array)):
            if array[b] < array[a]:
                tmp = array[b]
                array[b] = array[a]
                array[a] = tmp

#Testing code

data = [1, 6, 4, 2, 5, 8, 20, 100, 54, 1000, 523]
SelectionSort(data)
print(data) #Prints: [1, 2, 4, 5, 6, 8, 20, 54, 100, 523, 1000] 
Quote:
Originally Posted by Programmer (Post 1431733)
I converted it to GScript so that it can be tested by Graal developers.
How dare you place any code outside of a function !pissed!
And you're making global variables.

Programmer 10-12-2008 02:14 AM
Quote:
Originally Posted by Inverness (Post 1431994)
How dare you place any code outside of a function !pissed!
And you're making global variables.
Zzz...

PHP Code:
function onCreated()
{
    temp.dataSet = {1, 6, 4, 2, 5, 8, 20, 100, 54, 1000, 523};
    
    echo(temp.dataSet);
    temp.dataSet = selectionSort(temp.dataSet);
    echo(temp.dataSet);
    
    temp.dataSet = null;
    temp.dataSet.destroy();
}

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

Inverness 10-12-2008 02:32 AM
Quote:
Originally Posted by Programmer (Post 1432006)
Zzz...

PHP Code:
function onCreated()
{
    temp.dataSet = {1, 6, 4, 2, 5, 8, 20, 100, 54, 1000, 523};
    
    echo(temp.dataSet);
    temp.dataSet = selectionSort(temp.dataSet);
    echo(temp.dataSet);
    
    temp.dataSet = null;
    temp.dataSet.destroy();
}

function selectionSort(temp.data)
{
    for (a = 0; a < temp.data.size() - 1; a++)
    {
        for (b = a + 1; b < temp.data.size(); b++)
        {
            if (temp.data[b] < temp.data[a])
            {
                result = temp.data[b];
                temp.data[b] = temp.data[a];
                temp.data[a] = result;
            }
        }
    }
    
    return temp.data;
} 
That would cause an error because temp.dataSet is not an object with a destroy() function. And temp variables are destroyed automatically anyways when the function is over, no need to set it to null. Also, function parameters are automatically temp, you don't need to specify it. It's also less costly to send the array by reference using temp.dataSet.link() rather than duplicating it. :p
PHP Code:
function onCreated() {
  temp.dataset = {1, 6, 4, 2, 5, 8, 20, 100, 54, 1000, 523};

  echo(dataset);
  this.selectionsort(dataset.link());
  echo(dataset);
}
function selectionsort(data) {
  temp.a = 0;
  temp.b = 0;
  temp.tmp = 0;

  for (a = 0; a < data.size() - 1; a++) {
    for (b = a + 1; b < data.size(); b++) {
      if (data[b] < data[a]) {
        tmp = data[b];
        data[b] = data[a];
        data[a] = tmp;
      }
    }
  }
} 
Once a temp variable is initialized it can be referenced without using the temp prefix, however using the prefix is marginally faster.

Python is superior though. :D

[email protected] 10-12-2008 02:40 PM
HTML Code:
  temp.numbers = {1,4,6,2,65,20,200,4000,40,200};
  for (i: temp.numbers) {
    temp.e.add(i);
    temp.e[temp.c].sortvalue = i;
    temp.c++;
  }
  temp.e.sortbyvalue("sortvalue", "float", false); //Change to true for other way
  for (temp.i: temp.numbers) 
    sendtorc(e[temp.numbers.index(i)]);
works better I suppose...?

Gambet 10-12-2008 07:07 PM
Quote:
Originally Posted by [email protected] (Post 1432164)
works better I suppose...?
Quote:
Originally Posted by Stefan from my Bubble Sort thread
Nice code :)
sortascending()/sortdescending() currently only sort strings, so it's not helping in all cases. You can also use sortbyvalue() but it is more made for sorting objects

Plus, that's definitely not Selection Sort. >_<

Kristi 10-16-2008 05:10 AM
I don't understand why they still waste time with classics like these :P The concept of hashing has pretty much crushed any algorithm that didn't use it before.

Inverness 10-16-2008 07:07 AM
Quote:
Originally Posted by Kristi (Post 1433691)
I don't understand why they still waste time with classics like these :P The concept of hashing has pretty much crushed any algorithm that didn't use it before.
Maybe because smart people teach the basics before moving onto more advanced concepts.


All times are GMT +2. The time now is 06:52 PM.

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