Skip to content

Commit 8b78011

Browse files
author
Kendrick Ledet
committed
Made a change to the README before more conventions were added from another committer.
2 parents 57ec538 + 9ffb3a7 commit 8b78011

7 files changed

Lines changed: 378 additions & 3 deletions

File tree

‎Merge_Sort/C/Makefile‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
CFLAGS=-Wall -g
2+
3+
clean:
4+
rm -f jonathanlebron_merge_sort

‎Merge_Sort/C/jonathanlebron_merge_sort.c‎

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
#include <stdio.h>
2+
#include <stdlib.h>
3+
/* Author: Jonathan Lebron 2013
4+
* Merge Sort: Sorts an array of N elements using a divide and conquer approach.
5+
6+
* Definition:
7+
* Input: A sequence of n elements {A1, A2, ..., An}
8+
* Output: Permutation {A'1, A'2, ..., A'n} of Input such that A'1 <= A'2 <= ... <= A'n
9+
*/
10+
11+
// forward declarations
12+
void merge(int a[], int aux[], int lo, int mid, int hi);
13+
void sort(int a[], int aux[], int lo, int hi);
14+
15+
void mergeSort(int a[], int size)
16+
{
17+
int aux[size]; // create auxillary array to store copy
18+
sort(a, aux, 0, size-1);
19+
}
20+
21+
void sort(int a[], int aux[], int lo, int hi)
22+
{
23+
if (hi > lo){
24+
int mid = lo + (hi-lo)/2;
25+
26+
sort(a, aux, lo, mid);
27+
sort(a, aux, mid+1, hi);
28+
merge(a, aux, lo, mid, hi);
29+
}
30+
}
31+
32+
void merge(int a[], int aux[], int lo, int mid, int hi)
33+
{
34+
// copy array
35+
for (int k = lo; k <= hi; k++){
36+
aux[k] = a[k];
37+
}
38+
39+
int i = lo;
40+
int j = mid+1;
41+
for (int k = lo; k <= hi; k++) {
42+
if (i > mid) {
43+
a[k] = aux[j++];
44+
} else if (j > hi) {
45+
a[k] = aux[i++];
46+
} else if (aux[j] < aux[i]) {
47+
a[k] = aux[j++];
48+
} else {
49+
a[k] = aux[i++];
50+
}
51+
}
52+
}
53+
54+
int main(int argc, char *argv[])
55+
{
56+
if (argc < 2) {
57+
printf("ERROR: Must provide at least one argument!\n");
58+
exit(1);
59+
}
60+
61+
int a[argc-1];
62+
for (int i = 1; i < argc; i++){
63+
a[i-1] = atoi(argv[i]);
64+
}
65+
66+
mergeSort(a, argc-1);
67+
68+
printf("Done sorting... Result is {");
69+
for (int i = 0; i < argc-1; i++){
70+
printf("%d, ", a[i]);
71+
}
72+
printf("\b\b}\n");
73+
}

‎Merge_Sort/Java/MergeSort.java‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
2+
public class MergeSort {
3+
4+
static public void main(String[] args) {
5+
int[] unsorted = {10, 9, 8, 7, 6, 4, 5, 2, 3, 1};
6+
int[] sorted = mergeSort(unsorted);
7+
8+
for (int i : sorted) {
9+
System.out.println(i);
10+
}
11+
}
12+
13+
static int[] mergeSort(int[] array) {
14+
if (array.length == 1) {
15+
return array;
16+
} else {
17+
int[] firstHalf = new int[array.length / 2];
18+
System.arraycopy(array, 0, firstHalf, 0, array.length / 2);
19+
firstHalf = mergeSort(firstHalf);
20+
21+
int[] secondHalf = new int[array.length - firstHalf.length];
22+
System.arraycopy(array, firstHalf.length, secondHalf, 0, array.length - firstHalf.length);
23+
secondHalf = mergeSort(secondHalf);
24+
25+
return merge(firstHalf, secondHalf);
26+
}
27+
}
28+
29+
static int[] merge(int[] firstHalf, int[] secondHalf) {
30+
int newLength = firstHalf.length + secondHalf.length;
31+
int[] merged = new int[newLength];
32+
33+
int j = 0;
34+
int k = 0;
35+
36+
for (int i = 0; i < merged.length; i++) {
37+
if (j == firstHalf.length) {
38+
merged[i] = secondHalf[k];
39+
k++;
40+
continue;
41+
}
42+
43+
if (k == secondHalf.length) {
44+
merged[i] = firstHalf[j];
45+
j++;
46+
continue;
47+
}
48+
49+
if (firstHalf[j] > secondHalf[k]) {
50+
merged[i] = secondHalf[k];
51+
k++;
52+
} else {
53+
merged[i] = firstHalf[j];
54+
j++;
55+
}
56+
}
57+
58+
return merged;
59+
}
60+
61+
}

‎README.md‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,12 @@ Conventions
2121

2222
+ It is preferred that you prepend or append your files with your Github username or some identifier to avoid overwriting others' implementations. `git blame` is cool, and has many more appropriate applications, but in this context I'd rather pull a flat list of files and be able to check out everyone's contributions that way than have to look through the revisions.
2323

24+
+ Each algorithm should have its corresppnding unit test cases which covers the corner cases, happy/unhappy path.
25+
Advantage of doing so is to asset that every thing is covered and algorithm is not broken between code change.
26+
It also helps newbie to have a quick look at the unit test cases and understand the basic usecase of the algorithm.
27+
28+
+ Documentation inside the code is recommended. This helps others in understanding the code base.
29+
2430
+ Have fun!
2531

2632
Resources

‎Radix_Sort/Java/patrickyevsukov_readable_radix_sort.java‎

Lines changed: 7 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,11 @@
1-
// Patrick Yevsukov 2013
1+
// Patrick Yevsukov
22

3-
// Below is my own implementation of the radix sorting algorithm.
4-
// I wrote it to be as human readable as possible.
3+
// 2013 CC BY-NC-SA 4.0
4+
5+
// Excerpt From github.com/PatrickYevsukov/Sorting-Algorithms
6+
7+
// Below is my own implementation of the radix sort. It was
8+
// written to be as human readable as possible.
59

610
public static void RadixSort(ArrayList<Integer> list) {
711

‎Stat_Mode/C/patrickyevsukov_stat_mode.c‎

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
// Patrick Yevsukov
2+
3+
// 2013 CC BY-NC-SA 4.0
4+
5+
// Excerpt From github.com/PatrickYevsukov/Statistics-Calculator
6+
7+
// I devised this algorithm to identify the statistical mode or
8+
// modes of a dataset. It requires one pass through the set to
9+
// identify the set's mode or modes.
10+
11+
// This algorithm works by keeping track of the number of times a
12+
// unique value occurs in the set. If a unique value has occurred
13+
// more times than the ones before it, it is added to the list of
14+
// modes. As the loop continues all values which occur this number
15+
// of times are added to the list of modes, unless another unique
16+
// value occurs more times than the currently identified modes. If
17+
// this happens, the mode array indexing variable is reset to zero
18+
// and the previously identified values are overwritten by the new
19+
// modes. When finished, the mode array indexing variable will be
20+
// one less than the number of modes.
21+
22+
// This algorithm requires a set of values in which all instances
23+
// of a unique value are listed next to one another.
24+
25+
#include <stdio.h>
26+
#include <stdlib.h>
27+
28+
#define MAX_SAMPLE 25
29+
30+
double *
31+
SampleMode(double *, int *);
32+
33+
double *
34+
SampleMode(double *sample, int *sample_size)
35+
{
36+
int ii = 0;
37+
38+
int kk = 0;
39+
40+
int num_modes = 0;
41+
42+
int previous_freq = 0;
43+
44+
int current_freq = 1; // Every value must occur at least once
45+
46+
double *modes = NULL;
47+
48+
modes = (double *) malloc(MAX_SAMPLE * sizeof *modes);
49+
50+
for (ii = 0; ii <= *sample_size - 1; ii++)
51+
{
52+
if (sample[ii] == sample[ii + 1])
53+
{
54+
current_freq++;
55+
}
56+
else
57+
{
58+
if (current_freq > previous_freq)
59+
{
60+
kk = 0; // Reset
61+
62+
previous_freq = current_freq;
63+
64+
modes[kk] = sample[ii];
65+
}
66+
67+
else if (current_freq == previous_freq)
68+
{
69+
kk++;
70+
71+
modes[kk] = sample[ii];
72+
}
73+
74+
current_freq = 1; // Reset
75+
}
76+
}
77+
78+
num_modes = kk + 1;
79+
80+
return modes;
81+
}

‎Token_Bucket/Javascript/jhurliman_token_bucket.js‎

Lines changed: 146 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,146 @@
1+
/**
2+
* Copyright (c) 2013 John Hurliman <jhurliman@jhurliman.org>
3+
*
4+
* Permission is hereby granted, free of charge, to any person obtaining a copy
5+
* of this software and associated documentation files (the "Software"), to deal
6+
* in the Software without restriction, including without limitation the rights
7+
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8+
* copies of the Software, and to permit persons to whom the Software is
9+
* furnished to do so, subject to the following conditions:
10+
*
11+
* The above copyright notice and this permission notice shall be included in
12+
* all copies or substantial portions of the Software.
13+
*
14+
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15+
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16+
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17+
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18+
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19+
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20+
* THE SOFTWARE.
21+
*/
22+
23+
24+
/**
25+
* A hierarchical token bucket for rate limiting. See
26+
* http://en.wikipedia.org/wiki/Token_bucket for more information.
27+
*
28+
* @param {Number} bucketSize Maximum number of tokens to hold in the bucket.
29+
* Also known as the burst rate.
30+
* @param {Number} tokensPerInterval Number of tokens to drip into the bucket
31+
* over the course of one interval.
32+
* @param {String|Number} interval The interval length in milliseconds, or as
33+
* one of the following strings: 'second', 'minute', 'hour', day'.
34+
* @param {TokenBucket} parentBucket Optional. A token bucket that will act as
35+
* the parent of this bucket.
36+
*/
37+
var TokenBucket = function(bucketSize, tokensPerInterval, interval, parentBucket) {
38+
this.bucketSize = bucketSize;
39+
this.tokensPerInterval = tokensPerInterval;
40+
41+
if (typeof interval === 'string') {
42+
switch (interval) {
43+
case 'sec': case 'second':
44+
this.interval = 1000; break;
45+
case 'min': case 'minute':
46+
this.interval = 1000 * 60; break;
47+
case 'hr': case 'hour':
48+
this.interval = 1000 * 60 * 60; break;
49+
case 'day':
50+
this.interval = 1000 * 60 * 60 * 24; break;
51+
}
52+
} else {
53+
this.interval = interval;
54+
}
55+
56+
this.parentBucket = parentBucket;
57+
this.content = 0;
58+
this.lastDrip = +new Date();
59+
};
60+
61+
TokenBucket.prototype = {
62+
bucketSize: 1,
63+
tokensPerInterval: 1,
64+
interval: 1000,
65+
parentBucket: null,
66+
content: 0,
67+
lastDrip: 0,
68+
69+
/**
70+
* Remove the requested number of tokens and fire the given callback. If the
71+
* bucket (and any parent buckets) contains enough tokens this will happen
72+
* immediately. Otherwise, the removal and callback will happen when enough
73+
* tokens become available.
74+
* @param {Number} count The number of tokens to remove.
75+
* @param {Function} callback(err, remainingTokens)
76+
* @returns {Boolean} True if the callback was fired immediately, otherwise
77+
* false.
78+
*/
79+
removeTokens: function(count, callback) {
80+
var self = this;
81+
82+
// Is this an infinite size bucket?
83+
if (!this.bucketSize) {
84+
callback(null, count, Number.POSITIVE_INFINITY);
85+
return true;
86+
}
87+
88+
// Make sure the bucket can hold the requested number of tokens
89+
if (count > this.bucketSize) {
90+
callback('Requested tokens ' + count + ' exceeds bucket size ' +
91+
this.bucketSize, null);
92+
return false;
93+
}
94+
95+
// Drip new tokens into this bucket
96+
this.drip();
97+
98+
// If we don't have enough tokens in this bucket, come back later
99+
if (count > this.content) {
100+
// How long do we need to wait to make up the difference in tokens?
101+
var waitInterval = Math.ceil(
102+
(count - this.content) * (this.interval / this.tokensPerInterval));
103+
setTimeout(function() { self.removeTokens(count, callback); }, waitInterval);
104+
return false;
105+
}
106+
107+
if (this.parentBucket) {
108+
// Remove the requested from the parent bucket first
109+
return this.parentBucket.removeTokens(count, function(err, remainingTokens) {
110+
if (err) return callback(err, null);
111+
112+
// Tokens were removed from the parent bucket, now remove them from
113+
// this bucket and fire the callback. Note that we look at the current
114+
// bucket and parent bucket's remaining tokens and return the smaller
115+
// of the two values
116+
self.content -= count;
117+
callback(null, Math.min(remainingTokens, self.content));
118+
});
119+
} else {
120+
// Remove the requested tokens from this bucket and fire the callback
121+
this.content -= count;
122+
callback(null, this.content);
123+
return true;
124+
}
125+
},
126+
127+
/**
128+
* Add any new tokens to the bucket since the last drip.
129+
* @returns {Boolean} True if new tokens were added, otherwise false.
130+
*/
131+
drip: function() {
132+
if (!this.tokensPerInterval) {
133+
this.content = this.bucketSize;
134+
return;
135+
}
136+
137+
var now = +new Date();
138+
var deltaMS = Math.max(now - this.lastDrip, 0);
139+
this.lastDrip = now;
140+
141+
var dripAmount = deltaMS * (this.tokensPerInterval / this.interval);
142+
this.content = Math.min(this.content + dripAmount, this.bucketSize);
143+
}
144+
};
145+
146+
module.exports = TokenBucket;

0 commit comments

Comments
 (0)