String-Word Inversion

This one is a classic : reverse a string, and reverse the word of the strings, in place, and in linear time.

Cost comparison is caracter exchange. The heart of the algorithm is the reverseWord function, which reverses a word.

The first passe uses N/2 characters exchange, where N is the number of character

The second passe uses W*(w/2) characters exchange, where w is the average length of a word, and W the number of word. This falls back around N/2

Overall Cost is N exchange

<!DOCTYPE html>
<meta charset="utf-8">
<style>

text {
  font: bold 38px monospace;
}

.enter {
  fill: green;
}

.update {
  fill: #333;
}

</style>
<body>
<script src="https://d3js.org/d3.v2.min.js?2.10.1"></script>

var string = "I AM LEARNING SOME ALGORITHMS";
var chars=[];
var initialPos = [];
for (var i=0;i<string.length;i++) {
  chars.push({c:string[i],p:i});

}
var width = 960,
    height = 500;
var transition = null;
var step = 0;
var done = 0;
var animations = [];
var svg = d3.select("body").append("svg")
    .attr("width", width)
    .attr("height", height)
    .append("g")
    .attr("transform", "translate(32," + (height / 2) + ")");

// ALGO REALLY STARTS HERE, WE SUPPOSE THAT WE ARE GIVEN AN ARRAY OF CHARS
reverseWord(chars,0,chars.length-1);
var lo = 0;
console.log(chars);
/// TROUP SI SI
var hi = chars.length-1;

for (i=chars.length-1;i>=0;i--) {
  lo = i;
  if ( chars[i].c !=" ") {
  } else {
    reverseWord(chars,lo,hi);
    hi = i;
    chars[i].c=" ";
  }
}
// reverse last word
hi = hi-1;
reverseWord(chars,lo,hi);
function swap(arr,a,b) {
  step++;
  var temp = arr[a];

arr[a] = arr[b];
  arr[b] = temp;

Modified http://d3js.org/d3.v2.min.js?2.10.1 to a secure url

https://d3js.org/d3.v2.min.js?2.10.1