Quick Sort
Quicksort has a couple of other differences from merge sort. Quicksort works in place. And its worst-case running time is as bad as selection sort's and insertion sort's: . But its average-case running time is as good as merge sort's: . So why think about quicksort when merge sort is at least as good? That's because the constant factor hidden in the big-Θ notation for quicksort is quite good. In practice, quicksort outperforms merge sort, and it significantly outperforms selection sort and insertion sort.var quickSort = function(array, p, r) {
if(p<r){
var q = partition(array,p,r);
quickSort(array,p,q-1);
quickSort(array,q+1,r);
}
};
Challenge: implement partition
// Swaps two items in an array, changing the original arrayvar swap = function(array, firstIndex, secondIndex) {
var temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
};
var partition = function(array, p, r) {
// Compare array[j] with array[r], for j = p, p+1,...r-1
// maintaining that:
// array[p..q-1] are values known to be <= to array[r]
// array[q..j-1] are values known to be > array[r]
// array[j..r-1] haven't been compared with array[r]
// If array[j] > array[r], just increment j.
// If array[j] <= array[r], swap array[j] with array[q],
// increment q, and increment j.
// Once all elements in array[p..r-1]
// have been compared with array[r],
// swap array[r] with array[q], and return q.
var q = p;
for(var j = q; j < r; j++) {
if(array[j] <= array[r]) {
swap(array, j, q);
q++;
}
}
swap(array, r, q);
return q;
};
Graph Representation
var edgeList = [ [0, 2], [1, 3], [2, 3], [2, 4], [3, 5], [4, 5] ];
var adjMatrix = [
[[0,0,1,0,0,0], [0,0,0,1,0,0], [0,0,0,1,1,0], [0,0,0,0,0,1], [0,0,0,0,0,1], [0,0,0,0,0,0]]
];
var adjList = [
[[2], [3], [3, 4], [5], [5], []]
];
Breadth-first search, also known as BFS, finds shortest paths from a given source vertex to all other vertices, in terms of the number of edges in the paths.
Breadth-first search assigns two values to each vertex v:
- A distance, giving the minimum number of edges in any path from the source vertex to vertex v.
- The predecessor vertex of v along some shortest path from the source vertex. The source vertex's predecessor is some special value, such as
null
, indicating that it has no predecessor.
how to keep track of which vertices have already been visited but have not yet been visited from. We use a queue, which is a data structure that allows us to insert and remove items, where the item removed is always the one that has been in the queue the longest. We call this behavior first in, first out. A queue has three operations:
enqueue(obj)
inserts an object into the queue.dequeue()
removes from the queue the object that has been in it the longest, returning this object.isEmpty()
returnstrue
if the queue currently contains no objects, andfalse
if the queue contains at least one object.
Breadth First Search
BFS is a simple strategy in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors and so on until the best possible path has been found. Due to the fact that this strategy for graph traversal has no additional information about states beyond that provided in the problem definition, Breadth First Search is classed as an uninformed or blind search.BFS uses a queue data structure which is a 'First in, First Out' or FIFO data structure. This queue stores all the nodes that we have to explore and each time a node is explored it is added to our set of visited nodes.
If we were to conduct a breadth first search on the binary tree above then it would do the following:
- Set Node 1 as the start Node
- Add this Node to the Queue
- Add this Node to the visited set
- If this node is our goal node then return true, else add Node 2 and Node 3 to our Queue
- Check Node 2 and if it isn’t add both Node 4 and Node 5 to our Queue.
- Take the next node from our Queue which should be Node 3 and check that.
- If Node 3 isn’t our goal node add Node 6 and Node 7 to our Queue.
- Repeat until goal Node is found.
Challenge: Implement breadth-first search
/* A Queue object for queue-like functionality over JavaScript arrays. */var Queue = function() {
this.items = [];
};
Queue.prototype.enqueue = function(obj) {
this.items.push(obj);
};
Queue.prototype.dequeue = function() {
return this.items.shift();
};
Queue.prototype.isEmpty = function() {
return this.items.length === 0;
};
/*
* Performs a breadth-first search on a graph
* @param {array} graph - Graph, represented as adjacency lists.
* @param {number} source - The index of the source vertex.
* @returns {array} Array of objects describing each vertex, like
* [{distance: _, predecessor: _ }]
*/
var doBFS = function(graph, source) {
var bfsInfo = [];
for (var i = 0; i < graph.length; i++) {
bfsInfo[i] = {
distance: null,
predecessor: null };
}
bfsInfo[source].distance = 0;
var queue = new Queue();
queue.enqueue(source);
// Traverse the graph
// As long as the queue is not empty:
// Repeatedly dequeue a vertex u from the queue.
//
// For each neighbor v of u that has not been visited:
// Set distance to 1 greater than u's distance
// Set predecessor to u
// Enqueue v
//
// Hint:
// use graph to get the neighbors,
// use bfsInfo for distances and predecessors
while(!queue.isEmpty()){
var vertex= queue.dequeue();
for(var i=0; i< graph[vertex].length; i++){
var neighbour = graph[vertex][i];
if(bfsInfo[neighbour].distance===null){
bfsInfo[neighbour].distance = bfsInfo[vertex].distance + 1;
bfsInfo[neighbour].predecessor=vertex;
queue.enqueue(neighbour);
}
}
}
return bfsInfo;
};
var adjList = [
[1],
[0, 4, 5],
[3, 4, 5],
[2, 6],
[1, 2],
[1, 2, 6],
[3, 5],
[]
];
var bfsInfo = doBFS(adjList, 3);
for (var i = 0; i < adjList.length; i++) {
println("vertex " + i + ": distance = " + bfsInfo[i].distance + ", predecessor = " + bfsInfo[i].predecessor);
}
A graph in which ∣E∣=∣V∣−1 is called a free tree.)