Java, Selection Sort (선택 정렬), Bubble Sort (거품 정렬) / 정렬 방식

2024-7-9 네이버 클라우드

 

Selection Sort 
선택 정렬

 

 

현재 위치에 들어갈 데이터를 찾아 선택하는 알고리즘.

데이터를 비교하며 찾기 때문에 비교 정렬이다.

서로 교환하는 과정에서 임수 변수가 필요하다. (ex. 변수 temp)

 

[ 방법 ]

1. 리스트에서 최솟값을 찾는다.

2. 최솟값을 맨 앞자리의 값과 교환한다.

3. 맨 앞을 제외한 나머지 값들 중 최솟값을 찾아 위에 방법을 반복한다.

 

int temp;  // 임시 변수

for(int i=0; i<ar.length-1; i++) {
    for(int j=i+1; j<ar.length; j++) {
        if(ar[i] > ar[j]) {
            temp = ar[i]; // 임시 변수에 저장
            ar[i] = ar[j]; // 원래 값 버리고 다른 값 넣기
            ar[j] = temp; // 임시 변수 값 넣기
        }
    }
}

 

 

---

Bubble Sort
거품 정렬

 

정렬 알고리즘.

두개의 인접한 데이터를 비교하는 비교 정렬이다.

서로 교환하는 과정에서 임수 변수가 필요하다. (ex. 변수 temp)

 

[ 방법 ]

1. 앞에서부터 현재 배열값과 바로 다음 배열값을 비교한다.

2. 현재 배열값이 다음 배열값보다 크면 배열값을 교환한다.

3. 다음 배열값으로 이동하며 해당 배열값과 다음 배열값을 비교한다.

4. 위에 방법을 반복한다.

 

int temp;

for(int i=0; i<ar.length-1; i++) {
    for(int j=0; j<ar.length-1-i; j++) {
        if(ar[j]>ar[j+1]) {
            temp = ar[j];
            ar[j] = ar[j+1];
            ar[j+1] = temp;
        }
    }
}

 

 

i=0 일때,	i=1 일때,	i=2 일때,	i=3 일때,
j        j+1 ar[0] >ar[1] ar[1] >ar[2] ar[2] >ar[3] ar[3] >ar[4]	ar[0] >ar[1] ar[1] >ar[2] ar[2] >ar[3]	ar[0] >ar[1] ar[1] >ar[2]	ar[0] >ar[1]

 

출력되는 값들의 규칙을 생각해보면,

i=0 일때,             j=0; j<4; j++
i=1 일때,             j=0; j<3; j++
i=2 일때,             j=0; j<2; j++
i=3 일때,             j=0; j<1; j++

 

으로 4에서 i를 빼면 j를 구할 수 있다.

따라서, ar.length-1(4)에 i를 빼주어 다중 for문에 안쪽 for문 범위로 지정한다.

j < ar.length-1-i

 

 

인접한 두 데이터를 비교하는 것이기 때문에

 

 if(ar[j]>ar[j+1]) {  // 인접한 데이터의 큰값을 비교하고
            temp = ar[j]; // 큰값일 경우 두 데이터를 교환한다.
            ar[j] = ar[j+1];
            ar[j+1] = temp;

}