Skip to content

Commit d242c09

Browse files
https-samhttps-sam
committed
Heap Sort implemented
1 parent 64d0ce4 commit d242c09

4 files changed

Lines changed: 131 additions & 14 deletions

File tree

‎src/components/Animation/Animation.js‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,9 +28,12 @@ class Animation {
2828

2929
/**
3030
* takes indecies to be swapped
31+
* and swaps them in the dom tree
32+
* modifies: height, id, data (height value to be displayed in bar)
3133
* @param {Integer} i
3234
* @param {Integer} k
3335
*/
36+
3437
static swap(i, k) {
3538
let unSortedBars = document.querySelectorAll('.array-bars');
3639
var oldHeight = unSortedBars[k].style.height;

‎src/components/Canvas/AlgorithmSelection.js‎

Lines changed: 30 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,7 @@ import { MergeSort } from '../Strategy/Algorithms/MergeSort';
44
import { RadixSortLSD } from '../Strategy/Algorithms/RadixSortLSD';
55
import { QuickSort } from '../Strategy/Algorithms/QuickSort.js'
66
import SelectionSort from '../Strategy/Algorithms/SelectionSort';
7+
import { HeapSort } from '../Strategy/Algorithms/Heapsort';
78
function AlgorithmSelection({strategy, options}) {
89

910
const [currentAlgo, setCurrentAlgo] = useState(options.state.algorithm);
@@ -12,6 +13,7 @@ function AlgorithmSelection({strategy, options}) {
1213
const Merge = new MergeSort();
1314
const Selection = new SelectionSort();
1415
const Quick = new QuickSort();
16+
const Heap = new HeapSort();
1517

1618

1719
useEffect(() => {
@@ -29,6 +31,7 @@ function AlgorithmSelection({strategy, options}) {
2931
else if(currentAlgo === "Merge") strategy.setStrategy = Merge;
3032
else if(currentAlgo === "Selection") strategy.setStrategy = Selection;
3133
else if(currentAlgo === "Quick") strategy.setStrategy = Quick;
34+
else if(currentAlgo === "Heap") strategy.setStrategy = Heap;
3235
}, [])
3336

3437

@@ -55,6 +58,18 @@ function AlgorithmSelection({strategy, options}) {
5558
>
5659
<p className={`${currentAlgo === 'Radix' && 'text-black group-hover:text-white'}`}>Radix Sort</p>
5760
</div>
61+
62+
<div className={`${currentAlgo === 'Heap' && 'bg-gray-200'} group cursor-pointer w-full hover:bg-gray-700 font-semibold text-white h-[2.8em] flex items-center justify-start pl-4`}
63+
onClick={() => {
64+
setCurrentAlgo('Heap');
65+
options.setState({algorithm: "Heap"});
66+
strategy.setStrategy = Heap;
67+
localStorage.setItem("algorithm", "Heap");
68+
setShowDropdown(!showDropdown)
69+
}}
70+
>
71+
<p className={`${currentAlgo === 'Heap' && 'text-black group-hover:text-white'}`}>Heap Sort</p>
72+
</div>
5873

5974
<div className={`${currentAlgo === 'Merge' && 'bg-gray-200'} group cursor-pointer w-full hover:bg-gray-700 font-semibold text-white h-[2.8em] flex items-center justify-start pl-4`}
6075
onClick={() => {
@@ -66,9 +81,22 @@ function AlgorithmSelection({strategy, options}) {
6681
}}
6782
>
6883
<p className={`${currentAlgo === 'Merge' && 'text-black group-hover:text-white'}`}>Merge Sort</p>
69-
7084
</div>
71-
<div className={`${currentAlgo === 'Selection' && 'bg-gray-200'} group cursor-pointer w-full hover:bg-gray-700 font-semibold text-white h-[2.8em] flex items-center justify-start pl-4`}
85+
86+
<div className={`${currentAlgo === 'Quick' && 'bg-gray-200'} group cursor-pointer w-full hover:bg-gray-700 font-semibold text-white h-[2.8em] flex items-center justify-start pl-4`}
87+
onClick={() => {
88+
setCurrentAlgo('Quick');
89+
options.setState({algorithm: "Quick"});
90+
strategy.setStrategy = Quick;
91+
localStorage.setItem("algorithm", "Quick");
92+
setShowDropdown(!showDropdown)
93+
}}
94+
>
95+
<p className={`${currentAlgo === 'Quick' && 'text-black group-hover:text-white'}`}>Quick Sort</p>
96+
</div>
97+
98+
99+
<div className={`${currentAlgo === 'Selection' && 'bg-gray-200'} group cursor-pointer w-full rounded-b-md hover:bg-gray-700 font-semibold text-white h-[2.8em] flex items-center justify-start pl-4`}
72100
onClick={() => {
73101
setCurrentAlgo('Selection');
74102
options.setState({algorithm: "Selection"});
@@ -80,17 +108,6 @@ function AlgorithmSelection({strategy, options}) {
80108
<p className={`${currentAlgo === 'Selection' && 'text-black group-hover:text-white'}`}>Selection Sort</p>
81109

82110
</div>
83-
<div className={`${currentAlgo === 'Quick' && 'bg-gray-200'} group cursor-pointer w-full hover:bg-gray-700 rounded-b-md font-semibold text-white h-[2.8em] flex items-center justify-start pl-4`}
84-
onClick={() => {
85-
setCurrentAlgo('Quick');
86-
options.setState({algorithm: "Quick"});
87-
strategy.setStrategy = Quick;
88-
localStorage.setItem("algorithm", "Quick");
89-
setShowDropdown(!showDropdown)
90-
}}
91-
>
92-
<p className={`${currentAlgo === 'Quick' && 'text-black group-hover:text-white'}`}>Quick Sort</p>
93-
</div>
94111
</div>
95112
</div>
96113
)

‎src/components/Canvas/Description/SortingCanvasDescription.js‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,6 @@ import NormalParagraph from './NormalParagraph'
1010
import { InputHandler } from '../../InputHandler/InputHandler'
1111

1212

13-
1413
function SortingCanvasDescription() {
1514
return (
1615
<div className="z-10 self-center font-sans max-w-[90vw] text-gray-700 dark:text-white mt-10 md:mt-0 md:pt-0">

‎src/components/Strategy/Algorithms/Heapsort.js‎

Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,98 @@
1+
import { Animation } from "../../Animation/Animation"
2+
3+
4+
class HeapSort {
5+
6+
constructor() {
7+
this.options = null;
8+
}
9+
10+
getIndexDOM(element, DOM) {
11+
for(const e of DOM) {
12+
if(element === parseInt(e.id)) return DOM.indexOf(e);
13+
}
14+
}
15+
16+
async heapify(array, n, i) {
17+
let max = i;
18+
let left = (2 * i) + 1;
19+
let right = (2 * i) + 2;
20+
let DOM = Array.from(document.querySelectorAll('.array-bars'));
21+
let currentBar = this.getIndexDOM(array[i], DOM);
22+
23+
// SG 07/15/2022 14:06 making sure that the last bar - when n = 1, is not colored
24+
if(n > 2) {
25+
DOM[currentBar].style.backgroundColor = this.options.processingColor;
26+
27+
}
28+
29+
if(left < n && array[left] > array[max]) {
30+
max = left;
31+
}
32+
33+
if(right < n && array[right] > array[max]) {
34+
max = right;
35+
}
36+
37+
if(max !== i) {
38+
// SG 07/15/2022 13:23 swapping, sorted
39+
let first = this.getIndexDOM(array[i], DOM);
40+
let second = this.getIndexDOM(array[max], DOM);
41+
42+
if(!this.options.skipJ) {
43+
await Animation.getAnimation(this.options.delay);
44+
}
45+
46+
Animation.swap(first, second);
47+
48+
let temp = array[i];
49+
array[i] = array[max];
50+
array[max] = temp;
51+
52+
await this.heapify(array, n, max);
53+
}
54+
55+
// SG 07/15/2022 14:06 making sure that the last bar - when n = 1, is not colored
56+
if(n > 2) {
57+
DOM[currentBar].style.backgroundColor = this.options.defaultBarColor;
58+
}
59+
}
60+
61+
async heapSort(array, n) {
62+
for(let i = Math.floor(n / 2) - 1; i >= 0; i--) {
63+
await this.heapify(array, n, i);
64+
}
65+
66+
for(let i = n - 1; i >= 0; i--) {
67+
let DOM = Array.from(document.querySelectorAll('.array-bars'));
68+
69+
// SG 07/15/2022 13:20 swaping value to the end
70+
let first = this.getIndexDOM(array[0], DOM);
71+
let second = this.getIndexDOM(array[i], DOM);
72+
await Animation.getAnimation(this.options.delay);
73+
Animation.swap(first, second);
74+
console.log(this.options.sortedBarColor)
75+
76+
// SG 07/15/2022 13:52 coloring sorted bars
77+
DOM[second].style.backgroundColor = this.options.sortedBarColor;
78+
79+
80+
let temp = array[0];
81+
array[0] = array[i];
82+
array[i] = temp;
83+
84+
await this.heapify(array, i , 0);
85+
}
86+
87+
return array;;
88+
}
89+
90+
perform(options, array) {
91+
this.options = options;
92+
console.log(this.heapSort(array, array.length));
93+
}
94+
}
95+
96+
97+
98+
export { HeapSort }

0 commit comments

Comments
 (0)