자바(java)의 정렬 알고리즘(버블, 선택, 삽입)

정렬 알고리즘.

기초적인 방법 : 버블정렬, 선택정렬, 삽입정렬

***Array.sort()함수는 듀얼피봇 퀵정렬이라는 방식을 사용함. 가장 빠르고 효율적이지만 너무 어려운 내용이라 그냥 넘어간다.

 

버블정렬

가장 비효율적이지만 만들기 쉽고 간단해서 많이 쓰인다.

인덱스 0 부터 인덱스 끝까지 대/소를 비교하고, 만약 상대가 더 크거나 작다면 자신과 데이터를 교환하는 방식. 교환하고도 계속 비교 하지만, 이때도 기준은 인덱스다.

예를 들어보자.

배열 a[ ]를 오름차순으로 정리하고 있다.

a[2]의 값을 a[3], a[4] ... a[n]까지 계속 비교하는 도중,  a[10]이 자신보다  더 작다는 것을 발견했다.

그럼 이어서 a[2]의 데이터와 a[10]의 데이터를 맞교환한다.

그리고 이어서 바뀐 a[2]를 계속해서 a[11]과 비교한다. 만약 이후에도 자신보다 더 작은 데이터를 발견한다면, 그 데이터와 자신의 데이터를 교환한다.

public class ex61 {
    public static void main(String[] args) {
        //정렬 알고리즘
        //대표적인 방법 : 버블정렬, 선택정렬, 삽입정렬
        //Arrays.sort()함수 안에도 정렬알고리즘 - 듀얼피봇 퀵정렬

        //1. 버블정렬
        // 모든 자릿수를 오른쪽자리와 비교해서 맞교환(치환)하는 방식
        int[] numbers = { 9, 8, 1, 3, 2 };
        //연습문제 42 - 2중 반복문
        //모든 자릿수를 비교해보자.
        //출력: 9:8 9:1 9:3 9:2
        //     8:1 8:3 8:2
        //     1:3 1:2
        //     3:2
        for(int i=0; i<numbers.length; i++){
            for(int j=i+1; j<numbers.length; j++){
                System.out.print( numbers[i] + ":" );
                System.out.print( numbers[j] + " " );
            }
            System.out.println();
        }
        //연습문제 43
        //버블 정렬-오름차순 을 구현해보자.
        //모든 자릿수를 비교해서, 오른쪽값이 더 작으면
        //치환한다.(자리 이동)
        //정렬된 결과를 출력하시오.
        for(int i=0; i<numbers.length; i++){
            for(int j=i+1; j<numbers.length; j++){
                //i: 왼쪽값  j: 오른쪽값
                //오름차순은 맨 앞에 제일 작은 값이 위치.
                if( numbers[j] < numbers[i] ){
                //내리차순 정렬은 부호만 반대로 하면 됨.
                    int temp = numbers[j];
                    numbers[j] = numbers[i];
                    numbers[i] = temp;
                }
            }
        }
        for( int num : numbers ){
            System.out.println( num );
        }
    }
}

 

2. 선택정렬

최대 최소값 찾기와 비슷한 방법을 사용한다.

1. 새로운 변수(minIndex)를 만들아 for문의 i값을 할당한다.

2. 다시 for문을 사용해 a[ i ] 보다 작은 변수를 찾는다.

3. 더 작은 값을 발견하면, 그 인덱스 번호를 이전에 설정한 변수(minIndex)에 저장한다.

4. a[ i ] 의 값을 새로운 변수(tmep)에 저장하고, a[ i ]보다 작은 a[ f ]의 값을 a[ i ]에 넣는다.

5. a[minIndx]에 temp의 값을 다시 할당한다.

public class ex62 {
    public static void main(String[] args) {
        //2. 선택정렬
        //  인덱스변수 minIndex에 최소값 인덱스를 설정하고,
        //  minIndex를 이용해서 맞교환 하는 방식.
        int[] nums = { 9, 8, 1, 3, 2 };
        int minIndex;
        for(int i=0; i<nums.length-1; i++){
            minIndex = i;
            System.out.println("minIdx:"+minIndex);
            for(int j=i+1; j<nums.length; j++){
                if( nums[j] < nums[minIndex] ){
                    //더 작은 값을 발견! => minIndex값을 변경!
                    minIndex = j;
                }
            }
            //minIndex값을 이용해서 맞교환한다.
            int temp = nums[i];
            nums[i] = nums[minIndex];
            nums[minIndex] = temp;
        }
        for( int num : nums )
            System.out.println( num );
    }
}

 3. 삽입정렬

인덱스 번호 1(두번째 데이터) 부터 비교를 시작한다.

자신보다 왼쪽의 숫자(인덱스 번호 0) 과 자신을 비교한 뒤, 더 작은 값이면 맞교환한다.

이후 인덱스 번호를 2로 올려서 다시 자신의 왼쪽 데이터들(인덱스 번호가 더 낮은 데이터들) 과 자신을 비교한뒤, 맞교환한다.

교환할 값을 가진 key값을 이용한다.

public class ex63 {
    public static void main(String[] args) {
        //3. 삽입 정렬
        //  인덱스 1(두번째)부터 정렬을 시작하고,
        //  자기보다 왼쪽에 있는 값들과 비교하여,
        //  더 작은 값이면 맞교환한다.
        //  교환할 값을 가진 key변수를 이용함.
        int[] nums = { 9, 8, 1, 3, 2 };
        int key;
        for(int i=1; i<nums.length; i++){
            key = nums[i]; //8
            int j = i - 1;
            while( j >= 0 && nums[j] > key ){
                nums[ j + 1 ] = nums[j]; //9 9 1 3 2
                j--; //증감문
            }
            nums[ j + 1 ] = key; //8 9 1 3 2
        }
        for( int num : nums )
            System.out.println( num );
    }
}