QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
- Always pick first element as pivot.
- Always pick last element as pivot.
- Pick a random element as pivot.
- Pick median as pivot.
Approach:
- Firstly take an array of random values.
- Draw rectangle side-by-side according to the values at that array’s index.
- Implement QuickSort Algorithm in p5.js.
- Assign time delays in order to visualise the changes made at each successive stage.
Example:
<!DOCTYPE html> <html>   <head>     <meta charset="UTF-8">           <title>QuickSort Sorting Algorithm</title>           <script src=     type="text/javascript"></script>           <style>         body {             padding: 0;             margin: 0;         }         canvas {             vertical-align: top;         }     </style> </head>   <body>     <script type="text/javascript">                   // Assign Global Values         let values = [];         let w = 20;         let states = [];         function setup() {                       // Create Canvas of given Size             createCanvas(800, 500);                       // Assign Array of Random Values             values = new Array(floor(width/w));                           for(let i = 0; i < values.length; i++) {                 values[i] = float(random(height));                 states[i] = -1;             }                           // To print values to Browser's Console             print("Unsorted Array:" + values);                           // Invoke QuickSort Function             quickSort(values, 0, values.length);                           print("Sorted Array:" + values);         }                   // Asynchronous Definition of Quick Sort Function         async function quickSort(arr, start, end) {             if(start >= end) {                 return;             }             let index = await partition(arr, start, end);             states[index] = -1;                           // Promise.all is used so that each function             // should invoke simultaneously             await Promise.all([quickSort(arr, start, index-1),                     quickSort(arr, index+1, end)]);         }                   // Asynchronous Definition of Partition Function         async function partition(arr, start, end) {                           for(let i = start; i< end; i++) {                 states[i] = 1;             }                           let pivotIndex = start;             let pivotValue = arr[end];             states[pivotIndex] = 0;                           for(let i = start; i < end; i++) {                 if(arr[i]<pivotValue) {                     await swap(arr, i, pivotIndex);                     states[pivotIndex] = -1;                     pivotIndex++;                     states[pivotIndex] = 0;                 }             }                           await swap(arr, pivotIndex, end);                               for(let i = start; i < end; i++) {                     states[i] = -1;                 }                           return pivotIndex;         }                   // Definition of Draw function         function draw() {                           // Set Background Color             background(51);                           for(let i = 0; i < values.length; i++) {                 stroke(0);                 fill(255);                                   if(states[i] == 0) {                                       // Pivot Element                     fill(255, 0, 0);                 }                 else if (states[i]==1) {                     // Sorting bar                     fill("#58FA82");                 }                 else {                     // Sorted Bars                     fill(255);                 }                                   rect(i*w, height - values[i], w, values[i]);             }         }                   async function swap(arr, a, b) {                           // Call to sleep function             await sleep(100);             let t = arr[a];             arr[a] = arr[b];             arr[b] = t;         }                   // Definition of sleep function         function sleep(ms) {             return new Promise(resolve                     => setTimeout(resolve, ms));         }     </script> </body>   </html>                    |
Output:
Whether you’re preparing for your first job interview or aiming to upskill in this ever-evolving tech landscape, neveropen Courses are your key to success. We provide top-quality content at affordable prices, all geared towards accelerating your growth in a time-bound manner. Join the millions we’ve already empowered, and we’re here to do the same for you. Don’t miss out – check it out now!
