Published September 2, 2018 © GPL3+

QuickSort Algorithm and ESP8266 Web Server

Useful project to help those that need examples for sorting algorithms or web servers using AJAX.

IntermediateProtip1 hour3,242

Things used in this project

Hardware components

Espressif ESP8266 ESP-01

Arduino UNO

Software apps and online services

Arduino IDE

Story

I have recently watched some awesome visualizations of the sorting algorithms on YouTube. QuickSort was my favorite and I thought it would be fun to try to make that algorithm for Arduino. It proved to be very easy so I decided to make a visual representation on ESP8266 web site. Again, I have used Java example to write my code. I have tried to make sorting and web server part easily distinguishable so you can take it apart if you only need one part of it.

Arduino QuickSort Algorithm

Sorting part of the code is quite simple.

int input[] = {60, 153, 12, 13, 116, 10, 199, 54, 108, 198, 103, 115, 180, 169, 1, 26, 170, 97, 130, 71, 193, 44, 7, 72, 152, 166, 81, 19};
int output[sizeof(input) / sizeof(input[0])];
void sort() {
  quickSort(0, (sizeof(output) / sizeof(output[0])) - 1);
}

We prepare our input and output array. Output is needed so our input array in left for resetting of the process when numbers are sorted. After that quickSort is called with size of full array.

void quickSort(int lowerIndex, int higherIndex) {
 int i = lowerIndex;
 int j = higherIndex;
 int pivot = output[lowerIndex + (higherIndex - lowerIndex) / 2];
 while (i <= j) {
   while (output[i] < pivot) {
     i++;
   }
   while (output[j] > pivot) {
     j--;
   }
   if (i <= j) {
     exchangeNumbers(i, j);
     i++;
     j--;
   }
 }
 if (lowerIndex < j)
   quickSort(lowerIndex, j);
 if (i < higherIndex)
   quickSort(i, higherIndex);
}
void exchangeNumbers(int i, int j) {
 int temp = output[i];
 output[i] = output[j];
 output[j] = temp;
}

We need to pick a pivot number and rearrange the numbers so all numbers on the left side of the pivot are lesser than the pivot and greater on the right side.

ESP8266 Web Server

Web server visualization is muck more complicated that sorting.

void buildWebsite() {
 buildJavascript();
 webSite = "<!DOCTYPE HTML>\n";
 webSite += "  <head>\n";
 webSite += "    <title>QuickSort</title>\n";
 webSite +=      javaScript;
 webSite += "  </head>\n";
 webSite += "  <body onload='process()'>\n";
 webSite += "    <div style='height:100px;'></div>\n";
 webSite += "    <div style='text-align:center;'>\n";
 webSite += "      <div id='runtime'></div>\n";
 webSite += "    </div>\n";
 webSite += "    <form action='/' method='post'>";
 webSite += "      <div style='text-align:center;'>\n";
 webSite += "        <div style='height:20px;'></div>\n";
 webSite += "        <input type='submit' name='Sort'>\n";
 webSite += "      </div>\n";
 webSite += "    </form>\n";
 webSite += "  </body>\n";
 webSite += "</HTML>\n";
}

The web page itself is simple. It has only one button that is initiating the sorting procedure and resets if the process is already started. Main JavaScript function is called on page loading. JavaScript is created separately by buildJavascript().

void buildJavascript() {
 javaScript = "<script>\n";
 javaScript += "var xmlHttp=createXmlHttpObject();\n";
 javaScript += "function createXmlHttpObject(){\n";
 javaScript += " if(window.XMLHttpRequest){\n";
 javaScript += "    xmlHttp=new XMLHttpRequest();\n";
 javaScript += " }else{\n";
 javaScript += "    xmlHttp=new ActiveXObject('Microsoft.XMLHTTP');\n";
 javaScript += " }\n";
 javaScript += " return xmlHttp;\n";
 javaScript += "}\n";
 javaScript += "function process(){\n";
 javaScript += " if(xmlHttp.readyState==0 || xmlHttp.readyState==4){\n";
 javaScript += "   xmlHttp.open('PUT','xml',true);\n";
 javaScript += "   xmlHttp.onreadystatechange=handleServerResponse;\n";
 javaScript += "   xmlHttp.send(null);\n";
 javaScript += " }\n";
 javaScript += " setTimeout('process()',33);\n";
 javaScript += "}\n";
 javaScript += "function handleServerResponse(){\n";
 javaScript += " if(xmlHttp.readyState==4 && xmlHttp.status==200){\n";
 javaScript += "   var elem = document.createElement('span');\n";
 javaScript += "   elem.setAttribute('id', 'runtime');\n";
 javaScript += "   elem.innerHTML = this.responseText;\n";
 javaScript += "   document.getElementById('runtime').replaceWith(elem);\n";
 javaScript += " }\n";
 javaScript += "}\n";
 javaScript += "</script>\n";
}

process() is called every 33ms. It requests XML response and places it into the new element that is placed instead of the existing one.

Only that element is updated and not the whole page.

response = "";
     for (int e = 0; e < sizeof(output) / sizeof(output[0]); e ++) {
       String color = "";
       if (e == i || e == j) {
         color = "#00ff00"; // Green
       } else if (e == pivot) {
         color = "#0000ff"; // Blue
       } else {
         color = "#ff0000"; // Red
       }
       response += "<div style='display:inline-block;width:3px;height:";
       response += output[e];
       response += "px;border:1px solid #000;background-color:" + color + ";'>       </div>";
     }

XML response consists of one div element for every number in the array being sorted. Height is determined by values from the array. The green color is used for elements being exchanged and blue is used for pivot number.

 /*
    Quicksort algorithm and esp8266 web server

    Sketch used for sorting int array and visualizing process on the web page


    Created 31 August 2018
    By Dusan Lesan
*/

#include <ESP8266WiFi.h>
#include <ESP8266WebServer.h>

int input[] = {60,  153, 12,  13,  116, 10,  199, 54,  108, 198, 103, 115, 180, 169, 1,   26,  170, 97,  130, 71,
               193, 44,  196, 28,  11,  182, 50,  94,  66,  83,  123, 14,  7,   119, 62,  200, 129, 167, 72,  152,
               166, 81,  19,  68,  132, 157, 37,  149, 144, 64,  113, 176, 88,  36,  23,  75,  96,  192, 21,  98,
               105, 195, 48,  9,   190, 162, 92,  24,  156, 136, 67,  31,  106, 5,   165, 99,  46,  151, 100, 159,
               73,  114, 45,  120, 22,  118, 51,  34,  61,  69,  154, 110, 80,  63,  141, 131, 52,  160, 42,  47,
               38,  91,  16,  82,  93,  179, 78,  186, 189, 145, 6,   17,  181, 178, 163, 49,  150, 183, 53,  111,
               79,  173, 194, 35,  95,  124, 148, 58,  121, 117, 40,  86,  77,  122, 27,  59,  65,  134, 184, 2,
               138, 187, 125, 175, 107, 139, 102, 90,  143, 158, 146, 101, 142, 161, 155, 174, 70,  85,  29,  177,
               43,  171, 41,  140, 76,  127, 188, 8,   109, 191, 3,   30,  197, 33,  15,  57,  32,  74,  133, 135,
               185, 20,  147, 128, 126, 4,   172, 39,  55,  87,  25,  104, 89,  168, 84,  137, 18,  56,  112, 164
              };

int output[sizeof(input) / sizeof(input[0])];

const char* ssid = "networkName"; // WiFi network name
const char* password = "networkPassword"; // WiFi network password

IPAddress espIp(192, 168, 1, 33);
IPAddress gateway(192, 168, 1, 1); // Router IP
IPAddress dns(192, 168, 1, 1);
IPAddress subnet(255, 255, 255, 0);
ESP8266WebServer server(9000);

String webSite, javaScript, response;

void setup() {
  Serial.begin(9600);

  connect(espIp);

  server.on("/", handleWebsite);
  server.on("/xml", handleXML);
  server.begin();

  resetOutput();
}

void loop() {
  server.handleClient();
}

void connect(IPAddress ip) {

  Serial.print("Setting static ip to : ");
  Serial.println(ip);
  WiFi.config(ip, gateway, subnet, dns);

  Serial.print("Connecting to ");
  Serial.print(ssid);
  WiFi.begin(ssid, password);

  Serial.print(" ");
  while (WiFi.status() != WL_CONNECTED) {
    delay(500);
    Serial.print("*");
  }
  Serial.println("");

  Serial.print("WiFi connected to ");
  Serial.println(WiFi.localIP());
}

void handleWebsite() {
  buildWebsite();
  server.send(200, "text/html", webSite);
  if (server.hasArg("Sort")) {
    resetOutput();
    sort();
  }
}

void handleXML() {
  server.send(200, "text/xml", response);
}

void buildWebsite() {
  buildJavascript();
  webSite = "<!DOCTYPE HTML>\n";
  webSite += "  <head>\n";
  webSite += "    <title>QuickSort</title>\n";
  webSite +=      javaScript;
  webSite += "  </head>\n";
  webSite += "  <body onload='process()'>\n";
  webSite += "    <div style='height:100px;'></div>\n";
  webSite += "    <div style='text-align:center;'>\n";
  webSite += "      <div id='runtime'></div>\n";
  webSite += "    </div>\n";
  webSite += "    <form action='/' method='post'>";
  webSite += "      <div style='text-align:center;'>\n";
  webSite += "        <div style='height:20px;'></div>\n";
  webSite += "        <input type='submit' name='Sort'>\n";
  webSite += "      </div>\n";
  webSite += "    </form>\n";
  webSite += "  </body>\n";
  webSite += "</HTML>\n";
}

void buildJavascript() {
  javaScript = "<script>\n";
  javaScript += "var xmlHttp=createXmlHttpObject();\n";
  javaScript += "function createXmlHttpObject(){\n";
  javaScript += " if(window.XMLHttpRequest){\n";
  javaScript += "    xmlHttp=new XMLHttpRequest();\n";
  javaScript += " }else{\n";
  javaScript += "    xmlHttp=new ActiveXObject('Microsoft.XMLHTTP');\n";
  javaScript += " }\n";
  javaScript += " return xmlHttp;\n";
  javaScript += "}\n";
  javaScript += "function process(){\n";
  javaScript += " if(xmlHttp.readyState==0 || xmlHttp.readyState==4){\n";
  javaScript += "   xmlHttp.open('PUT','xml',true);\n";
  javaScript += "   xmlHttp.onreadystatechange=handleServerResponse;\n";
  javaScript += "   xmlHttp.send(null);\n";
  javaScript += " }\n";
  javaScript += " setTimeout('process()',33);\n"; // Request new content every 33ms
  javaScript += "}\n";
  javaScript += "function handleServerResponse(){\n";
  javaScript += " if(xmlHttp.readyState==4 && xmlHttp.status==200){\n";
  javaScript += "   var elem = document.createElement('span');\n";
  javaScript += "   elem.setAttribute('id', 'runtime');\n";
  javaScript += "   elem.innerHTML = this.responseText;\n";
  javaScript += "   document.getElementById('runtime').replaceWith(elem);\n";
  javaScript += " }\n";
  javaScript += "}\n";
  javaScript += "</script>\n";
}

void sort() {
  if ((sizeof(output) / sizeof(output[0])) == 0) {
    return;
  }
  quickSort(0, (sizeof(output) / sizeof(output[0])) - 1);
  response = "";
  for (int e : output) {
    response += "<div style='display:inline-block;width:3px;height:";
    response += e;
    response += "px;border:1px solid #000;background-color:#ff0000;'></div>";
  }
}

void quickSort(int lowerIndex, int higherIndex) {

  int i = lowerIndex;
  int j = higherIndex;

  int pivot = output[lowerIndex + (higherIndex - lowerIndex) / 2]; //  Set middle of selection as pivot number 

  while (i <= j) {
    while (output[i] < pivot) { // Iterate while left side number is lesser than the pivot
      i++;
    }

    while (output[j] > pivot) { // Iterate while right side number is greater than the pivot
      j--;
    }

    if (i <= j) {
      exchangeNumbers(i, j);
      i++; // Move index to the next position on both sides
      j--;
      response = "";
      for (int e = 0; e < sizeof(output) / sizeof(output[0]); e ++) {
        String color = "";
        if (e == i || e == j) {
          color = "#00ff00"; // Green
        } else if (e == pivot) {
          color = "#0000ff"; // Blue
        } else {
          color = "#ff0000"; // Red
        }
        response += "<div style='display:inline-block;width:3px;height:";
        response += output[e];
        response += "px;border:1px solid #000;background-color:" + color + ";'></div>";
      }
      server.handleClient(); // Second handleClient() is needed so the page can be updated while sorting
      delay(100); // Time used to slow down the process for web server visualization
    }
  }
  
  if (lowerIndex < j)  // Call quickSort() method recursively
    quickSort(lowerIndex, j);
  if (i < higherIndex)
    quickSort(i, higherIndex);
}

void exchangeNumbers(int i, int j) {
  int temp = output[i];
  output[i] = output[j];
  output[j] = temp;
}

void copyArray(int* src, int* dst, int len) {
  for (int i = 0; i < len; i++) {
    *dst++ = *src++;
  }
}

void resetOutput() {
  copyArray(input, output, sizeof(input) / sizeof(input[0]));
  for (int e : output) {
    response += "<div style='display:inline-block;width:3px;height:";
    response += e;
    response += "px;border:1px solid #000;background-color:#ff0000;'></div>";
  }
}

int input[] = {60,  153, 12,  13,  116, 10,  199, 54,  108, 198, 103, 115, 180, 169, 1,   26,  170, 97,  130, 71,
               193, 44,  196, 28,  11,  182, 50,  94,  66,  83,  123, 14,  7,   119, 62,  200, 129, 167, 72,  152,
               166, 81,  19,  68,  132, 157, 37,  149, 144, 64,  113, 176, 88,  36,  23,  75,  96,  192, 21,  98,
               105, 195, 48,  9,   190, 162, 92,  24,  156, 136, 67,  31,  106, 5,   165, 99,  46,  151, 100, 159,
               73,  114, 45,  120, 22,  118, 51,  34,  61,  69,  154, 110, 80,  63,  141, 131, 52,  160, 42,  47,
               38,  91,  16,  82,  93,  179, 78,  186, 189, 145, 6,   17,  181, 178, 163, 49,  150, 183, 53,  111,
               79,  173, 194, 35,  95,  124, 148, 58,  121, 117, 40,  86,  77,  122, 27,  59,  65,  134, 184, 2,
               138, 187, 125, 175, 107, 139, 102, 90,  143, 158, 146, 101, 142, 161, 155, 174, 70,  85,  29,  177,
               43,  171, 41,  140, 76,  127, 188, 8,   109, 191, 3,   30,  197, 33,  15,  57,  32,  74,  133, 135,
               185, 20,  147, 128, 126, 4,   172, 39,  55,  87,  25,  104, 89,  168, 84,  137, 18,  56,  112, 164
              };

void setup() {
  Serial.begin(9600);
  sort(0, (sizeof(input) / sizeof(input[0])) - 1);
}

void loop() {
}

void sort(int lowerIndex, int higherIndex) {
  if ((sizeof(input) / sizeof(input[0])) == 0) {
    return;
  }
  quickSort(lowerIndex, higherIndex);
  for (int e = 0; e < sizeof(input) / sizeof(input[0]); e ++) {
    Serial.print(input[e]);
    Serial.print(", ");
  }  
}

void quickSort(int lowerIndex, int higherIndex) {

  int i = lowerIndex;
  int j = higherIndex;

  int pivot = input[lowerIndex + (higherIndex - lowerIndex) / 2]; //  Set middle of selection as pivot number 

  while (i <= j) {
    while (input[i] < pivot) { // Iterate while left side number is lesser than the pivot
      i++;
    }

    while (input[j] > pivot) { // Iterate while right side number is greater than the pivot
      j--;
    }

    if (i <= j) {
      exchangeNumbers(i, j);
      i++; // Move index to the next position on both sides
      j--;
    }
  }
  
  if (lowerIndex < j)  // Call quickSort() method recursively
    quickSort(lowerIndex, j);
  if (i < higherIndex)
    quickSort(i, higherIndex);
}

void exchangeNumbers(int i, int j) {
  int temp = input[i];
  input[i] = input[j];
  input[j] = temp;
}

package Sort;

import java.util.Arrays;

public class Main {

	private int array[];
	private int length;

	public void sort(int[] inputArr) throws InterruptedException {

		if (inputArr == null || inputArr.length == 0) {
			return;
		}
		this.array = inputArr;
		length = inputArr.length;
		quickSort(0, length - 1);
	}

	private void quickSort(int lowerIndex, int higherIndex) throws InterruptedException {

		int i = lowerIndex;
		int j = higherIndex;
		// calculate pivot number, I am taking pivot as middle index number
		int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];

		// Divide into two arrays
		while (i <= j) {
			/**
			 * In each iteration, we will identify a number from left side which 
			 * is greater then the pivot value, and also we will identify a number 
			 * from right side which is less then the pivot value. Once the search 
			 * is done, then we exchange both numbers.
			 */

			while (array[i] < pivot) {
				i++;
			}
			while (array[j] > pivot) {
				j--;
			}

			if (i <= j) {
				exchangeNumbers(i, j);
				//move index to next position on both sides
				i++;
				j--;
			}
		}
		// call quickSort() method recursively
		if (lowerIndex < j)
			quickSort(lowerIndex, j);
		if (i < higherIndex)
			quickSort(i, higherIndex);
	}

	private void exchangeNumbers(int i, int j) throws InterruptedException {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}

	public static void main(String a[]) throws InterruptedException{
		Main sorter = new Main();

		int[] input = {15, 46, 12, 35, 68, 21, 74, 73, 32, 22, 86, 54, 91, 98, 40, 92, 14, 9, 2, 55, 63, 88, 10, 75,
				80, 51, 23, 26, 43, 48, 25, 82, 99, 69, 76, 60, 90, 79, 97, 95, 36, 71, 24, 27, 96, 81, 33, 72, 85,
				8, 64, 42, 84, 47, 78, 20, 19, 29, 4, 45, 6, 7, 66, 34, 58, 56, 50, 53, 93, 89, 44, 17, 100, 5, 13,
				83, 62, 52, 1, 16, 70, 3, 94, 31, 41, 18, 67, 49, 61, 30, 38, 77, 39, 11, 37, 87, 57, 65, 59, 28};
		sorter.sort(input);
		System.out.println(Arrays.toString(input));
	}
}

Credits

Alfodr

2 projects • 3 followers

QuickSort Algorithm and ESP8266 Web Server

Things used in this project

Hardware components

Software apps and online services

Story

Arduino QuickSort Algorithm

ESP8266 Web Server

Code

Quick sort and esp8266 web server

Arduino code

Java code

Credits

Alfodr

Comments

Embed the widget on your own site

QuickSort Algorithm and ESP8266 Web Server

QuickSort Algorithm and ESP8266 Web Server

Things used in this project

Hardware components

Software apps and online services

Story

Arduino QuickSort Algorithm

ESP8266 Web Server

Code

Quick sort and esp8266 web server

Arduino code

Java code

Credits

Alfodr

Comments

Related channels and tags