Mercurial > hg > Members > tatsuki > Alice
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(); } }