정렬 - 삽입, 퀵, 병합

[코드]

public class SortTest {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        final int nums[] = { 25, 5, 37, 1, 61, 11, 59, 15, 48, 19 };
 
        Sorting s = new Sorting();
 
        
        s.Insert(nums);
        s.Quick(nums, 0, nums.length - 1);
        s.Merge(nums, 0, nums.length - 1);
    }
 
}

Sort Test 메인 클래스를 하나 만들고, 차례대로 삽입, 퀵, 머지정렬 함수를 호출했다.

class Sorting {
 
    int list[] = new int[10];
    static int count = 0;
 
    public void Insert(int nums[]) {
 
        System.arraycopy(nums, 0, list, 0, nums.length);
        
        System.out.println("----------- insertion sort ------------");
        PrintResult(list); //원래 배열 출력
        InsertSorting(list); //소팅
        
        
        System.out.println(); // 결과출력
        PrintResult(list); // 결과 출력
        System.out.println("Total number of comparison = " + count);
        count = 0;
    }
 
    public void Merge(int nums[], int s, int e) {
        
        System.arraycopy(nums, 0, list, 0, nums.length);
        
        System.out.println("----------- merge sort ----------------");
        PrintResult(list);
        MergeSorting(list, s, e);
        
        
        System.out.println();
        PrintResult(list);
        System.out.println("Total number of comparison = " + count);
        count = 0;
    }
 
    public void Quick(int nums[], int s, int e) {
        
        System.arraycopy(nums, 0, list, 0, nums.length);
        
        System.out.println("----------- quick sort ----------------");
        PrintResult(list);
        QuickSorting(list, s, e);
        
        
        System.out.println();
        PrintResult(list);
        System.out.println("Total number of comparison = " + count);
        count = 0;
    }
 
    public static void InsertSorting(int nums[]) {
 
        for (int i = 1; i < nums.length; i++) {
            int pivot = nums[i];
            for (int j = i - 1; j >= 0; j--) {
                if (pivot < nums[j]) { // pivot 이 비교값보다 작을때에는 뒤로 밀어주기
                    count++;
                    nums[j + 1] = nums[j];
                    if (j == 0)
                        nums[j] = pivot;
                } else { // pivot 이 비교값보다 클때에는 바로 뒤에 삽입하기
                    nums[j + 1] = pivot;
                    break;
                }
            }
 
            for (int j = 0; j < nums.length; j++)
                System.out.printf("%4d", nums[j]);
            System.out.println();
        }
 
    }
 
    public static void QuickSorting(int nums[], int s, int e) {
 
        if (s < e) {
 
            int mid = partition(nums, s, e); // Partition
 
            // 파티션 후 중간 출력
            for (int k = 0; k < nums.length; k++) {
                if (k < s || k > e)
                    System.out.print("    ");
                else {
                    System.out.printf("%4d", nums[k]);
                }
            }
            System.out.println();
            if (mid != -1) {
                QuickSorting(nums, s, mid - 1); // 왼쪽 정렬
                QuickSorting(nums, mid + 1, e); // 오른쪽 정렬
            }
        }
    }
 
    public static int partition(int nums[], int s, int e) {
 
        // s : 배열 시작
        // e : 배열 끝
        int pivot = nums[s];
        int low = s + 1;
        int high = e;
 
        while (low <= high) { // low 보다 high가 작거나 같을때 반복
            while (pivot > nums[low]) { // 왼쪽부터 비교
                count++;
                low++;
            }
            while (pivot < nums[high]) { // 오른쪽 비교
                count++;
                high--;
            }
 
            if (low <= high) { // low 번째 값과 high 번째 값을 바꿔주기
                int temp = nums[low];
                nums[low] = nums[high];
                nums[high] = temp;
                low++;
                high--;
            }
        }
 
        // 마무리로 high 번째와 pivot 의 자리를 교체한 후, 현재 pivot 이 들어간 자리를 return 해준다.
        int temp = nums[high];
        nums[high] = nums[s];
        nums[s] = temp;
        return high;
    }
 
    public static void MergeSorting(int nums[], int s, int e) {
 
        if (s < e) { // 시작점이 끝나는점보다 작을때만 수행해야하고
 
            int mid = (s + e) / 2;
            MergeSorting(nums, s, mid);
            MergeSorting(nums, mid + 1, e);
            Merging(nums, s, mid, e);
 
        }
    }
 
    public static void Merging(int nums[], int s, int mid, int e) {
 
        int tmp[] = new int[e + 1]; // 임시배열 만들어주기
 
        int i = s; // 앞배열 첫부분
        int j = mid + 1; // 뒷배열의 첫부분
        int t = 0;
 
        while (i <= mid && j <= e) {
            count++;
            if (nums[i] <= nums[j])
                tmp[t++] = nums[i++];
            else
                tmp[t++] = nums[j++];
        }
 
        while (i <= mid)
            tmp[t++] = nums[i++];
        while (j <= e)
            tmp[t++] = nums[j++];
 
        i = s;
        t = 0;
        while (i <= e) {
            nums[i++] = tmp[t++];
        }
 
        for (int k = 0; k <= e; k++) {
            if (k < s || k > e)
                System.out.print("    ");
            else {
                System.out.printf("%4d", nums[k]);
            }
        }
        System.out.println();
 
    }
 
    public static void PrintResult(int nums[]) {
 
        
        for (int j = 0; j < nums.length; j++)
            System.out.printf("%4d", nums[j]);
        System.out.println();
 
    }
}
 

printf 함수는, 매일 댓글을 달아주시는 이웃님의 코드에서 배웠따 핳. 공백 똑같이 해주는거 써본적이 없었는데 신세계!

그리고, 또 배열복사를 몰라서 ㅋㅋㅋ...이것도 이웃님의 코드에서 배웠다 ㅠㅠ 진짜 내가 왜 여태껏 한번도 안써봤는지 모르겠지만... JAVA 다시 공부해야 될 듯 ㅜㅜ

학교 전공책도 찾아보고 했는데 머리에 잘 안들어왔다 ㅠ_ㅠ

이해하고 짜긴했지만 내일 되면 왠지 또 사라질 것 같은 예감ㅋㅋㅋ

[결과창]

결과는 잘 나왔다! ㅎㅎ 졸려...이만 자야지 ㅠ_ㅠ