1,105,423 Community Members

Gap Sort

Member Avatar
laidback7
Newbie Poster
6 posts since Oct 2009
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
1
 

I'm trying to implement a gap sort which is a bubble sort that instead of comparing neighboring elements to sort a list, it compares elements 'i' positions apart. I can get the sort to execute the loop once, but I can't figure out how to make my program continue looping until the list is completely sorted. Can anyone help?
Thanks for reading and here is my code:

public static <T extends Comparable<? super T>> void gapSort (T[] data, int i)
   {
      int position, scan;
      T temp;
    	  
      while(i > 0)
      {
    	  for (position = data.length - 1; position >= 0; position--)
    	  {
    		  for (scan = 0; scan <= position - 1; scan++)
    		  {
    			 if (i > scan)
    			 {
    				 if (data[scan].compareTo(data[scan+i]) > 0)
    				 {
    					 /** Swap the values */
    					 temp = data[scan];
    					 data[scan] = data[scan + i];
    					 data[scan + i] = temp;
    				 }
    			 }
    			 else
    			 {
    				 if (data[scan].compareTo(data[scan-i]) < 0)
    				 {
    					 temp = data[scan];
    					 data[scan] = data[scan - i];
    					 data[scan - i] = temp;
    				 }
    			 }
    		 
    		  }
    	  }
    	  i--;
      } 
   }
public class SortPhoneList
{
   /**
    * Creates an array of Contact objects, sorts them, then prints
    * them.
    */
   public static void main (String[] args)
   {
      Contact[] friends = new Contact[7];

      friends[0] = new Contact ("John", "Smith", "610-555-7384");
      friends[1] = new Contact ("Sarah", "Barnes", "215-555-3827");
      friends[2] = new Contact ("Mark", "Riley", "733-555-2969");
      friends[3] = new Contact ("Laura", "Getz", "663-555-3984");
      friends[4] = new Contact ("Larry", "Smith", "464-555-3489");
      friends[5] = new Contact ("Frank", "Phelps", "322-555-2284");
      friends[6] = new Contact ("Marsha", "Grant", "243-555-2837");

      SortingAndSearching.gapSort(friends, 3);

      for (int index = 0; index < friends.length; index++)
         System.out.println (friends[index]);
   }
}
Member Avatar
pavigo
Newbie Poster
1 post since Apr 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 
public static void gapSort (Comparable [] data, int size) {  
int index;
int gap, top;
Comparable temp;
boolean exchanged;
double SF = 1.3;
gap = size;
do {
exchanged = false;
gap = (int) (gap / SF);
if (gap == 0)
gap = 1;
for (index = 1; index <= size - gap; index++) {
if (data [index].compareTo
(data [index + gap]) > 0) {
temp = data [index];
data [index] = data [index + gap];
data [index + gap] = temp;
exchanged = true;
}
}
} while (exchanged || gap > 1);
}
//The algorithm is almost identical to Bubble Sort. If the gap were set to 1, 
////then pure Bubble Sort would result.
You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article