kttruong
BAN USERMerge sort can be inplace with O(n log n) and is stable.
#include <iostream>
using namespace std;
void print(int *a, int len) {
for (int i=0; i<len; i++)
cout << a[i];
cout << "\n";
}
void merge(int *a, int *b, int len1, int len2) {
int c[len1+len2];
int i=0, j=0, k=0;
while (i<len1 && j<len2) {
if (a[i] < b[j]) {
c[k++] = a[i++];
} else {
c[k++] = b[j++];
}
}
while (i<len1) {
c[k++] = a[i++];
}
while (j<len2) {
c[k++] = b[j++];
}
for(i=0; i<(len1+len2); i++) {
a[i] = c[i];
}
}
void sort(int *a, int start, int end) {
if (end <= start) return;
int len = end - start;
// ERROR: Must offset with index start to do inplace msort!
int mid = start + len/2;
if (len < 2) {
cout << "start " << start << ": " << a[start] << ", end " << end << ": " << a[end] << "\n";
if (a[start] > a[end]) {
int tmp = a[start];
a[start] = a[end];
a[end] = tmp;
}
} else {
cout << "start " << start << ": " << a[start] << ", mid " << mid << ": " << a[mid] << ", end " << end << ": " << a[end] << "\n";
sort(a, start, mid);
sort(a, mid+1, end);
merge(&a[start], &a[mid+1], (mid-start+1), (end-mid));
cout << "merge result: \n"; // << start << ": " << a[start] << ", mid " << mid << ": " << a[mid] << ," end " << end << ": " << a[end] << "\n";
print(&a[start], end-start + 1);
}
}
void msort(int *a, int len) {
sort(a, 0, len-1);
}
int main() {
int a[] = {3,2,1};
print(a, 3);
msort(a, 3);
print(a, 3);
int b[] = {9,0,1, 5, 2, 7, 2,3};
print(b, 8);
msort(b, 8);
print(b, 8);
return 0;
}
- kttruong June 26, 2016Have two pointers pointing to the linked list incrementing at different pace. Ptr1 increments each node and ptr2 increments every two nodes. If there is a cycle, eventually ptr1 == ptr2.
#include <iostream>
#include <list>
using namespace std;
#define MAX 5
template<class T>
class Node {
public:
Node(): next(NULL) {};
Node(T d): data(d), next(NULL) {};
T data;
Node *next;
};
template <class T>
bool hasCycle(Node<T> *n, Node<T> **me = 0) {
if (n == NULL) return false;
Node<T> *ptr1 = n;
Node<T> *ptr2 = n->next;
while (ptr2 && (ptr2->next)) {
if (ptr1 == ptr2) {
*me = ptr1;
return true;
}
ptr1 = ptr1->next;
ptr2 = ptr2->next->next;
}
return false;
}
int main() {
Node<int> *head = new Node<int>(0);
Node<int> *tmp = head, *tmp1 = NULL;
Node <int> **me = NULL;
// Case 1: NULL
cout << "Case 1 cycle: " << hasCycle<int>(tmp1) << "\n";
// Case 2: 0 -> NULL
cout << "Case 2 cycle: " << hasCycle<int>(tmp) << "\n";
// Case 3: 0 -> 1 -> NULL
tmp = head;
for (int i=1; i<2; i++) {
tmp1 = new Node<int>(i);
tmp->next = tmp1;
}
cout << "Case 3 cycle: " << hasCycle<int>(tmp) << "\n";
// Case 4: 0 loops
tmp = head;
tmp->next = tmp;
cout << "Case 4 cycle: " << hasCycle<int>(tmp, &tmp1) << " at: " << tmp1->data << "\n";
// Case 5: 0 -> 1 -> loops to 0
tmp = head;
for (int i=1; i<2; i++) {
tmp1 = new Node<int>(i);
tmp->next = tmp1;
tmp = tmp->next;
}
tmp->next = head;
cout << "Case 5 cycle: " << hasCycle<int>(head, &tmp1) << " at: " << tmp1->data << "\n";
// Case 6: 0 -> 1 -> 2 -> loops to 1
tmp = head;
for (int i=1; i<3; i++) {
tmp1 = new Node<int>(i);
tmp->next = tmp1;
tmp = tmp->next;
}
tmp->next = head->next;
cout << "Case 6 cycle: " << hasCycle<int>(head, &tmp1) << " at: " << tmp1->data << "\n";
// Case 7: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> loops to 5
tmp = head;
for (int i=1; i<11; i++) {
tmp1 = new Node<int>(i);
tmp->next = tmp1;
tmp = tmp->next;
}
tmp->next = head->next->next->next->next->next;
cout << "Case 7 cycle: " << hasCycle<int>(head, &tmp1) << " at: " << tmp1->data << "\n";
return 0;
}
- kttruong June 25, 2016
I think it has to do with the layout of the object. arrd is class der, which has the layout of two entries, int a (4 bytes) and int b (4 bytes). So if arrd[0] is at address x, arrd[0].a is at x+0 and arrd[0].b is at x+4.
- kttruong July 13, 2016When you pass arrd into the display function, you're passing it as a pointer. When you increment a pointer (obj+i), you're adding 4 bytes to the object's address. This does not give you the next element in the array (unless each element is size 4 bytes like an array of integers). You really need to add 8 bytes to get the next element in the array of der objects because 8 is the size of each arrd object.
In summary, you're seeing 0,1,0 because you're seeing var 'a' of the first object, var 'b' of the first object, and var 'a' of the second object.
If you print out the address of the objects, this will be make more sense. For example,
arrd[0] is at address 0xfff...e0 where var 'a' is at 0xfff...e0 and var 'b' is at 0xfff...e4
arrd[1] is at address 0xfff...e8 where 'a' is at 0xfff...e8 and 'b' is at 0xfff...ec
arrd[2] is at address 0xfff...f0 where 'a' is at 0xfff...f0 and 'b' is at 0xfff...f4
If you print the address of obj+i:
obj+0 is at address 0xfff...e0 // 'a' from arrd[0]
obj+1 is at address 0xfff...e4 // 'b' from arrd[0]
obj+2 is at address 0xfff...e8 // 'a' from arrd[1]