School algo02 mergeSort, timsort 풀이코드

Merge sort에 관한 코드가 여러 폼이 존재하여 각각의 특징을 명확히 공부하기 위해 남겨놓는다. 파이썬으로 코딩하고 그것을 각각 자바 코드로 변환해 보았다.

###병합정렬1 가장 대표적인 폼의 병합정렬

def merge(arr, f, l):
    if(f<l):
        m=(f+l)//2
        merge(arr, f, m)
        merge(arr, m+1, l)
        conquer(arr, f, m, l)

def conquer(arr, f, m, l):
    front=f
    rear=m+1
    temp=[]
    while(front<=m and rear<=l):
        if(arr[front]<=arr[rear]):
            temp.append(arr[front])
            front+=1
        else:
            temp.append(arr[rear])
            rear+=1
    while(front<=m):
        temp.append(arr[front])
        front+=1
    while(rear<=l):
        temp.append(arr[rear])
        rear+=1
    front=f
    i=0
    while(front<=l):
        arr[front]=temp[i]
        front+=1
        i+=1
arr=[3,2,1,3,2,66,4,23,45,43]
print(arr)
merge(arr, 0, len(arr)-1)
print(arr)
            
#병합정렬2 (배열을 반환하고 arr에는 변화를 주지않음)
def merge(arr):
    if(len(arr)<=1):
        return arr
    mid=len(arr)//2
    left=merge(arr[ : mid])
    right=merge(arr[mid : ])
    front=0
    rear=0
    temp=[]
    while(front<len(left) and rear<len(right)):
        if(left[front]<=right[rear]):
            temp.append(left[front])
            front+=1
        else:
            temp.append(right[rear])
            rear+=1
    while(front<len(left)):
        temp.append(left[front])
        front+=1
    while(rear<len(right)):
        temp.append(right[rear])
        rear+=1
    return temp

arr=[3,2,1,3,2,66,4,23,45,43]
#arr자체갖 변하는 것이 아니므로 아래코드 쓸모없음   
# print(arr)
# merge(arr, 0, len(arr)-1)
# print(arr)
print(arr)#비교를 위해
print(merge(arr))
 

#병합정렬3. 더 파고들어가지 않는 병합정렬.이미 정렬된 2개의 배열을 
#하나의 정렬된 배열로 반환함
def merge(a,b):
    aP=0
    bP=0
    c=[]
    while(aP<len(a) and bP<len(b)):
        if(a[aP]<=b[bP]):
            c.append(a[aP])
            aP+=1
        else:
            c.append(b[bP])
            bP+=1
    while(aP<len(a)):
        c.append(a[aP])
        aP+=1
    while(bP<len(b)):
        c.append(b[bP])
        bP+=1
    return c

arr=[2,4,6,6,6,6,8,10]
arr2=[1,3,5,5,5,7,9]
#arr자체갖 변하는 것이 아니므로 아래코드 쓸모없음   
# print(arr)
# merge(arr, 0, len(arr)-1)
# print(arr)
print(arr)#비교를 위해
print(arr2)#비교를 위해
print(merge(arr,arr2))

아래는 위의 코드를 각각 자바로 변형한 코드들

////병합정렬1 가장 대표적인 폼의 병합정렬
public class TestingPleaseDeleteAll {

	public static void main(String[] args) {
		int[] arr = { 3, 2, 1, 3, 2, 66, 4, 23, 45, 43 };
		for (int element : arr)
			System.out.print(element + " ");
		System.out.println();
		merge(arr, 0, arr.length - 1);
		for (int element : arr)
			System.out.print(element + " ");
		System.out.println();

	}

	private static void merge(int[] arr, int front, int rear) {
		if (front < rear) {
			int mid = (front + rear) / 2;
			merge(arr, front, mid);
			merge(arr, mid + 1, rear);
			conquer(arr, front, mid, rear);
		}
	}

	private static void conquer(int[] arr, int front, int mid, int rear) {
		int f = front;
		int r = mid + 1;
		int i = 0;
		int[] temp = new int[arr.length];
		while (f <= mid && r <= rear) {
			if (arr[f] <= arr[r]) 
				temp[i++] = arr[f++];
			else 
				temp[i++] = arr[r++];
			
		}
		while (f <= mid) 
			temp[i++] = arr[f++];
		while (r <= rear) 
			temp[i++] = arr[r++];
		f = front;
public class TestingPleaseDeleteAll  {
	public static void main(String[] args) {
		Integer[] arr = { 3, 2, 1, 3, 2, 66, 4, 23, 45, 43 };
		for (Integer element : arr)
			System.out.print(element + " ");
		System.out.println();
		Integer[]result=merge(arr);
		for (Integer element : result)
			System.out.print(element + " ");
		System.out.println();
	}

	private static Integer[] merge(Integer[] arr) {
		if(arr.length<2)
			return arr;
		int mid=arr.length/2;
		Integer[]farr=Arrays.copyOfRange(arr, 0, mid);
		Integer[]rarr=Arrays.copyOfRange(arr, mid, arr.length);
		farr=merge(farr);
		rarr=merge(rarr);
		int f=0;
		int r=0;
		int i=0;
		Integer[]temp=new Integer[arr.length];
		while(f<farr.length&& r<rarr.length) {
			if(farr[f]<=rarr[r])
				temp[i++]=farr[f++];
			else
				temp[i++]=rarr[r++];
		}
		while(f<farr.length)
			temp[i++]=farr[f++];
		while(r<rarr.length)
			temp[i++]=rarr[r++];
		return temp;
	}
}

		i = 0;
		while (f <= rear) 
			arr[f++] = temp[i++];		
	}
}

////병합정렬2 (배열을 반환하고 arr에는 변화를 주지않음)
//
//
public class TestingPleaseDeleteAll  {
	public static void main(String[] args) {
		Integer[] arr = { 3, 2, 1, 3, 2, 66, 4, 23, 45, 43 };
		for (Integer element : arr)
			System.out.print(element + " ");
		System.out.println();
		Integer[]result=merge(arr);
		for (Integer element : result)
			System.out.print(element + " ");
		System.out.println();
	}

	private static Integer[] merge(Integer[] arr) {
		if(arr.length<2)
			return arr;
		int mid=arr.length/2;
		Integer[]farr=Arrays.copyOfRange(arr, 0, mid);
		Integer[]rarr=Arrays.copyOfRange(arr, mid, arr.length);
		farr=merge(farr);
		rarr=merge(rarr);
		int f=0;
		int r=0;
		int i=0;
		Integer[]temp=new Integer[arr.length];
		while(f<farr.length&& r<rarr.length) {
			if(farr[f]<=rarr[r])
				temp[i++]=farr[f++];
			else
				temp[i++]=rarr[r++];
		}
		while(f<farr.length)
			temp[i++]=farr[f++];
		while(r<rarr.length)
			temp[i++]=rarr[r++];
		return temp;
	}
}

//병합정렬3. 더 파고들어가지 않는 병합정렬.이미 정렬된 2개의 배열을 
//하나의 정렬된 배열로 반환함
public class TestingPleaseDeleteAll{
	public static void main(String[] args) {
		int[]arr= {2,4,6,6,6,6,8,10};
		int[]arr2= {1,3,5,5,5,7,9};
		int[]result=merge(arr, arr2);
		for(int element: arr)
			System.out.print(element+" ");
		System.out.println();
		for(int element: arr2)
			System.out.print(element+" ");
		System.out.println();
		for(int element: result)
			System.out.print(element+" ");
		System.out.println();
	}
	private static int[] merge(int[]arr, int[]arr2) {
		int i=0;
		int j=0;
		int k=0;
		int[]temp=new int[arr.length+arr2.length];
		while(i<arr.length && j<arr2.length) {
			if(arr[i]<=arr2[j])
				temp[k++]=arr[i++];
			else
				temp[k++]=arr2[j++];
		}
		while(i<arr.length)
			temp[k++]=arr[i++];
		while(j<arr2.length)
			temp[k++]=arr2[j++];
		return temp;
	}
}