-
Notifications
You must be signed in to change notification settings - Fork 0
/
quick_sort.js
75 lines (58 loc) · 2.43 KB
/
quick_sort.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
function Quick()
{
//Setting Time complexities
document.getElementById("Time_Worst").innerText="O(N^2)";
document.getElementById("Time_Average").innerText="Θ(N log N)";
document.getElementById("Time_Best").innerText="Ω(N log N)";
//Setting Space complexity
document.getElementById("Space_Worst").innerText="O(log N)";
c_delay=0;
quick_sort(0,array_size-1);
enable_buttons();
}
function quick_partition (start, end)
{
var i = start + 1;
var piv = div_sizes[start] ;//make the first element as pivot element.
div_update(divs[start],div_sizes[start],"yellow");//Color update
for(var j =start + 1; j <= end ; j++ )
{
//re-arrange the array by putting elements which are less than pivot on one side and which are greater that on other.
if (div_sizes[ j ] < piv)
{
div_update(divs[j],div_sizes[j],"yellow");//Color update
div_update(divs[i],div_sizes[i],"red");//Color update
div_update(divs[j],div_sizes[j],"red");//Color update
var temp=div_sizes[i];
div_sizes[i]=div_sizes[j];
div_sizes[j]=temp;
div_update(divs[i],div_sizes[i],"red");//Height update
div_update(divs[j],div_sizes[j],"red");//Height update
div_update(divs[i],div_sizes[i],"blue");//Height update
div_update(divs[j],div_sizes[j],"blue");//Height update
i += 1;
}
}
div_update(divs[start],div_sizes[start],"red");//Color update
div_update(divs[i-1],div_sizes[i-1],"red");//Color update
var temp=div_sizes[start];//put the pivot element in its proper place.
div_sizes[start]=div_sizes[i-1];
div_sizes[i-1]=temp;
div_update(divs[start],div_sizes[start],"red");//Height update
div_update(divs[i-1],div_sizes[i-1],"red");//Height update
for(var t=start;t<=i;t++)
{
div_update(divs[t],div_sizes[t],"green");//Color update
}
return i-1;//return the position of the pivot
}
function quick_sort (start, end )
{
if( start < end )
{
//stores the position of pivot element
var piv_pos = quick_partition (start, end ) ;
quick_sort (start, piv_pos -1);//sorts the left side of pivot.
quick_sort (piv_pos +1, end) ;//sorts the right side of pivot.
}
}