[JAVA, App] 5.데이터정렬

데이터 정렬

1.정렬의 구분

1) 오름차순(Ascending - 작은 것에서 큰 것 순으로 배치, 기본) 과 내림차순(Descending - 큰 것에서 작은 것 순으로 배치)

2) 알고리즘에 의한 분류

selection sort(선택정렬) : 교재에서 많이 설명, 정렬이 무엇인지 설명하고 제어문 학습하는 용도로 주로 이용, 실무에서느 거의 사용하지 않음

bubble sort

insertion sort

quick sort

shell sort

heap sort

radix sort 등

• 면접이나 코딩 테스트에서는 quick sort를 많이 물어봅니다.

2.selection sort(선택 정렬)

20 30 40 50 10 : 정렬 되지 않은 상태

• 첫번째 위치부터 마지막 바로 앞 위치까지 자신의 뒤에 있는 모든 데이터와 비교해서 더 작은 데이터를 자리 바꿈을 하는 방식으로 데이터를 정렬

1pass(0)  10  30  40  50  20   : 1,2,3,4
2pass(1)  10  20  40  50  30   : 2,3,4
3pass(2)  10  20  30  50  40   : 3,4
4pass(3)  10  20  30  40  50   : 4

int [] ar = {20 30 40 50 10};
int len = ar.length;

//선택 정렬
//기준 위치 반복문
for(int i=0; i< len-1; i=i+1){
    //비교 위치 반복문
    for(j=i+1; j<len; j=j+1){
        if(ar[i] > ar[j]){
            //swap
            int temp = ar[i];
            ar[i] = ar[j];
            ar[j] = temp;
        }
    }
}

3.Bubble Sort

• 최대 n(데이터 개수)-1 회전 동안 맨 앞에서 부터 자신의 바로 뒤에 있는 데이터와만 비교해서 정렬하는 방식
• 1회전이 끝나면 가장 큰 데이터가 맨 뒤로 이동
• 1회전 동안 데이터의 이동이 없으면 정렬이 된 것이므로 중단해도 됩니다.

        int [] ar = {20, 30, 40, 50, 10, 32};
        //버블 정렬은 최대 n(데이터 개수)-1 회전 동안
        //자신의 바로 뒤에 있는 데이터와 비교해서 정렬
        //오름차순이면 뒤의 데이터가 작을 때 swap
        //내림차순이면 뒤의 데이터가 클 때 swap

        //버블 정렬은 가장 큰 데이터가 맨 뒤로 이동하므로 하나의 회전이 끝나면
        //맨 마지막 데이터와는 비교할 필요가 없습니다.
        //1회전 동안 데이터의 이동이 없으면 정렬 종료

        int len = ar.length;

        //최대 n-1 회전
        for(int i=0; i<len-1; i=i+1){
            //1회전 동안의 데이터의 이동 여부를 판별하기 위한 변수
            boolean flag = false;
            //자신의 인접한 데이터와 비교하기 위한 제어문
            for(int j=0; j<len-i-1; j=j+1){
                //뒤의 데이터가 더 작으면 swap
                if(ar[j] > ar[j+1]){
                    int temp = ar[j];
                    ar[j] = ar[j+1];
                    ar[j+1] = temp;
                    //데이터 이동 여부 표시
                    flag = true;
                }
            } 
            //데이터의 이동이 없으면 정렬 종료
            if(flag == false){
                break;
            }
        }

        //데이터 출력
        for(int temp : ar) {
            System.out.print(temp + "\t");
        }