[JAVA] #3-2 정렬(Sort)

1. 정렬의 종류와 방식

 

- 정렬 유형
  오름차순 ascending 1->10 A->Z a->z ㄱ->ㅎ
  내림차순 descending

- 정렬방식
  삽입정렬 : insertion sort
  선택정렬 : selection sort
  버블정렬 : bubble sort

 

 

2. 정렬의 알고리즘

 

 1) 선택정렬(selection sort) 알고리즘

  9 8 7 6 5 -> 5 6 7 8 9
  가장 앞자리 수가 자기보다 더 작은 가장 최소값과 자리를 바꿔가며
  차례로 정렬을 하는 방법
  
  ex)
  9 8 7 6 5
  5 8 7 6 9 > 9가 최소값 5를 찾아서 바꿈
  --------- step 1
  5 8 7 6 9
  5 6 7 8 9 > 8이 다음 최소값 6을 찾아서 바꿈
  --------- step 2
  5 6 7 8 9
  5 6 7 8 9 > 7보다 더 작은 최소값이 없음
  --------- step 3
  5 6 7 8 9
  5 6 7 8 9 > 8보다 더 작은 최소값이 없음
  --------- step 4
  5 6 7 8 9
  5 6 7 8 9 > 9보다 더 작은 최소값이 없음
  --------- step 5, 정렬 완료

 

 - 코드로 구현하기

// selection sort
for(int a=0; a<size-1; a++) {
    for(int b=a+1; b<size; b++) {
        if(su[a]>su[b]) {			// 오름차순
            int temp=su[a];
            su[a]=su[b];
            su[b]=temp;					
        } // if end
    } // for end
} // for end

for (int idx=0; idx<size; idx++) {
    System.out.print(su[idx]);
} //for end

 

 2) 버블정렬(bublble sort) 알고리즘

  9 8 7 6 5 -> 5 6 7 8 9
  앞자리수부터 순차적으로 하나씩 비교를 해가면서 정렬하는 방식(거품이 생기듯).

 

  ex)

  9 8 7 6 5
  8 9 7 6 5
  8 7 9 6 5 
  8 7 6 9 5
  8 7 6 5 9
  ---------- step 1 : 9로 모든 수 비교해서 자리 바꾸기
  8 7 6 5 9
  7 8 6 5 9
  7 6 8 5 9
  7 6 5 8 9
  ---------- step 2 : 8로 모든 수 비교해서 자리바꾸기
  7 6 5 8 9
  6 7 5 8 9
  6 5 7 8 9 
  ---------- step 3 : 7로 모든 수 비교해서 자리 바꾸기
  6 5 7 8 9 
  5 6 7 8 9
  ---------- step 4 : 5로 모든 수 비교해서 자리 바꾸기
  5 6 7 8 9
  ---------- 정렬 완료

 

 

 - 코드로 구현하기

// bubble sort
for(int a=size-2; a>=0; a--) {
    for(int b=0; b<=a; b++) {
        if(su[b]<su[b+1]) { // 내림차순
            int temp=su[b+1];
            su[b+1]=su[b];
            su[b]=temp;
        } // if end
    } // for end
} // for end

for (int idx2=0; idx2<size; idx2++) {
    System.out.print(su[idx2]);
} //for end

 

 3) 삽입정렬(insertion sort) 알고리즘

  9 8 7 6 5 -> 5 6 7 8 9
 비교할 키값을 앞에서 전환한 모든 키 값과 한번씩 다 비교하는 방식

 

 9 8 7 6 5

 8 9 7 6 5

 ------------ step1 : 키값은 8(9가 아니다), 8이 9와 비교

 8 9 7 6 5

 8 7 9 6 5

 7 8 9 6 5

 ------------ step 2 : 키값은 7, 7이 앞에 있는 9와 8을 비교

 7 8 9 6 5

 7 8 6 9 5

 7 6 8 9 5

 6 7 8 9 5

 ------------ step 3 : 키값은 6, 6이 앞에 있는 7, 8, 9와 비교

 6 7 8 9 5

 6 7 8 5 9

 6 7 5 8 9

 6 5 7 8 9

 5 6 7 8 9

 ------------ step 4 : 키값은 5, 5가 앞에 있는 6, 7, 8, 9와 비교

 5 6 7 8 9

 ------------ 오름차순 정렬 완료

 

 

 

3. 메서드로 정렬하기

 Arrays.sort로도 정렬이 가능하다.

int [] lotto = {3, 7, 4, 15, 28, 13};
Arrays.sort(lotto);
for(int i=0; i<lotto.length; i++) {
    System.out.print(lotto[i]);
    System.out.print(" ");
}