Menu
▾
▴
[Algorhythmics-svn] SF.net SVN: algorhythmics:[268] algorhythmicSorting/ofAlgorhythmicSorting/ src
|
From: <mc...@us...> - 2011-01-13 21:44:09
|
Revision: 268
http://algorhythmics.svn.sourceforge.net/algorhythmics/?rev=268&view=rev
Author: mchinen
Date: 2011-01-13 21:44:02 +0000 (Thu, 13 Jan 2011)
Log Message:
-----------
new color scheme to seperate swap and compare.
Modified Paths:
--------------
algorhythmicSorting/ofAlgorhythmicSorting/src/bubble.cpp
algorhythmicSorting/ofAlgorhythmicSorting/src/cleanerinsert.cpp
algorhythmicSorting/ofAlgorhythmicSorting/src/heap.cpp
algorhythmicSorting/ofAlgorhythmicSorting/src/msort.cpp
algorhythmicSorting/ofAlgorhythmicSorting/src/quicksort.cpp
algorhythmicSorting/ofAlgorhythmicSorting/src/shell.cpp
Modified: algorhythmicSorting/ofAlgorhythmicSorting/src/bubble.cpp
===================================================================
--- algorhythmicSorting/ofAlgorhythmicSorting/src/bubble.cpp 2011-01-13 20:58:23 UTC (rev 267)
+++ algorhythmicSorting/ofAlgorhythmicSorting/src/bubble.cpp 2011-01-13 21:44:02 UTC (rev 268)
@@ -26,14 +26,17 @@
// >>>>>>>>>>>>>>>>
// >>>>>>>>>>>>>>>>
-// return p,q in ascending order (swap, when they are not in order)
-void Order(double* p,double* q) { // double datentyp is more precise than float
+// return 0 if no swap, 1 if swap
+//p,q in ascending order (swap, when they are not in order)
+int Order(double* p,double* q) { // double datentyp is more precise than float
double temp; // saves the value
if(*p>*q) { // ie. value at p is 500, value at q is 100
temp=*p; // temp gets 500
*p=*q; // value 100(q) gets transferred to the address where 500 was? q doesnt change
*q=temp; // change q to temps value 500 right now.
+ return 1;
}
+ return 0;
}
//Bubble sorting of integer array A[]
@@ -43,12 +46,11 @@
for (i=0; i<n; i++) {
printseperator(0);
for (j=n-1; i<j; j--){ // nested (verschachtelt) forloop | starts at the end of the array
+ printdoublearray(something, n, i, n - i, j-1, j); // sonification what happens here?
- Order(&something[j-1], &something[j]); // first look and "Order" the last two values of array and then decrement until i (beginning of array)
- // takes same amount of time for best and worst case.
-
- printdoublearray(something, n, i, n - i, j-1, j); // sonification what happens here?
-
+ if (Order(&something[j-1], &something[j]))
+ printdoublearray(something, n, i, n - i, j-1, j);
+
if(SortingMan::Instance()->ShouldStop())
return;
}
Modified: algorhythmicSorting/ofAlgorhythmicSorting/src/cleanerinsert.cpp
===================================================================
--- algorhythmicSorting/ofAlgorhythmicSorting/src/cleanerinsert.cpp 2011-01-13 20:58:23 UTC (rev 267)
+++ algorhythmicSorting/ofAlgorhythmicSorting/src/cleanerinsert.cpp 2011-01-13 21:44:02 UTC (rev 268)
@@ -38,28 +38,26 @@
/* Insert a[i] into the sorted sublist */
int j;
double v = a[i];
-
+
for (j = i - 1; j >= 0; j--)
{
-// printseperator(1);
+ // printseperator(1);
+ printdoublearray(a, length, j, i - j + 1, j, i); // function defined somewhere else
if (a[j] <= v) {
-
- printdoublearray(a, length, j, i - j + 1, j, i); // function defined somewhere else
- break;
+
+ break;
}
a[j + 1] = a[j];
- printdoublearray(a, length, j, i - j + 1, j, j+1); // function defined somewhere else
-
-
+ printdoublearray(a, length, j, i - j + 1, j+1); // function defined somewhere else
+
+
// stopping the loop
- if(SortingMan::Instance()->ShouldStop())
- return;
+ if(SortingMan::Instance()->ShouldStop())
+ return;
}
a[j + 1] = v;
printseperator(0);
- printdoublearray(a, length, j, i - j + 2, j+1, i); // function defined somewhere else
-
-
+ printdoublearray(a, length, j, i - j + 2, j+1); // function defined somewhere else
}
}
//
Modified: algorhythmicSorting/ofAlgorhythmicSorting/src/heap.cpp
===================================================================
--- algorhythmicSorting/ofAlgorhythmicSorting/src/heap.cpp 2011-01-13 20:58:23 UTC (rev 267)
+++ algorhythmicSorting/ofAlgorhythmicSorting/src/heap.cpp 2011-01-13 21:44:02 UTC (rev 268)
@@ -1,17 +1,17 @@
/**************************************************************
- * Sorting an array with the Heapsort method *
- * ----------------------------------------------------------- *
- * REFERENCE: *
- * *
- * "NUMERICAL RECIPES By W.H. Press, B.P. Flannery, *
- * S.A. Teukolsky and W.T. Vetterling, Cambridge *
- * University Press, 1986" [BIBLI 08]. *
- * *
- * C++ version by J-P Moreau *
- * -----------------------------------------------------------
+* Sorting an array with the Heapsort method *
+* ----------------------------------------------------------- *
+* REFERENCE: *
+* *
+* "NUMERICAL RECIPES By W.H. Press, B.P. Flannery, *
+* S.A. Teukolsky and W.T. Vetterling, Cambridge *
+* University Press, 1986" [BIBLI 08]. *
+* *
+* C++ version by J-P Moreau *
+* -----------------------------------------------------------
- * *
- **************************************************************/
+* *
+**************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
@@ -20,18 +20,18 @@
/****************************************************
- * Sorts an array RA of length n in ascending order *
- * by the Heapsort method *
- * ------------------------------------------------- *
- * INPUTS: *
- * n size of table RA *
- * RA table to be sorted *
- * OUTPUT: *
- * RA table sorted in ascending order *
- * *
- * NOTE: The Heapsort method is a N Log2 N routine, *
- * and can be used for very large arrays. *
- ****************************************************/
+* Sorts an array RA of length n in ascending order *
+* by the Heapsort method *
+* ------------------------------------------------- *
+* INPUTS: *
+* n size of table RA *
+* RA table to be sorted *
+* OUTPUT: *
+* RA table sorted in ascending order *
+* *
+* NOTE: The Heapsort method is a N Log2 N routine, *
+* and can be used for very large arrays. *
+****************************************************/
// Heap sort is like selection sort, but uses a heap (max-heap)
@@ -45,71 +45,73 @@
int origchild, orign,origparent;
int depth ;
orign= n;
-
+
while ( 1 )
{
-
+
if ( m ) { // First Part of the Algorithm: Make a max-Heap
parent= --m;
val= data[parent]; // Value, which goes down the heap
-
+
}
else
if ( --n ) { // Teil 2: eigentliche Sortierung
val= data[n]; // zu versickernder Wert vom Heap-Ende
data[n]= data[0]; // Spitze des Heaps hinter den Heap in
parent= 0; // den sortierten Bereich verschieben
+
+ printdoublearray(data, orign,0,0,0,n);//origparent, origchild-origparent);
}
else // Heap ist leer; Sortierung beendet
break;
-
+
origparent=parent;
origchild = parent * WIDTH + 1;
depth =1;
while ( (child= parent * WIDTH + 1) < n ) // erstes Kind;
{ // Abbruch am Ende des Heaps
-
+
printseperator(depth);
-
+
w= n - child < WIDTH ?
- n - child : WIDTH; // Anzahl der vorhandenen Geschwister
-
+ n - child : WIDTH; // Anzahl der vorhandenen Geschwister
+
count += w;
-
- for ( max= 0, i= 1; i < w; ++i ) // größtes Kind suchen
+
+ for ( max= 0, i= 1; i < w; ++i ) { // größtes Kind suchen
+ printdoublearray(data,orign,child, w, child+max, child+i);
if ( data[child+i] > data[child+max] )
{
- printdoublearray(data,orign,0,0, child+i, child+max);
max= i;
}
- else
- {
- printdoublearray(data,orign,0,0, child+i, child+max);
- }
+ }
child += max;
+
+ printdoublearray(data, orign,0,0,child, parent);//origparent, origchild-origparent);
if ( data[child] <= val ) // kein Kind mehr größer als der
break; // zu versickernde Wert
-
+
data[parent]= data[child]; // größtes Kind nach oben rücken
-
-
+ printdoublearray(data, orign,0,0,parent, child);//origparent, origchild-origparent);
+
+
if(SortingMan::Instance()->ShouldStop())
return 1;
-
+
parent= child; // in der Ebene darunter weitersuchen
depth++;//for our print/sonification
}
-
+
data[parent]= val; // versickerten Wert eintragen
+ printdoublearray(data, orign,0,0,parent,-1);
if(parent-origchild>0) {
printseperator(0);
- printdoublearray(data, orign,0,0,parent,-1);//origparent, origchild-origparent);
}
}
-
+
return count;
}
@@ -118,7 +120,7 @@
// Labels: e10, e20
int i,ir,j,l;
double rra;
-
+
l=(n/2)+1;
ir=n;
//The index L will be decremented from its initial value during the
@@ -134,15 +136,15 @@
rra=RA[ir];
RA[ir]=RA[1];
printdoublearray(RA, n,1,1);
-
+
if(SortingMan::Instance()->ShouldStop())
return;
-
+
ir--;
if (ir==1) {
RA[1]=rra;
printdoublearray(RA, n,1,1);
-
+
return;
}
}
@@ -155,11 +157,11 @@
if (rra < RA[j]) {
RA[i]=RA[j];
printdoublearray(RA, n,i,1);
-
+
if(SortingMan::Instance()->ShouldStop())
return;
-
-
+
+
i=j; j=j+j;
}
else
@@ -168,5 +170,5 @@
}
RA[i]=rra;
goto e10;
-
+
}
\ No newline at end of file
Modified: algorhythmicSorting/ofAlgorhythmicSorting/src/msort.cpp
===================================================================
--- algorhythmicSorting/ofAlgorhythmicSorting/src/msort.cpp 2011-01-13 20:58:23 UTC (rev 267)
+++ algorhythmicSorting/ofAlgorhythmicSorting/src/msort.cpp 2011-01-13 21:44:02 UTC (rev 268)
@@ -1,30 +1,30 @@
/*********************************************************
- * Demonstration Program of In-place Merge Sorting *
- * (about n*n comparisons used with no extra storage). *
- * ------------------------------------------------------ *
- * Reference: After a java algorithm By Jason Harrison, *
- * 1995 University of British Columbia. *
- * *
- * C++ Version By J-P Moreau, Paris. *
- * ------------------------------------------------------ *
- * *
- *********************************************************/
+* Demonstration Program of In-place Merge Sorting *
+* (about n*n comparisons used with no extra storage). *
+* ------------------------------------------------------ *
+* Reference: After a java algorithm By Jason Harrison, *
+* 1995 University of British Columbia. *
+* *
+* C++ Version By J-P Moreau, Paris. *
+* ------------------------------------------------------ *
+* *
+*********************************************************/
#include <stdio.h>
#include <math.h>
#include "sorthelp.h"
- #include "SortingMan.h"
+#include "SortingMan.h"
/*****************************************************
- * In-place sorting of a table a[] in ascending order *
- * -------------------------------------------------- *
- * Inputs: *
- * a : Table of n real numbers *
- * lo: Starting index (>=0) *
- * hi: Ending index (<=n-1), with lo<hi. *
- * Output: *
- * a : Table sorted in ascending order. *
- *****************************************************/
+* In-place sorting of a table a[] in ascending order *
+* -------------------------------------------------- *
+* Inputs: *
+* a : Table of n real numbers *
+* lo: Starting index (>=0) *
+* hi: Ending index (<=n-1), with lo<hi. *
+* Output: *
+* a : Table sorted in ascending order. *
+*****************************************************/
// >>>>>>>>>>>>>>>>
// >>>>>>>>>>>>>>>>
@@ -35,90 +35,87 @@
void sort(double *a, int lo, int hi, int depth ) { // lo=0, hi=n-1 (only for the first call)
- // lo and hi are index
-
- static double* original;
- static int originalsize;
+ // lo and hi are index
- if(SortingMan::Instance()->ShouldStop())
- return;
+ static double* original;
+ static int originalsize;
- if(depth==0){
-
- original = a;
- originalsize = hi+1;
- }
-
-// >>>>>>>>>>>>>>>>
-
- if (lo>=hi) return; // no action if the array is already sorted
-
- int mid = (lo + hi) / 2; // for example 9 / 2 = 4.5 >> 4
-
- // Recursion breaks up the array in to smaller pieces before they are going to be sorted!
-
- // Partition the list into two lists and sort them recursively
- sort(a, lo, mid, depth+1); // compare with void sort(double *a, int lo, int hi, bool toplevel)
- sort(a, mid + 1, hi, depth+1);
-
-
- // Merge the two sorted lists
- int start_hi = mid + 1;
- int end_lo = mid;
-
- // [2,3] [5,4] [0,5] [4,6] >> 2 at index 3, 5 at index 4 ...
- // code which is run on each piece of the whole array
- while ((lo <= end_lo) && (start_hi <= hi)) {
- printseperator(depth);
- if (a[lo] < a[start_hi]) // if value of array a at index lo is smaller value at start-hi
-
-
-
+ if(SortingMan::Instance()->ShouldStop())
+ return;
+
+ if(depth==0){
+
+ original = a;
+ originalsize = hi+1;
+ }
+
+ // >>>>>>>>>>>>>>>>
+
+ if (lo>=hi) return; // no action if the array is already sorted
+
+ int mid = (lo + hi) / 2; // for example 9 / 2 = 4.5 >> 4
+
+ // Recursion breaks up the array in to smaller pieces before they are going to be sorted!
+
+ // Partition the list into two lists and sort them recursively
+ sort(a, lo, mid, depth+1); // compare with void sort(double *a, int lo, int hi, bool toplevel)
+ sort(a, mid + 1, hi, depth+1);
+
+
+ // Merge the two sorted lists
+ int start_hi = mid + 1;
+ int end_lo = mid;
+
+ // [2,3] [5,4] [0,5] [4,6] >> 2 at index 3, 5 at index 4 ...
+ // code which is run on each piece of the whole array
+ while ((lo <= end_lo) && (start_hi <= hi)) {
+ printseperator(depth);
+ printdoublearray(original, originalsize, lo, (start_hi-lo)+1, lo, start_hi); // Sonification
+ if (a[lo] < a[start_hi]) // if value of array a at index lo is smaller value at start-hi
{
-
- printdoublearray(original, originalsize, lo, (start_hi-lo)+1, lo, start_hi); // Sonification
- //blue means a[lo] < a[start_hi]. lo = first value of a chunk
-
- lo++; // lo gets incremented
-
-
+
+ //blue means a[lo] < a[start_hi]. lo = first value of a chunk
+
+ lo++; // lo gets incremented
+
+
}
-
- else {
-
- // a[lo] >= a[start_hi]
-
- // The next element comes from the second list,
- // move the a[start_hi] element into the next
- // position and shuffle all the other elements up.
-
- double T = a[start_hi]; // [2,3] [5,4] [0,5] [4,6]
-
- // 0 (the value at index 5) goes to a storage called T
-
-
- for (int k = start_hi-1; k >= lo; k--) { // count down from start-1 to lo
- a[k+1] = a[k]; // [2,3] [5,4] [<0>,5] [4,6] >> [2,3] [5,4] [<5>,5] [4,6]
- // = is like arrow pointing to left
-
- // makes a line of red values, because all values change
-
- }
-
- a[lo] = T;
-
+
+ else {
+
+ // a[lo] >= a[start_hi]
+
+ // The next element comes from the second list,
+ // move the a[start_hi] element into the next
+ // position and shuffle all the other elements up.
+
+ double T = a[start_hi]; // [2,3] [5,4] [0,5] [4,6]
+
+ // 0 (the value at index 5) goes to a storage called T
+
+
+ for (int k = start_hi-1; k >= lo; k--) { // count down from start-1 to lo
+ a[k+1] = a[k]; // [2,3] [5,4] [<0>,5] [4,6] >> [2,3] [5,4] [<5>,5] [4,6]
+ // = is like arrow pointing to left
+
+ // makes a line of red values, because all values change
+
+ }
+
+ a[lo] = T;
+
//print and play as an array segment instaid of a pair since the above for loop moves as a chunk (like memcpy)
- printdoublearray(original, originalsize, lo, (start_hi-lo)+1); // Sonification
-
- //
-
- lo++;
- end_lo++;
- start_hi++;
-
- }
+ printdoublearray(original, originalsize, lo, (start_hi-lo)+1); // Sonification
- if(SortingMan::Instance()->ShouldStop())
- return;
- }
+ //
+
+ lo++;
+ end_lo++;
+ start_hi++;
+
+ }
+
+ if(SortingMan::Instance()->ShouldStop())
+ return;
+ }
}
\ No newline at end of file
Modified: algorhythmicSorting/ofAlgorhythmicSorting/src/quicksort.cpp
===================================================================
--- algorhythmicSorting/ofAlgorhythmicSorting/src/quicksort.cpp 2011-01-13 20:58:23 UTC (rev 267)
+++ algorhythmicSorting/ofAlgorhythmicSorting/src/quicksort.cpp 2011-01-13 21:44:02 UTC (rev 268)
@@ -34,6 +34,8 @@
j--;
}
+
+ printdoublearray(arr,orign, low, high - low, i, j);
if(i <= j) {
/* swap two elements */
y = arr[i];
@@ -43,9 +45,6 @@
i++;
j--;
- }else
- {
- printdoublearray(arr,orign, low, high - low, i, j);
}
if(SortingMan::Instance()->ShouldStop())
Modified: algorhythmicSorting/ofAlgorhythmicSorting/src/shell.cpp
===================================================================
--- algorhythmicSorting/ofAlgorhythmicSorting/src/shell.cpp 2011-01-13 20:58:23 UTC (rev 267)
+++ algorhythmicSorting/ofAlgorhythmicSorting/src/shell.cpp 2011-01-13 21:44:02 UTC (rev 268)
@@ -57,6 +57,7 @@
e10: l=i+m;
//if(j!=1)
// printseperator(1);
+ printdoublearray(realArray, n,i-1,1,i-1,l-1);
if (ARR[l] < ARR[i]) {
t=ARR[i];
ARR[i]=ARR[l];
@@ -67,9 +68,6 @@
printdoublearray(realArray, n,i-1,1,i-1,l-1);
i=i-m;
if (i >= 1) goto e10;
- }else
- {
- printdoublearray(realArray, n,i-1,1,i-1,l-1);
}
}
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
