How to animate the following quicksort algorithm in javascript?

Question

I'm trying to learn more about programing and sorting algorithms in general and i wanted to create an animation of a quicksort algorithm using div's with different heights. I've created the sorting algorithm. Running the code snippet will help you understand what i'm trying to do. Here is the code but after the sorting is done it only shows the final result and not the whole process:

function createColumns() {
  $('.column').remove();
  var content = $('#content');
  var columnNumber = $('input:text').val();
  var columnWidth = ((content.width() * 99 / 100) / columnNumber) + 'px';
  for (var i = 0; i < columnNumber; i++) {
    var randomColor = '#' + ('000000' + Math.floor(Math.random() * 16777215).toString(16)).slice(-6);
    var columnHeight = Math.floor(Math.random() * (columnNumber - 1)) + 1;
    $('<div/>', {
      'class': 'column'
    }).css({
      'height': columnHeight + 'px',
      'width': columnWidth,
      'background-color': randomColor
    }).appendTo(content);
  }
}


function quickSort(columns, left, right) {
  var index;
  if (columns.length > 1) {
    index = partition(columns, left, right);
    if (left < (index - 1)) {
      quickSort(columns, left, (index - 1));
    }
    if (index < right) {
      quickSort(columns, index, right);
    }
  }

  return columns;

}

function partition(columns, left, right) {
  var pivot = $(columns[Math.floor((right + left) / 2)]),
    i = left,
    j = right;
  while (i <= j) {
    while ($(columns[i]).height() < pivot.height()) {
      i++
    }
    while ($(columns[j]).height() > pivot.height()) {
      j--;
    }
    if (i <= j) {
      swap(columns, i, j);
      i++;
      j--;
    }
  }
  return i;
}

function swap(columns, firstIndex, secondIndex) {
  var temp, visualTemp;

  visualTemp = columns[secondIndex];
  $(columns[firstIndex]).insertAfter($(columns[secondIndex]));
  $(visualTemp).insertBefore($(columns[firstIndex + 1]));

  temp = columns[firstIndex];
  columns[firstIndex] = columns[secondIndex];
  columns[secondIndex] = temp;
}


$('input').change(function() {
  createColumns();
});

$('#quickSort').click(function() {
  var columns = $('.column');
  var left = 0,
    right = columns.length - 1;

  quickSort(columns, left, right);
});

createColumns();

body {
  padding: 2em;
}

#content {
  width: 100%;
  height: 200px;
  border: 2px solid black;
  position: relative;
  overflow: hidden;
}

.column {
  float: left;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
Number of columns: <input type="text" value="100" />
<div id="content">
</div>
<input type="button" id="quickSort" name="QuickSort" value="Quick Sort">

When I try to run the snippet it keeps telling my createColumns(); is undefined, did you forget to put some code in your snippet? — B. Cratty
– B. Cratty, Commented Oct 29, 2018 at 17:41
The code is probably executed way to fast for you to be able to see the animation. Try adding some kind of delay between steps, for example using a setTimeout for 100 milliseconds each step. This will probably be enough to see the results — VlassisFo
– VlassisFo, Commented Oct 29, 2018 at 17:41
This is not a full solution, but an approach you might consider. Inside swap, add some code that appends the pair of indices to a running list. (You could use a parameter passed through quicksort and partition or a more global variable.) Run the sort, and only then do some animation using this list of swaps. It's a lot less intrusive than trying to modify your algorithm to incorporate animation delays. Of course I leave the animation up to you! :-) — Scott Sauyet
– Scott Sauyet, Commented Oct 29, 2018 at 17:47
If you are looking for something to reference to get some guidance, I was able to find this Sorting.Js — B. Cratty
– B. Cratty, Commented Oct 29, 2018 at 17:48

ksav · Accepted Answer · 2020-11-18 12:04:13Z

3

While it's not quite animated, you can slow the sorting process down a bit if you wrap the internals of your quickSort function in a setTimeout with a small delay (i've chosen 750ms) to see each step.

function createColumns() {
  $('.column').remove();
  var content = $('#content');
  var columnNumber = $('input:text').val();
  var columnWidth = ((content.width() * 99 / 100) / columnNumber) + 'px';
  for (var i = 0; i < columnNumber; i++) {
    var randomColor = '#' + ('000000' + Math.floor(Math.random() * 16777215).toString(16)).slice(-6);
    var columnHeight = Math.floor(Math.random() * (columnNumber - 1)) + 1;
    $('<div/>', {
      'class': 'column'
    }).css({
      'height': columnHeight + 'px',
      'width': columnWidth,
      'background-color': randomColor
    }).appendTo(content);
  }
}


function quickSort(columns, left, right) {
  var index;

  setTimeout(function() {


    if (columns.length > 1) {
      index = partition(columns, left, right);
      if (left < (index - 1)) {

        quickSort(columns, left, (index - 1));
      }
      if (index < right) {
        quickSort(columns, index, right);
      }
    }

    return columns;
  }, 750);

}

function partition(columns, left, right) {
  var pivot = $(columns[Math.floor((right + left) / 2)]),
    i = left,
    j = right;
  while (i <= j) {
    while ($(columns[i]).height() < pivot.height()) {
      i++
    }
    while ($(columns[j]).height() > pivot.height()) {
      j--;
    }
    if (i <= j) {
      swap(columns, i, j);
      i++;
      j--;
    }
  }
  return i;
}

function swap(columns, firstIndex, secondIndex) {
  var temp, visualTemp;

  visualTemp = columns[secondIndex];
  $(columns[firstIndex]).insertAfter($(columns[secondIndex]));
  $(visualTemp).insertBefore($(columns[firstIndex + 1]));

  temp = columns[firstIndex];
  columns[firstIndex] = columns[secondIndex];
  columns[secondIndex] = temp;
}


$('input').change(function() {
  createColumns();
});

$('#quickSort').click(function() {
  var columns = $('.column');
  var left = 0,
    right = columns.length - 1;

  quickSort(columns, left, right);
});

createColumns();

body {
  padding: 2em;
}

#content {
  width: 100%;
  height: 200px;
  border: 2px solid black;
  position: relative;
  overflow: hidden;
}

.column {
  float: left;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
Number of columns: <input type="text" value="100" />
<div id="content">
</div>
<input type="button" id="quickSort" name="QuickSort" value="Quick Sort">

edited Nov 18, 2020 at 12:04

answered Oct 29, 2018 at 17:48

ksav

20.9k6 gold badges52 silver badges69 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Szucs Eduard Over a year ago

I can't believe it was this easy all along. Great answer!

Nimitt Shah Over a year ago

While this code snippet may solve the question, including an explanation really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion.

ksav Over a year ago

@SzucsEduard let me know if you need help with anything else

Collectives™ on Stack Overflow

How to animate the following quicksort algorithm in javascript?

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related