This site requires JavaScript, please enable it in your browser!
Greenfoot back
Twitter Twitter.hover
JasonZhu
JasonZhu wrote ...

2014/3/23

Help with determining efficiency.

JasonZhu JasonZhu

2014/3/23

#
I have the 3 following sorting algorithms: Bubble Sort:
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void BubbleSort( int [ ] num )
{
     int j;
     boolean flag = true;   // set flag to true to begin first pass
     int temp;   //holding variable
 
     while ( flag )
     {
            flag= false;    //set flag to false awaiting a possible swap
            for( j=0;  j < num.length -1;  j++ )
            {
                   if ( num[ j ] < num[j+1] )   // change to > for ascending sort
                   {
                           temp = num[ j ];                //swap elements
                           num[ j ] = num[ j+1 ];
                           num[ j+1 ] = temp;
                          flag = true;              //shows a swap occurred
                  }
            }
      }
}
Selection Sort:
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void SelectionSort ( int [ ] num )
{
     int i, j, first, temp;
     for ( i = num.length - 1; i > 0; i - - )
     {
          first = 0;   //initialize to subscript of first element
          for(j = 1; j <= i; j ++)   //locate smallest element between positions 1 and i.
          {
               if( num[ j ] < num[ first ] )        
                 first = j;
          }
          temp = num[ first ];   //swap smallest found with element in position i.
          num[ first ] = num[ i ];
          num[ i ] = temp;
      }          
}
And Insertion Sort:
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void InsertionSort( int [ ] num)
{
     int j;                     // the number of items sorted so far
     int key;                // the item to be inserted
     int i;
 
     for (j = 1; j < num.length; j++)    // Start with 1 (not 0)
    {
           key = num[ j ];
           for(i = j - 1; (i >= 0) && (num[ i ] < key); i--)   // Smaller values are moving up
          {
                 num[ i+1 ] = num[ i ];
          }
         num[ i+1 ] = key;    // Put the key in its proper location
     }
}
I want to be able to sort them in order of efficiency. Can someone help me determine the order using n notation? I'm new to the concept. Much appreciated. Thank you in advance!
lordhershey lordhershey

2014/3/23

#
All of these have Big O(n^2) worst case. try a quick search or possibly a heap sort. Bubble sort will always run its worst case, insertion sort will do much better if your list is not too jumbled up. here check out this site http://sorting.at/ is has all of these sorts animated.
JasonZhu JasonZhu

2014/3/23

#
Thank you for the site! It helps a lot.
JasonZhu JasonZhu

2014/3/24

#
Example 1 had a random ordered array: {3,78,9,4,3,6,8,45,7,8,8,5,4,3,42,7,56,82,35,2,63,7,56,8,61,5,1,51,5,13,62,67,47}; Grunt Sort: Big O notation: O(n^2 + n) Example 1: From the average time in five trials, the result was: 47368 nanoseconds. Bubble Sort: O(n^2) Example 1: From the average time in five trials, the result was: 65846 nanoseconds. Selection Sort: O(n^2) Example 1: From the average time in five trials, the result was: 28120 nanoseconds. Insertion Sort: O(n^2) Example 1: From the average time in five trials, the result was: 31896 nanoseconds. Base on the data I've gotten, the time it takes to sort is not representative of the efficiency... I need additional help please.
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void gruntSortList()
{
    long startTime = System.nanoTime();
    int pos = 0;
    int[] tempList = new int[list.length];       
    for(int i=0;i<tempList.length;i++){
        for(int j=0;j<list.length;j++){
            if(list[j]<list[pos]){
                pos=j;
                count++;
            }
        }
        tempList[i]=list[pos];
        list[pos] = 679084;
    }
    for(int i=0;i<list.length;i++){
        list[i] = tempList[i];
        count++;
    }
    long endTime = System.nanoTime();
    System.out.println("Grunt Sort");
    System.out.println("Completed in "+(endTime-startTime)+" nanoseconds");
    System.out.println(count);
}
The grunt sort looks obviously less efficient yet the nanoseconds tell a different story.
lordhershey lordhershey

2014/3/24

#
Here is a quick sort I had punched in using C just to study it:
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
int partition(int *a,int p, int r)
{
  int x = a[p];
  int i = p - 1;
  int j = r + 1;
  int tmp;
  
  while(1)
    {
      for(; !(a[--j] <= x););
      for(; !(a[++i] >= x););
      if (i < j)
    {
      tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
    }
      else
    {
      return (j);
    }
    }
}
  
void quickSort(int *a,int p, int r)
{
  int q;
  if(p < r)
    {
      q = partition(a,p,r);
      quickSort(a,p,q);
      quickSort(a,(q + 1),r);
    }
}
  
int main(int argc, char *argv[])
{
  int a[10];
  int i;
  
  a[0] = 4;
  a[1] = 3;
  a[2] = 8;
  a[3] = 2;
  a[4] = 9;
  a[5] = 1;
  a[6] = 0;
  a[7] = 7;
  a[8] = 5;
  a[9] = 6;
  
  for(i = 0 ; i < 10; i++)
    {
      printf ("%d ",a[i]);
    }
  
  printf("\n");
  
  quickSort(a,0,9);
  
  for(i = 0 ; i < 10; i++)
    {
      printf ("%d ",a[i]);
    }
  
  printf("\n");
}
You may have to do a few adaptations to it - example anywhere you see int *a turn that into int a, you do need to keep the number parameters in the main routine when you call quick sort for the first time use the parameters quicksort(a,0,a.length-1); as this particular algorithm uses the number range as an inclusive range. you could also try the bucket or radix sort - that is a good one especially if you data is limited to integers.
JasonZhu JasonZhu

2014/3/24

#
I'm in need of ordering the efficiency of the algorithms above. I don't need a different algorithm :).
JasonZhu JasonZhu

2014/3/24

#
Something was wrong with Grunt sort in giving a wrong time, it should be the slowest. I've ordered the algorithms from least to most efficient as Grunt, Bubble, Insertion, Selection
lordhershey lordhershey

2014/3/24

#
they can vary in their performance depending on how mixed up the input is. try this as an experiment: give each algorithm a sorted list as input and see what happens, then give them one where the sorted list is in reverse order. This will let you see these algorithms run at their extremes.
JasonZhu JasonZhu

2014/3/24

#
I did 2 examples. Example 1 being a randomly assorted array (same random array) for each sort. Example 2 being a reverse ordered list. I averaged the 2 values in nanoseconds I got to determine the efficiency. Grunt, Bubble, Insertion, Selection Hope I did this properly :)
You need to login to post a reply.