changeset 161:1a84834ba33a working

add bubble sort
author sugi
date Wed, 12 Dec 2012 16:23:39 +0900
parents e5837e1d242f
children 7f8a3680a35c
files src/alice/test/codesegment/local/bitonicsort/EvenPhase.java src/alice/test/codesegment/local/bitonicsort/OddPhase.java src/alice/test/codesegment/local/bitonicsort/SetTask.java
diffstat 3 files changed, 47 insertions(+), 27 deletions(-) [+]
line wrap: on
line diff
--- a/src/alice/test/codesegment/local/bitonicsort/EvenPhase.java	Wed Dec 12 00:20:25 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/EvenPhase.java	Wed Dec 12 16:23:39 2012 +0900
@@ -101,12 +101,11 @@
 	}
 	
 	public List<Integer> quickSort(List<Integer> numbers){
-		if (numbers.size() < 1) 
+		//if (numbers.size() < 1) return numbers;
+		if (numbers.size() < 400){
+			bubbleSort(numbers);	
 			return numbers;
-		/*if (numbers.size() < 400){ 
-			return bubbleSort(numbers);
-			
-		} */
+		}
 		int pivot = numbers.size() / 2;
 		List<Integer> lesser = new LinkedList<Integer>();
 		List<Integer> greater = new LinkedList<Integer>();
@@ -133,14 +132,13 @@
 		return sorted;
 	}
 	
-	public List<Integer> quickSort(List<Integer> numbers1, 
-			List<Integer> numbers2){
-		if (numbers1.size() < 1) 
+	public List<Integer> quickSort(List<Integer> numbers1,List<Integer> numbers2){
+		//if (numbers1.size() < 1) return numbers1;
+		if (numbers1.size() + numbers2.size()< 400){
+			numbers1.addAll(numbers2);
+			bubbleSort(numbers1);
 			return numbers1;
-		/*if (numbers.size() < 400){ 
-			return bubbleSort(numbers);
-			
-		} */
+		}
 		int pivot = numbers1.size() / 2;
 		List<Integer> lesser = new LinkedList<Integer>();
 		List<Integer> greater = new LinkedList<Integer>();
@@ -175,8 +173,19 @@
 		return sorted;
 	}
 	
-	public List<Integer> bubbleSort(List<Integer> numbers){
-		List<Integer> sorted = new LinkedList<Integer>();
-		return sorted;
+	public void bubbleSort(List<Integer> numbers){
+		for (int i=0;i<numbers.size()-1;i++){
+			for (int j=numbers.size()-1;j>i;j--){
+				if (numbers.get(i) > numbers.get(j)){
+					swap(numbers,i,j);
+				}
+			}
+		}
+	}
+	
+	public <T> void swap(List<T> list,int index1,int index2){
+		T tmp=list.get(index1);
+		list.set(index1,list.get(index2));
+		list.set(index2, tmp);
 	}
 }
--- a/src/alice/test/codesegment/local/bitonicsort/OddPhase.java	Wed Dec 12 00:20:25 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/OddPhase.java	Wed Dec 12 16:23:39 2012 +0900
@@ -149,14 +149,13 @@
 		return sorted;
 	}
 	
-	public List<Integer> quickSort(List<Integer> numbers1, 
-			List<Integer> numbers2){
-		if (numbers1.size() < 1) 
+	public List<Integer> quickSort(List<Integer> numbers1, List<Integer> numbers2){
+		//if (numbers1.size() < 1) return numbers1;
+		if (numbers1.size() + numbers2.size()< 400){
+			numbers1.addAll(numbers2);
+			bubbleSort(numbers1);
 			return numbers1;
-		/*if (numbers.size() < 400){ 
-			return bubbleSort(numbers);
-			
-		} */
+		}
 		int pivot = numbers1.size() / 2;
 		List<Integer> lesser = new LinkedList<Integer>();
 		List<Integer> greater = new LinkedList<Integer>();
@@ -191,8 +190,19 @@
 		return sorted;
 	}
 	
-	public List<Integer> bubbleSort(List<Integer> numbers){
-		List<Integer> sorted = new LinkedList<Integer>();
-		return sorted;
+	public void bubbleSort(List<Integer> numbers){
+		for (int i=0;i<numbers.size()-1;i++){
+			for (int j=numbers.size()-1;j>i;j--){
+				if (numbers.get(i) > numbers.get(j)){
+					swap(numbers,i,j);
+				}
+			}
+		}
+	}
+	
+	public <T> void swap(List<T> list,int index1,int index2){
+		T tmp=list.get(index1);
+		list.set(index1,list.get(index2));
+		list.set(index2, tmp);
 	}
 }
--- a/src/alice/test/codesegment/local/bitonicsort/SetTask.java	Wed Dec 12 00:20:25 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/SetTask.java	Wed Dec 12 16:23:39 2012 +0900
@@ -5,7 +5,7 @@
 import alice.datasegment.Receiver;
 
 public class SetTask extends CodeSegment {
-	
+	public static long t;
 	private Receiver info1 = ids.create(CommandType.PEEK);
 	private Receiver info2 = ids.create(CommandType.TAKE);
 	
@@ -43,9 +43,10 @@
 			ods.update("local", key+i, list.createDataList(i*block_num, last_block_num));
 			ods.update("local", "count"+i, 0);
 			new OddPhase("range"+i,key+i,0,"count"+i);
+			System.out.println(i);
 			new ShowData(i);
 		}
-		
+		t = System.currentTimeMillis();
 	}
 
 }