Skip to content

Fix some errors in Quicksort source #18

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 2 commits into from
May 22, 2016
Merged

Fix some errors in Quicksort source #18

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
eafc8e9
Fix define warning in "temp" variable
imkimchi May 22, 2016
d8bc151
make it look better
imkimchi May 22, 2016
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
92 changes: 42 additions & 50 deletions algorithm/sorting/merge/basic/code.js
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -3,74 +3,66 @@ tracer._sleep(1000);
tracer._pace(500);

function mergeSort(start, end) {
if (Math.abs(end - start) <= 1) {
return [];
}

if (Math.abs(end - start) <= 1) return [];
var middle = Math.ceil((start + end) / 2);

mergeSort(start, middle);
mergeSort(middle, end);

tracer._print('divide left[' + start + ', ' + (middle-1) + '], right[' + (middle) + ', ' + (end-1) + ']');

tracer._print('divide left[' + start + ', ' + (middle - 1) + '], right[' + (middle) + ', ' + (end - 1) + ']');
return mergeSort.merge(start, middle, end);
}

mergeSort.merge = function (start, middle, end) {
var left = Array();
var right = Array();

var leftSize = middle - start;
var rightSize = end - middle;
var maxSize = Math.max(leftSize, rightSize);
var size = end - start;
mergeSort.merge = function(start, middle, end) {
const leftSize = middle - start;
const rightSize = end - middle;
const maxSize = Math.max(leftSize, rightSize);
const size = end - start;
var left = [];
var right = [];
var i;

for (i = 0; i < maxSize; i++) {
if (i < leftSize) {
left.push(D[start + i]);
tracer._select(start + i);
tracer._print('insert value into left array[' + i +'] = ' + D[start + i]);
}
if (i < rightSize) {
right.push(D[middle + i]);
tracer._select(middle + i);
tracer._print('insert value into right array[' + i +'] = ' + D[middle + i]);
}
if (i < leftSize) {
left.push(D[start + i]);
tracer._select(start + i);
tracer._print('insert value into left array[' + i + '] = ' + D[start + i]);
}
if (i < rightSize) {
right.push(D[middle + i]);
tracer._select(middle + i);
tracer._print('insert value into right array[' + i + '] = ' + D[middle + i]);
}
}
tracer._print('left array = [' + left.join(', ') + '],' + 'right array = [' + right.join(', ') + ']');

i = 0;
while (i < size) {
if (left[0] && right[0]) {
if (left[0] > right[0]) {
D[start + i] = right.shift();
tracer._print('rewrite from right array[' + i + '] = ' + D[start+i]);
if (left[0] && right[0]) {
if (left[0] > right[0]) {
D[start + i] = right.shift();
tracer._print('rewrite from right array[' + i + '] = ' + D[start + i]);
} else {
D[start + i] = left.shift();
tracer._print('rewrite from left array[' + i + '] = ' + D[start + i]);
}
} else if (left[0]) {
D[start + i] = left.shift();
tracer._print('rewrite from left array[' + i + '] = ' + D[start + i]);
} else {
D[start + i] = left.shift();
tracer._print('rewrite from left array[' + i + '] = ' + D[start+i]);
D[start + i] = right.shift();
tracer._print('rewrite from right array[' + i + '] = ' + D[start + i]);
}
} else if (left[0]) {
D[start + i] = left.shift();
tracer._print('rewrite from left array[' + i + '] = ' + D[start+i]);
} else {
D[start + i] = right.shift();
tracer._print('rewrite from right array[' + i + '] = ' + D[start+i]);
}

tracer._deselect(start + i);
tracer._notify(start + i);

i++;
}

tempArray = Array();
for (i=start; i<end; i++) {
tempArray.push(D[i]);

tracer._deselect(start + i);
tracer._notify(start + i);
i++;
}

tempArray = [];
for (i = start; i < end; i++) tempArray.push(D[i]);
tracer._print('merged array = [' + tempArray.join(', ') + ']');
}
};

mergeSort(0, D.length)
mergeSort(0, D.length);
tracer._print('sorted array = [' + D.join(', ') + ']');
11 changes: 8 additions & 3 deletions algorithm/sorting/quick/basic/code.js
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,32 +1,37 @@
tracer._print('original array = [' + D.join(', ') + ']');
tracer._sleep(1000);
tracer._pace(500);

function quicksort(low, high) {
if (low < high) {
var p = partition(low, high);
quicksort(low, p - 1);
quicksort(p + 1, high);
}
}

function partition(low, high) {
var pivot = D[high];
tracer._selectSet([low, high]);
var i = low;
var temp;

for (var j = low; j < high; j++) {
if (D[j] <= pivot) {
var temp = D[i];
temp = D[i];
D[i] = D[j];
D[j] = temp;
tracer._notify(i, j);
i++;
}
}
var temp = D[i];
temp = D[i];
D[i] = D[high];
D[high] = temp;
tracer._notify(i, high);
tracer._deselectSet([low, high]);
return i;
}

quicksort(0, D.length - 1);
tracer._print('sorted array = [' + D.join(', ') + ']');
tracer._print('sorted array = [' + D.join(', ') + ']');