Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit9d5ea28

Browse files
committed
bubble sort basic implemetation
1 parentca93912 commit9d5ea28

12 files changed

+203
-95
lines changed

‎Hash_Table/generic_hash_table_implementation.js

100644100755
File mode changed.

‎Hash_Table/hashmap_interview_question.js

100644100755
File mode changed.

‎Hash_Table/remove_duplicates_from_array_returning_only_unique_elements.js

100644100755
File mode changed.

‎Linked-List/generic-Linked-list.js

100644100755
Lines changed: 47 additions & 56 deletions
Original file line numberDiff line numberDiff line change
@@ -2,88 +2,79 @@ function Node(element) {
22
this.element=element;
33
this.next=null;
44
this.previous=null;
5-
}
5+
}
66

7-
functionLList(){
7+
// The only property stored in a linked list is a node to represent the head of the list and the head node starts with its next property set to null.
8+
9+
functionLList(){
810
this.head=newNode("head");
911
this.find=find;
1012
this.insert=insert;
1113
this.display=display;
1214
this.remove=remove;
13-
this.findLast=findLast;
14-
this.dispReverse=dispReverse;
15-
}
16-
17-
functiondispReverse(){
18-
varcurrNode=this.head;
19-
currNode=this.findLast();
20-
while(!(currNode.previous==null)){
21-
console.log(currNode.element);
22-
currNode=currNode.previous;
23-
}
24-
}
25-
26-
functionfindLast(){
27-
varcurrNode=this.head;
28-
while(!(currNode.next==null)){
29-
currNode=currNode.next;
30-
}
31-
returncurrNode;
32-
}
15+
}
3316

34-
functionremove(item){
17+
functionremove(item){
3518
varcurrNode=this.find(item);
3619
if(!(currNode.next==null)){
37-
currNode.previous.next=currNode.next;
38-
currNode.next.previous=currNode.previous;
39-
currNode.next=null;
40-
currNode.previous=null;
20+
currNode.previous.next=currNode.next;
21+
currNode.next.previous=currNode.previous;
22+
currNode.next=null;
23+
currNode.previous=null;
4124
}
42-
}
25+
}
4326

44-
// findPrevious is no longer needed
45-
/*function findPrevious(item) {
46-
var currNode = this.head;
47-
while (!(currNode.next == null) &&
48-
(currNode.next.element != item)) {
49-
currNode = currNode.next;
50-
}
51-
return currNode;
52-
}*/
53-
54-
functiondisplay(){
27+
// function to display the elements of a linked list. Starts by hooking into the linked list by assigning the head of the list to a new node. Then it loops through the linked list printing the the next.element, till the current node’s next property is set to null, i.e. the last node has been reached.
28+
functiondisplay(){
5529
varcurrNode=this.head;
5630
while(!(currNode.next==null)){
5731
console.log(currNode.next.element);
5832
currNode=currNode.next;
5933
}
60-
}
34+
}
35+
36+
// A helper function to find a particular node.
37+
functionfind(item){
38+
varcurrNode=this.head;// create a new node and assign it as the head node.
39+
40+
// Keep looping through the linked list with the next property, while the value of the current node’s element property is not equal to the data we are searching for. And on success, the function returns the node storing the data. If the data is not found, the function returns null.
6141

62-
functionfind(item){
63-
varcurrNode=this.head;
6442
while(currNode.element!=item){
6543
currNode=currNode.next;
6644
}
6745
returncurrNode;
68-
}
46+
}
6947

70-
functioninsert(newElement,item){
48+
49+
// function to insert a new node, after a particular node say node X, first find X using find(). Then set new node’s next property to the value of the next property of X . Then set X's next property to reference to the new node that I just inserted.
50+
51+
functioninsert(newElement,item){
7152
varnewNode=newNode(newElement);
7253
varcurrent=this.find(item);
7354
newNode.next=current.next;
7455
newNode.previous=current;
7556
current.next=newNode;
76-
}
57+
}
58+
59+
60+
varcities=newLList();
61+
cities.insert("Bill","head");
62+
cities.insert("Steve","Bill");
63+
cities.insert("Paul","Steve");
64+
cities.insert("Woz","Paul");
65+
66+
cities.display();
67+
cities.remove("Steve");
68+
console.log("**After removal**");
69+
cities.display();
7770

71+
/* OUTPUT: -
7872
79-
varcities=newLList();
80-
cities.insert("Conway","head");
81-
cities.insert("Russellville","Conway");
82-
cities.insert("Carlisle","Russellville");
83-
cities.insert("Alma","Carlisle");
84-
cities.display();
85-
console.log();
86-
cities.remove("Carlisle");
87-
cities.display();
88-
console.log();
89-
cities.dispReverse();
73+
Bill
74+
Steve
75+
Paul
76+
Woz
77+
**After removal**
78+
Bill
79+
Paul
80+
Woz */
Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
/* https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
2+
3+
Given a linked list, remove the nth node from the end of list and return its head.
4+
5+
For example,
6+
7+
Given linked list: 1->2->3->4->5, and n = 2.
8+
9+
After removing the second node from the end, the linked list becomes 1->2->3->5.
10+
Note: Given n will always be valid. Try to do this in one pass. */
11+
12+
/*
13+
A> In order to remove a node from a linked list, we need to find the node that is just before the node we want to remove. Once we find that node, we change its next property to no longer reference the removed node. But, the previous node is modified to point to the node after the removed node. So the key line of code will be
14+
15+
prevNode.next = prevNode.next.next
16+
17+
We are just skipping over the node we want to remove and linking the “previous” node with the node just after the one we are removing.
18+
19+
20+
B> The nth node from the end will be (list.length - n + 1)-th node from the begining of the Linked List.
21+
22+
For example:
23+
24+
1-> 2 -> 3 -> 4 -> 5 -> 6 -> 7
25+
26+
To return 2nd node from the end(n = 2), we need to return 6th (7 - 2 + 1) node from beginning which is node '6'.
27+
28+
http://www.ideserve.co.in/learn/find-nth-node-from-the-end-of-linked-list
29+
30+
C> So the problem could be simply reduced to another one : Remove the (L - n + 1)th node from the beginning in the list , where L is the list length.
31+
32+
D> First we will add an auxiliary dummy or fake head node which in the below program I am naming as "currentNode", which points to the list head. The “dummy” node is used to simplify some corner cases such as a list with only one node, or removing the head of the list. The key step is we have to relink next pointer of the (L - n)th node to the (L - n + 2)th node and we are done.
33+
34+
*/
35+
36+
varremoveNthFromEnd=function(head,n){
37+
varlist=[],
38+
currentNode=head;
39+
40+
while(currentNode.next!==null){
41+
list.push(currentNode);
42+
currentNode=currentNode.next;
43+
}
44+
list.push(currentNode);
45+
46+
// Now we have to deal with 3 cases about the initial position of the node-to-be-removed.
47+
48+
/* Case-1 >> When the node-to-be-removed is somewhere in between the last and first nodes of the linked-list.
49+
50+
A) The link of the node before the removed node is redirected to point to the node the removed node is pointing to.
51+
52+
B) But now the total length of the list has been reduced by one after removal of the n-th node, so the The new n-th node from the end will be (list.length - n + 1 - 1 )-th node from the beginning of the Linked List i.e. (list.length -n )-th node.
53+
54+
C) And the node previous to the removed node will be ((list.length -n + 1) - 1 - 1)-th node, i.e. (list.length - n - 1)-th node.
55+
56+
D) So, now, I have to link the node before the removed node to be redirected to point to the node after the removed node, which will be (list.length -n + 1)-th node.
57+
58+
D) So I do, list[list.length - n - 1].next = list[list.length -n + 1]
59+
So, to remove the current element from the list, all we have to do is link previous.next with current.next . This way, the current element will be lost in the computer memory and will be available to be cleaned by the garbage collector.
60+
*/
61+
62+
if(list.length-n-1>=0&&list.length-n+1<list.length){
63+
list[list.length-n-1].next=list[list.length-n+1];
64+
returnlist[0];
65+
}
66+
67+
/* Case-2 >> If the node-to-be-removed was the first node of the Linked-list.
68+
That is, after removal the position of the previous-node to the removed-node will be negative.
69+
In this case, if the node-removed was the only node of the linked list then for the head of the list, return an empty array if list.length is <=1. ELSE,
70+
If the length is more than one, then return the index 1 element for the head. */
71+
if(list.length-n-1<0){
72+
returnlist.length<=1 ?[] :list[1]
73+
}
74+
75+
/* Case - 3 >> If the node-to-be-removed was the last node of the Linked-list.
76+
That is, after removal the previous node becomes the last node of the Linked-list, then just point its next-node to null.*/
77+
78+
if(list.length-n+1>=list.length){
79+
list[list.length-n-1].next=null;
80+
returnlist[0];
81+
}
82+
83+
}

‎Sorting/bubble-sort-basic.js

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
letarr=Array.from({length:20},()=>Math.floor(Math.random()*20))
2+
console.log(arr);
3+
4+
// swap helper function
5+
swap=(arr,i,j)=>{
6+
lettemp=arr[i];
7+
arr[i]=arr[j];
8+
arr[j]=temp;
9+
}
10+
11+
// Necessary warning :) :) - this is a super basic implementation to understand the principle behind bubble sort (going through all comparisons) but there's huge room for performance improvement on this.
12+
13+
bubbleSortBasicAscending=(arr)=>{
14+
15+
for(leti=0;i<arr.length;i++){
16+
for(letj=1;j<arr.length;j++){
17+
if(arr[j]<arr[j-1]){
18+
swap(arr,j,j-1);
19+
}
20+
}
21+
}
22+
returnarr;
23+
}
24+
25+
console.log(bubbleSortBasicAscending(arr));
26+
27+
bubbleSortBasicDescending=(arr)=>{
28+
29+
for(leti=0;i<arr.length;i++){
30+
for(letj=1;j<arr.length;j++){
31+
if(arr[j]>arr[j-1]){
32+
swap(arr,j,j-1);
33+
}
34+
}
35+
}
36+
returnarr;
37+
}
38+
39+
console.log(bubbleSortBasicDescending(arr));

‎Sorting/insertion_sort.js

100644100755
File mode changed.

‎Sorting/quick-sort-Hoare.js

100644100755
Lines changed: 3 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -24,8 +24,8 @@
2424

2525
}
2626

27-
/* Two indices that start at the ends of the array being partitioned, then move toward each other, until they detect an inversion: a pair of elements, one greater than the pivot, one smaller, that are in the wrong order relative to each other. The inverted elements are then swapped.
28-
Here the numerical values of left and right is continually getting updated with each inner while loop. But only if the while loop condition gets satisfied. That is, when the while loop condition is unsatisfied, e.g. for the first inner while loop, when array[left] > array[pivot] which means we have found a misplaced pair.
27+
/* Two indices that start at the ends of the array being partitioned, then move toward each other, until they detect an inversion: a pair of elements, one greater than the pivot, one smaller, that are in the wrong order relative to each other. The inverted elements are then swapped.
28+
Here the numerical values of left and right is continually getting updated with each inner while loop. But only if the while loop condition gets satisfied. That is, when the while loop condition is unsatisfied, e.g. for the first inner while loop, when array[left] > array[pivot] which means we have found a misplaced pair.
2929
3030
That is, although the left <= right (which is being made sure by the outer while loop) the actual elements are not sorted. Meaning a left side element is larger in value than the right side element. So, the code execution then jumps out of the inner while loop and goes right in to execute the swap function.
3131
*/
@@ -53,20 +53,9 @@
5353

5454
/******************* Testing Hoare algorithm *********************/
5555

56-
functiongetRandomInt(min,max){
57-
returnMath.floor(Math.random()*(max-min+1))+min;
58-
// By adding 1, I am making the maximum inclusive ( the minimum is inclusive anyway). Because, the Math.random() function returns a floating-point, pseudo-random number in the range from 0 inclusive up to but not including 1
59-
}
60-
61-
vararr=[];
62-
63-
for(vari=0;i<10;i++){//initialize a random integer unsorted array
64-
arr.push(getRandomInt(1,100));
65-
}
6656

67-
console.log("Unsorted array: ");
57+
letarr=Array.from({length :20},()=>Math.floor(Math.random()*20));
6858
console.log(arr);//printing unsorted array
6959

7060
arr=quicksortHoare(arr,0,arr.length-1);
71-
console.log("Sorted array: ");
7261
console.log(arr);

‎Sorting/quick-sort-Lomuto.js

100644100755
Lines changed: 24 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -43,18 +43,32 @@ function partitionLomuto(array, left, right) {
4343

4444
functiongetRandomInt(min,max){
4545
returnMath.floor(Math.random()*(max-min+1))+min;
46-
// By adding 1, I am making the maximum inclusive ( the minimum is inclusive anyway). Because, the Math.random() function returns a floating-point, pseudo-random number in the range from 0 inclusive up to but not including 1
4746
}
4847

49-
vararr=[];
50-
51-
for(vari=0;i<10;i++){//initialize a random integer unsorted array
52-
arr.push(getRandomInt(1,100));
53-
}
54-
55-
console.log("Unsorted array: ");
48+
letarr=Array.from({length :20},()=>Math.floor(Math.random()*20));
5649
console.log(arr);//printing unsorted array
5750

5851
arr=quicksortLomuto(arr,0,arr.length-1);
59-
console.log("Sorted array: ");
60-
console.log(arr);
52+
console.log(arr);
53+
54+
55+
/* Explanation of < Math.floor(Math.random() * (max - min + 1)) + min >
56+
57+
By adding 1, I am making the maximum inclusive ( the minimum is inclusive anyway). Because, the Math.random() function returns a floating-point, pseudo-random number in the range from 0 inclusive up to but not including 1. the formula can generate the correct amount of numbers but they always start at 0 because the range from Math.random starts from 0. https://teamtreehouse.com/community/need-an-explanation
58+
59+
Math.random() returns a number from 0 to 1, not including one. Flooring this number will always result in a zero.
60+
61+
If you multiply this float by the max prior to flooring, you will get numbers all the way up to the maximum, including those below the minimum, but not the maximum itself. Say you have 10 as the maximum, you cannot get a 10.
62+
63+
In order to rule out those below the minimum, you subtract the minimum from the maximum. In order to include the maximum, you add one. This is all multiplied by the random floating point number between 0 and 1.
64+
65+
At that point, we aren't quite there. You will be receiving numbers based on the range between the minimum and maximum as explained above. Adding the minimum back in, post-randomizing, ensure that you have numbers that are between the minimum and the maximum.
66+
67+
TLDR: The range of numbers (i.e. the number of numbers between min and max) is defined by those within the floor method's parentheses. The minimum added at the end ensures these numbers are between the desired minimum and maximum.
68+
69+
By subtracting the minimum number from the maximum, you define the range. Say you have minimum of 5 and a maximum of 20, you will get the range of 15. There are 15 possible numbers that you could select at random between these bounds.
70+
71+
Paul-Note - So, if I dont add Min of 5, the formulae will give me all the random numbers between 0 and 15. But I want between 5 and 20. So thats why I add back the min.
72+
73+
Another great visual explanation at - https://stackoverflow.com/questions/1527803/generating-random-whole-numbers-in-javascript-in-a-specific-range
74+
*/
Lines changed: 7 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,15 @@
1-
// sorting the below array with quick sorting
2-
31
/*The algorithm for Quicksort is:
42
1. Pick a pivot element that divides the list into two sublists.
53
64
2. Reorder the list so that all elements less than the pivot element are placed before
75
the pivot and all elements greater than the pivot are placed after it.
86
97
3. Repeat steps 1 and 2 on both the list with smaller elements and the list of larger
10-
elements.*/
8+
elements.
9+
10+
4. Quicksort is a divide and conquer algorithm in the style of merge sort. The basic idea is to find a “pivot” item in the array to compare all other items against, then shift items such that all of the items before the pivot are less than the pivot value and all the items after the pivot are greater than the pivot value. After that, recursively perform the same operation on the items before and after the pivot. */
1111

12-
// basic implementation, where pivot is the first element, withoutusuing swap function and partition function.
12+
// basicrecursiveimplementation, where pivot is the first element, withoutusing swap function and partition function.
1313

1414
functionquickSortBasic(array){
1515
if(array.length<2){
@@ -27,29 +27,21 @@ function quickSortBasic(array) {
2727
lesserArray.push(array[i]);
2828
}
2929
}
30-
30+
// Now, recursively perform the same operation on the items before and after the pivot.
3131
returnquickSortBasic(lesserArray).concat(pivot,quickSortBasic(greaterArray));
3232
}
3333

34-
3534
/******************* Testing Quick sort algorithm *********************/
3635

3736
// Returns a random integer between min (inclusive) and max (inclusive). Using Math.round() will give a non-uniform distribution, which we dont want in this case.
3837

3938
functiongetRandomInt(min,max){
4039
returnMath.floor(Math.random()*(max-min+1))+min;
41-
// By adding 1, I am making the maximum inclusive ( the minimum is inclusive anyway). Because, the Math.random() function returns a floating-point, pseudo-random number in the range from 0 inclusive up to but not including 1
4240
}
4341

44-
vararr=[];
45-
46-
for(vari=0;i<10;i++){//initialize a random integer unsorted array
47-
arr.push(getRandomInt(1,100));
48-
}
42+
letarr=Array.from({length :20},()=>Math.floor(Math.random()*20));
4943

50-
console.log("Unsorted array: ");
5144
console.log(arr);//printing unsorted array
5245

5346
arr=quickSortBasic(arr,0,arr.length-1);
54-
console.log("Sorted array: ");
55-
console.log(arr);
47+
console.log(arr);

‎package-lock.json

100644100755
File mode changed.

‎package.json

100644100755
File mode changed.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp