삽입 정렬(Insertion Sort), 퀵 정렬(Quick Sort)

삽입 정렬(Insertion Sort)

• 정렬되어 있는 부분집합에 새로운 원소의 순서를 찾아 삽입하는 방법

출처: GeeksforGeeks

 

삽입 정렬 자바 구현

public class InsertSort {
    public static void main(String[] args) {
        int arr[] = {3, 6, 4, 87, 54, 23, 44, 65, 21, 95};
        InsertionSort is = new InsertionSort();
        is.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.printf(" %d", arr[i]);
        }
        System.out.println();
    }
}

class InsertionSort {
    public void sort(int arr[]) {
        for (int i = 1; i < arr.length; i++) {
            int position = i;
            int tempValue = arr[i];

            while (position > 0 && arr[position - 1] > tempValue) {
                arr[position] = arr[position - 1];
                position--;
            }
            arr[position] = tempValue;

            System.out.printf("\n삽입정렬 %d 단계 : ", i);
            for (int t = 0; t < arr.length; t++) {
                System.out.printf("%3d ", arr[t]);
            }
        }
        System.out.println();
    }
}

 

 

퀵 정렬(Quick Sort)

• 정렬할 전체 원소에 대해서 정렬을 수행하지 않고 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분집합으로 분할한다.
• 왼쪽 부분집합에는 기준 값보다 작은 원소들을 이동시키고, 오른쪽 부분집합에는 기준 값보다 큰 원소들을 이동시킨다.

출처: GeeksforGeeks

 

 

퀵 정렬 자바 구현

public class QuickSort {
    public static void main(String[] args) {
        int arr[] = {32, 41, 64, 24, 76, 94, 23, 54, 20, 11};
        QSort qs = new QSort();
        qs.quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.printf(" %3d", arr[i]);
        }
        System.out.println();
    }
}

class QSort {
    public int partition(int arr[], int begin, int end) {

        int temp;
        int left = begin;
        int right= end;
        int pivot = (begin + end) / 2;
        System.out.printf("\npivot=%d", arr[pivot]);

        while (left < right) {
            while ((arr[left] <= arr[pivot]) && (left <= right)) {
                left++;
            }
            while ((arr[right] > arr[pivot]) && (left <= right)) {
                right--;
            }
            if (left < right) {
                temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;

                if (left == pivot) {
                    return right;
                }
            }
        }
        // left > right 인 경우
        temp = arr[pivot];
        arr[pivot] = arr[right];
        arr[right] = temp;
        return right;
    }

    public void quickSort(int arr[], int begin, int end) {
        if (begin < end) {
            int p = partition(arr, begin, end);
            quickSort(arr, begin, p - 1);
            quickSort(arr, p + 1, end);
        }
    }
}

 

 

삽입 정렬, 퀵 정렬 비교

	최선의 경우	평균적인 경우	최악의 경우
삽입 정렬	O(N)	O(N²)	O(N²)
퀵 정렬	O(N log N)	O(N log N)	O(N²)

 

 

 

 

학습 교재

자바로 배우는 쉬운 자료구조 - 이지영 지음

누구나 자료구조와 알고리즘 - 제이 웬그로우 지음