Skip to content

Commit 4f7e4b3

Browse files
author
cfdcoder
committed
Add MergeSort2.java
1 parent 3948049 commit 4f7e4b3

File tree

42 files changed

+3992
-1593
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

42 files changed

+3992
-1593
lines changed

‎.metadata/.plugins/org.eclipse.core.resources/.history/1c/f004a3187dae001517cea66f72e0b330

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
package study;
2+
3+
public class MergeSort2 {
4+
int[] Arr;
5+
MergeSort2(int[] A){
6+
this.Arr=A.clone();
7+
}
8+
9+
public int[] leftDivided(int[] A){
10+
int n=A.length;
11+
int mid=n/2;
12+
int[] left=new int[mid];
13+
int[] right=new int[n-mid];
14+
for(int i=0;i<mid;i++){
15+
left[i]=A[i];
16+
}
17+
for(int j=mid;j<n;j++){
18+
right[j-mid]=A[j];
19+
}
20+
}
21+
22+
public int[] rightDivided(int[] A){
23+
int n=A.length;
24+
int mid=n/2;
25+
int[] left=new int[mid];
26+
int[] right=new int[n-mid];
27+
for(int i=0;i<mid;i++){
28+
left[i]=A[i];
29+
}
30+
for(int j=mid;j<n;j++){
31+
right[j-mid]=A[j];
32+
}
33+
return right;
34+
}
35+
36+
37+
public void MergeSort(int[] A){
38+
int n=A.length;
39+
System.out.println("arr legth=:"+n);
40+
if(n<2) return;
41+
/*
42+
int mid=n/2;
43+
System.out.println("arr mid=:"+mid);
44+
int[] left=new int[mid];
45+
int[] right=new int[n-mid];
46+
for(int i=0;i<mid;i++){
47+
left[i]=A[i];
48+
}
49+
for(int j=mid;j<n;j++){
50+
right[j-mid]=A[j];
51+
}
52+
*/
53+
54+
MergeSort(left);
55+
MergeSort(right);
56+
Merge(left,right,A);
57+
}
58+
59+
private void Merge(int[] L, int[] R, int[] A){
60+
int nL=L.length;
61+
int nR=R.length;
62+
int i=0; int j=0; int k=0;
63+
while(i<nL && j<nR){
64+
if(L[i]<=R[j]){
65+
A[k]=L[i];
66+
i++;
67+
}else{
68+
A[k]=R[j];
69+
j++;
70+
}
71+
k++;
72+
}
73+
//check leftovers on the left
74+
while(i<nL){
75+
A[k]=L[i];
76+
i++;
77+
k++;
78+
}
79+
//check leftovers on the right
80+
while(j<nR){
81+
A[k]=R[j];
82+
j++;
83+
k++;
84+
}
85+
}
86+
87+
public void outputArray(int A[]) {
88+
for (int i = 0; i < A.length; i++) {
89+
System.out.print(A[i] + ", ");
90+
}
91+
}
92+
93+
public static void main(String[] args) {
94+
// TODO Auto-generated method stub
95+
//System.out.println("5/2=: "+(5/2)); System.exit(0);
96+
int[] Array = { 0, 1, 3, 5, 7, 9, 15, 13, 11, 2, 4, 6, 8, 10, 14, 12};
97+
System.out.println("Initial array length: "+Array.length);
98+
MergeSort2 sort = new MergeSort2(Array);
99+
sort.MergeSort(sort.Arr);
100+
sort.outputArray(sort.Arr);
101+
}
102+
103+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/21/202caef574ae001517cea66f72e0b330

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
package study;
2+
3+
public class MergeSort {
4+
5+
int[] Arr;
6+
int countMerge;
7+
8+
// constructor
9+
MergeSort(int[] A) {
10+
this.Arr = A;
11+
this.countMerge = 0;
12+
}
13+
14+
public void divide(int[] A, int low, int high) {
15+
if (low == high)
16+
return;
17+
else {
18+
this.countMerge++;
19+
int mid = (low + high) / 2;
20+
divide(A, low, mid);
21+
divide(A, mid + 1, high);
22+
mergeAndSort(A, low, mid, high);
23+
}
24+
}
25+
26+
private static void mergeAndSort(int A[], int low, int mid, int high) {
27+
int m = mid - low + 1;// num of elements in the first half of Array A
28+
int n = high - (mid + 1) + 1; // num of elements in the second half of
29+
// Array A
30+
int[] firstHalf = new int[m];
31+
int[] secondHalf = new int[n];
32+
33+
// extract the first half of already sorted sub array
34+
for (int i = 0; i < m; i++) {
35+
firstHalf[i] = A[low + i];
36+
}
37+
// extract the second half of already sorted sub array
38+
for (int j = 0; j < n; j++) {
39+
secondHalf[j] = A[mid + 1 + j];
40+
}
41+
// sort and merge the two halves together
42+
int i = 0;
43+
int j = 0;
44+
while (i < m || j < n) {
45+
if (firstHalf[i] < secondHalf[j]) {
46+
A[low++] = firstHalf[i++];
47+
} else {
48+
A[low++] = secondHalf[j++];
49+
}
50+
51+
if (i >= m) {
52+
A[low++] = secondHalf[j++];
53+
continue;
54+
}
55+
if (j >= n) {
56+
A[low++] = firstHalf[i++];
57+
continue;
58+
}
59+
60+
}
61+
}
62+
63+
public void outputArray(int A[]) {
64+
for (int i = 0; i < A.length; i++) {
65+
System.out.print(A[i] + ", ");
66+
}
67+
}
68+
69+
public void outputMergeCounts() {
70+
System.out.println(" ");
71+
System.out.println("num of merge executions: " + this.countMerge);
72+
}
73+
74+
public static void main(String[] args) {
75+
// TODO Auto-generated method stub
76+
int[] Array = { 0, 1, 3, 5, 7, 9, 15, 13, 11, 2, 4, 6, 8, 10, 14, 12 };
77+
MergeSort sort = new MergeSort(Array);
78+
sort.divide(sort.Arr, 0, sort.Arr.length - 1);
79+
sort.outputArray(sort.Arr);
80+
sort.outputMergeCounts();
81+
}
82+
83+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/23/80d7721477ae001517cea66f72e0b330

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package study;
2+
3+
public class MergeSort2 {
4+
int[] Arr;
5+
6+
public void MergeSort(int[] A){
7+
int n=length(A);
8+
if(n<2) return;
9+
int mid=n/2;
10+
int[] left=new int[mid];
11+
int[] right=new int[n-mid];
12+
for(int i=0;i<mid;i++){
13+
left[i]=A[i];
14+
}
15+
for(int j=0;j<(n-mid);j++){
16+
right[j]=A[mid+1+j];
17+
}
18+
MergeSort(left);
19+
MergeSort(right);
20+
Merge(left,right,A);
21+
}
22+
23+
public void Merge(int[] L, int[] R, int[] A){
24+
int nL=L.length;
25+
int nR=R.length;
26+
int i=0, j=0, k=0;
27+
while(i<nL && j<nR){
28+
if(L[i]<=R[j]){
29+
A[k]=L[i];
30+
k++;
31+
i++;
32+
}else{
33+
A[k]=R[j];
34+
k++;
35+
j++;
36+
}
37+
k++;
38+
}
39+
while(i<nL){
40+
A[k]=L[i];
41+
i++;
42+
k++;
43+
}
44+
while(j<nR){
45+
A[k]=R[j];
46+
j++;
47+
k++;
48+
}
49+
}
50+
public static void main(String[] args) {
51+
// TODO Auto-generated method stub
52+
53+
}
54+
55+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/38/3046a95374ae001517cea66f72e0b330

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
package study;
2+
3+
public class MergeSort {
4+
5+
int[] Arr;
6+
int countMerge;
7+
8+
// constructor
9+
MergeSort(int[] A) {
10+
this.Arr = A;
11+
this.countMerge = 0;
12+
}
13+
14+
public void divide(int[] A, int low, int high) {
15+
if (low == high)
16+
return;
17+
else {
18+
this.countMerge++;
19+
int mid = (low + high) / 2;
20+
divide(A, low, mid);
21+
divide(A, mid + 1, high);
22+
mergeAndSort(A, low, mid, high);
23+
}
24+
}
25+
26+
private static void mergeAndSort(int A[], int low, int mid, int high) {
27+
int m = mid - low + 1;// num of elements in the first half of Array A
28+
int n = high - (mid + 1) + 1; // num of elements in the second half of
29+
// Array A
30+
int[] firstHalf = new int[m];
31+
int[] secondHalf = new int[n];
32+
33+
// extract the first half of already sorted sub array
34+
for (int i = 0; i < m; i++) {
35+
firstHalf[i] = A[low + i];
36+
}
37+
// extract the second half of already sorted sub array
38+
for (int j = 0; j < n; j++) {
39+
secondHalf[j] = A[mid + 1 + j];
40+
}
41+
// sort and merge the two halves together
42+
int i = 0;
43+
int j = 0;
44+
while (i < m || j < n) {
45+
if (i >= m) {
46+
A[low++] = secondHalf[j++];
47+
continue;
48+
}
49+
if (j >= n) {
50+
A[low++] = firstHalf[i++];
51+
continue;
52+
}
53+
if (firstHalf[i] < secondHalf[j]) {
54+
A[low++] = firstHalf[i++];
55+
} else {
56+
A[low++] = secondHalf[j++];
57+
}
58+
}
59+
}
60+
61+
public void outputArray(int A[]) {
62+
for (int i = 0; i < A.length; i++) {
63+
System.out.print(A[i] + ", ");
64+
}
65+
}
66+
67+
public void outputMergeCounts() {
68+
System.out.println(" ");
69+
System.out.println("num of merge executions: " + this.countMerge);
70+
}
71+
72+
public static void main(String[] args) {
73+
// TODO Auto-generated method stub
74+
int[] Array = { 0, 1, 3, 5, 7, 9, 15, 13, 11, 2, 4, 6, 8, 10, 14, 12 };
75+
MergeSort sort = new MergeSort(Array);
76+
sort.divide(sort.Arr, 0, sort.Arr.length - 1);
77+
sort.outputArray(sort.Arr);
78+
sort.outputMergeCounts();
79+
}
80+
81+
}

0 commit comments

Comments
 (0)