[뉴렉처 6기] JAVA│버블 정렬과 선택 정렬(230623)

 

💙 들어가며

---

지난 시간에 자리를 바꾸는 방법에 대해서 간단하게 다루었다.
오늘은 배열과 반복문을 활용해서 본격적으로 값의 순서를 바꾸는 정렬을 해보고,
정렬의 2가지 방법에 대해서 익혀보자.
 
 
 

✏️ 학습내용 정리

---

#버블정렬(뒤부터 오름차순, 내림차순)

가장 큰 값을 맨 뒤로 보내는 작업이다.
마치 부력이 가장 큰 버블이 맨 위로 올라가는 것같은 모양에서 이름이 지어졌다고 한다.

 
 
버블정렬을 하기 위해서는 반복문이 2개 필요하다. (이중 for문)
그리고 2개의 값을 가지고 비교하는 작업이기 때문에
우선 2개의 반복문의 횟수는 값의 갯수(length)보다는 1개가 적다.

하지만 큰 반복문과 작은 반복문의 인덱스는 성격이 다르다.
결론부터 말하자면 바깥의 for문은 인덱스가 고정되어 있는 반면에 (length-1)
안쪽에서 도는 for문은 인덱스가 계속 -1씩 줄어들어야 한다. 
 
 
앞에서부터 순서대로 가장 큰 값을 뒤로 보내고 나면
두 번째로 큰 값을 찾을 때는 이미 정렬된 값은 제외하고 반복시키기 때문에 반복이 진행될 수록 계속 -1회씩 줄어든다.
작업이 진행될 수록 나머지 값들끼리 비교해서 그 중에서 큰 값을 맨 뒤로 보내는 작업이기 때문이다.
 
 
즉, 반복이 진행되면서 맨 뒤로 값을 보내는 방법을 통해서 정렬한다.
🫧버블버블🫧

기준점이 계속 뒤로 이동하면서, 뒤에서부터 정렬한다.

 
 
 
일단 틀렸던 풀이부터 확인해보자. 인덱스가 잘못 되었다.

❌ 틀린 풀이
💯 포인트: 두 for문의 기본값은 size-1이다.

두번째 for문에서 size에서 1을 안빼주고 바로 i를 빼면
우리가 원래 돌려야 하는 횟수보다 1회를 더 돌리게 된다.
그렇게 되면 100이 갑자기... 사라짐?..;;

for(int i=0; i<size-1; i++) {    
    for(int j=0; j<size-i; j++)
        if(nums[j]>nums[j+1]) {
            int temp = 0;
            temp = nums[j];
            nums[j] = nums[j+1];
            nums[j+1] = temp;
        }
}			
for(int i=0; i<size; i++)
    System.out.printf("%d, ", nums[i]);

⭕ 출력결과:
0이 나왔었던 이유는 데이터 파일 맨 뒤에 공백이 있었기 때문에
100과 공백값을 비교한 이클립스가 0을 출력한 것 같다.
(원래 0자리에 100이 있어야 함)

20, 0, 23, 46, 46, 50, 50, 57, 70, 80, 82, 90,

 
 
헷갈렸던 부분은 size-1로만 했었을 때에도 원하는 결과값이 나왔었기 때문이다.

💯 포인트: 반복 횟수를 최대한 효율적으로 줄여보자.

🚨 헷갈렸던 풀이
두번째 for문에서 (size-1)에서 i를 안 빼주면
돌리는 횟수가 줄어들지 않고 계속 돌아서
결과는 제대로 나오지만
뒤에 이미 정렬이 끝났는데 의미없게 계속 돌게 됨
    
for(int i=0; i<size-1; i++) {    
    for(int j=0; j<size-1; j++)
        if(nums[j]>nums[j+1]) {
            int temp = 0;
            temp = nums[j];
            nums[j] = nums[j+1];
            nums[j+1] = temp;
        }
}			
for(int i=0; i<size; i++)
    System.out.printf("%d, ", nums[i]);


⭕ 옳은 풀이
원래 돌려야 하는 크기는 (size-1)이다
여기서 i만큼씩 계속 덜 돌릴 것이다.
왜냐하면 한 회씩 돌 때마다
맨 끝에 것은 정렬이 이미 끝났으니깐
다시 정렬할 필요가 없다!

for(int i=0; i<size-1; i++) {
    for(int j=0; j<(size-1)-i; j++)
        if(nums[j]>nums[j+1]) {
            int temp = 0;
            temp = nums[j];
            nums[j] = nums[j+1];
            nums[j+1] = temp;
        }
}			
for(int i=0; i<size; i++)
    System.out.printf("%d, ", nums[i]);

⭕ 출력결과:

20, 23, 46, 46, 50, 50, 57, 70, 80, 82, 90, 100,

 
늘 헷갈리지만 i이든, j이든 인덱스는 0부터 시작한다.
항상 처음부터(0번째 index부터) 비교하는 것이고 전체적인 횟수가 줄어드는 것이다.
 
 
 

#선택정렬(앞부터 오름차순, 내림차순)

선택정렬은 특정한 값 1개를 찾아서 그 값을 특정한 위치의 것과 바꿔주는 것이다.
일단 처음에 의미만 놓고 보았을 때에는 전체가 다 정렬된다기 보다는 선택된 것만 정렬해준다는 점에서
정렬이라기 보다는 교환의 느낌이 강하게 느껴졌다.
 
 

 
 
이것도 역시 원하는 값을 반복을 통해  찾아야 하고 위치를 바꿔준다는 점에서 2개의 for문이 필수이다.
그리고 2개 for문의 인덱스 i와 j는 반복되는 횟수가 다르다.
고정된 횟수 안에서 반복하는 것(바깥 for(i))과 반복 횟수가 변하는 것(안쪽 for(j))을 잘 구분해야 한다.
 
그런데 여기에 최소값을 찾아서 라거나 최대값을 찾아서라는 식의 조건이 들어가면
그 값을 찾을 인덱스(조건변수)가 추가로 하나 더 필요하게 된다.
총 3개의 인덱스(i, j, 조건변수)가 하나의 식을 위해 필요하다.
그리고 이 조건을 활용해서 반복시키면 위의 버블정렬과 같이 오름차순, 내림차순이 가능해진다.
 

 
 
버블정렬과 다른 점은 선택정렬은 선택한 값을 현재 위치와 바꿔주는 방식을 사용하기 때문에
앞에서부터 정렬이 된다는 점이다.

기준점이 계속 뒤로 이동하면서, 앞에서부터 정렬한다.

 
여기서도 틀린 풀이부터 확인해보자, minIndex라는 변수의 용도를 제대로 파악하지 못했다.
minIndex는 변수의 역할도 하지만 인덱스의 역할도 하고 있다.

❌ 틀린 풀이:
minIndex를 for문 안에 같이 선언하고 ++했다.
밑에서 minIndex가 밑에서 변동되는 값이므로
for문 안에서 또 값이 변해서는 안된다.

minIndex같은 경우 j와 같이 1씩 증가하지만
밑에서 값이 대입되고 변하기 때문에
for문안에서 같이 ++이 되어버리면 값이 계속 바뀌게 된다.

즉, 여기서 minIndex는 변수의 역할도 하지만,
인덱스의 역할도 하고 있는 것!


for(int j=0, minIndex=0; j<size-1; j++, minIndex++) {
    for(int i=0; i<size-1-j; i++) {
        if(nums[minIndex]>nums[i+1+j])
            minIndex = i+1+j;
    }//for i
    System.out.printf("%d, ", minIndex);
    int temp = nums[j];
    nums[j] = nums[minIndex];
    nums[minIndex] = temp;
}// for j
System.out.println();

⭕ 출력결과:

원본 파일: 100 23 46 82 57 90 50 46 80 20 50 70
저장된 파일: 20 46 46 23 50 50 70 0 0 0 0 57
(비교해야 할 minIndex가 바뀌다 보니 영역을 벗어난 null값과 비교가 되었다.)
(참고로 이 배열은 15개까지만 출력이 될 뿐 방 크기 자체는 100개이다.)

 
 
때문에 minIndex를 j로 고정하여 값이 밑에서 어떻게 변동이 되었든 다시 바깥 for문이 돌기 시작할 때는
j로 초기화를 해주어야 한다. (인덱스로서 사용할 것이기 때문!) 
 
즉, for문 안에 선언해서 for문이 돌면서 ++하면 안됨!

⭕ 옳은 풀이:
int minIndex = j로 한다.
밑에서 minIndex가 밑에서 변동되는 값이므로
같이 for문안에 선언해서 minIndex++을 하면 안된다.


for(int j=0; j<size-1; j++) {
    int minIndex = j;
    for(int i=0; i<size-1-j; i++) {
        if(nums[minIndex]>nums[i+1+j])
            minIndex = i+1+j;
    }//for i
    System.out.printf("%d, ", minIndex);
    int temp = nums[j];
    nums[j] = nums[minIndex];
    nums[minIndex] = temp;
}// for j
System.out.println();

⭕ 출력결과:

원본 파일: 100 23 46 82 57 90 50 46 80 20 50 70
저장한 파일: 20 23 46 46 50 50 57 70 80 82 90 100

 
 
인덱스의 인덱스에 의한 인덱스를 위한 정렬식들. 익숙해질 필요가 있겠다.
 

💙 마치며

---

1.
#버블정렬
기준점이 이동하면서 맨 뒤로 정렬값을 보낸다.
뒤에서부터 정렬된다.
i와 i+1만 비교하고 자리 바꿈
 
#선택정렬
기준점이 이동하면서 맨 앞으로 정렬값을 보낸다.
앞에서부터 정렬된다.
(minIndex와 i+1+j의 값을 비교하고) i와 minIndex 자리 바꿈
 
 
2.
고정되는 값과 변하는 값을 깨달아야 한다.
변하는 값을 고정된 값으로 사용하고 싶다면 다시 초기화를 해주어야 한다.
 
반복문을 배우면서 제일 헷갈리는 것이 인덱스이다.
내가 i와 j중에 어떤 값을 바깥으로 돌릴 지를 선택하고 나면
바깥 i는 상대적으로 고정된 값이고, 안의 j는 계속 횟수가 줄어드는 등의 영향을 받는 녀석으로 인지한 뒤에
제어문을 잘 운용해야겠다.