[알고리즘] 버블, 삽입, 퀵 정렬 알고리즘 구현 (java)

 

1. 버블정렬

 

버블 정렬은 간단한 정렬 알고리즘이다.

 

배열에서 인접한 두 원소를 비교하면서 큰 값을 뒤로 보내는 방식으로 정렬을 수행한다.

 

반복적으로 진행되며 가장 큰 값이 배열의 가장 마지막으로 이동한다.

 

이런 식으로 작은 값들이 순차적으로 정렬되어 나열된다.

 

버블 정렬은 간단하지만 배열의 크기가 커질수록 비효율적인 특징이 있다.

자바 구현

public class BubbleSort {

    public static void bubbleSort(int[] ary) {
        int n = ary.length;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (ary[j] > ary[j + 1]) {
                    int temp = ary[j + 1];
                    ary[j + 1] = ary[j];
                    ary[j] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] ary = { 1, 10, 9, 5, 3, 2, 4, 6, 7, 8 };
        bubbleSort(ary);
        for (int value : ary) {
            System.out.print(value + ",");
        }
        System.out.println();
    }
}

 

2. 삽입정렬

• 초기 배열에 첫 인덱스 부터 시작해서 만약 비교 인덱스보다 크다면 그대로 그리고 작다면 계속 정렬된 데이터의 값을 오른쪽으로 옮겨서 0인덱스나 자기보다 작은 인덱스를 찾을때까지 연산을 수행한다
• 위 연산처럼 한다면 인덱스 보다 큰값이면 삽입 연산 1번에 적게 연산이 수행된다
• → 이말은 즉, 초기 리스트가 오름차순의 형태가 많으면 연산이 적게 수행된다
• → 또 내림차순으로 정렬되어있는 형태가 많이 보인다면 연산을 많이 수행한
• 오름차순으로 정렬된 데이터의 삽입정렬 수행시간은 O(n)
• 최악은 O(n2) ( 내림차순으로 정렬된 데이터

 

3. 퀵정렬

퀵정렬 과정

 

1단계 분할: 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열로 분할한다

2단계 정복: 부분 배열을 정렬한다 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다

1. 피벗을 선정한다 (보통 첫번째 원소 선정
2. 그리고 왼쪽 과 오른쪽을 차례대로 검사한다
3. low 는 pivot보다 큰 값 high 는 pivot보다 작은 값을 찾는다 그리고 바꾼다
4. low 와 high가 교차하면 high와 pivot 과 교차
5. 그러면 pivot 보다 작은 값들이 왼쪽 큰 값들이 오른쪽으로 나뉠 것
6. 그 다음에 순차적으로 분할정복 한다

퀵 정렬은 오름차순으로 정렬되있거나 내림차순으로 정렬되어있는 대이터가 많을 수록 많은 수행시간을 초례한다 평균적으로 NlogN의 수행시간을 초례하지만 bad경우에는 N2까지 초례한다

 

 

자바 구현

public class Sorting {

    public static void insertionSort(int[] ary) {
        int n = ary.length;
        for (int i = 1; i < n; i++) {
            int key = ary[i];
            int j = i - 1;
            while (j >= 0 && ary[j] > key) {
                ary[j + 1] = ary[j];
                j--;
            }
            ary[j + 1] = key;
        }
    }

    public static void quickSort(int[] ary, int start, int end) {
        if (start >= end) return;
        int pivot = ary[start];
        int left = start + 1;
        int right = end;
        while (left <= right) {
            while (left <= right && ary[right] >= pivot) {
                right--;
            }
            while (left <= right && ary[left] <= pivot) {
                left++;
            }
            if (left <= right) {
                int temp = ary[left];
                ary[left] = ary[right];
                ary[right] = temp;
            }
        }
        if (left > right) {
            int temp = ary[start];
            ary[start] = ary[right];
            ary[right] = temp;
            quickSort(ary, start, right - 1);
            quickSort(ary, right + 1, end);
        }
    }

    public static void main(String[] args) {
        int[] ary = { 1, 10, 9, 5, 3, 2, 4, 6, 7, 8 };
        for (int value : ary) {
            System.out.print(value + ",");
        }
        System.out.println();

        insertionSort(ary);
        for (int value : ary) {
            System.out.print(value + ",");
        }
        System.out.println();

        int[] quickAry = { 1, 10, 9, 5, 3, 2, 4, 6, 7, 8 };
        quickSort(quickAry, 0, quickAry.length - 1);
        for (int value : quickAry) {
            System.out.print(value + ",");
        }
        System.out.println();
    }
}

 

이미지 출처

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog (gmlwjd9405.github.io)

[정렬] 삽입 정렬(insertion sort) : 네이버 블로그 (naver.com)

퀵 정렬 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)