[BOJ/백준] 정렬_ 2750번_ 선택정렬(Selection Sort)+버블정렬(Bubble Sort)_삽입 정렬(Insertion Sort)

1. 문제 번호 2750

 

 

 

 

---

 

 

 

 

 

2. 문제 풀이

 

 

한줄 평가

•   선택정렬 (배열중 최소값을 찾아 맨 앞자리와 스왑)
•   버블정렬 (1회의 반복이 0...부터 끝까지 옆의 수와 큰 수를 반복적으로 뒤로 보낸다.)
•   삽입정렬 (1회의 반복이 1...부터 앞의 값과 비교하여 작으면 반복적으로 앞으로 보낸다.) 

 

 

 

문제를 먼저 정확히 파악

 

•  

 

 

 

나의 문제풀이 방식 및 순서

 

 * 나의 다양한 학습이 우선이기 때문에 다양한 방법을 생각 *

 

1. 이중 for문을 활용한다. 두 번째 for문은  최소값을 찾아서 첫 번째 for문에서 스왑처리

       for문의 형태 + 선택 정렬하는 로직 주의

for (int i = 0; i < numAry.length; i++) {
    minValue = Integer.MAX_VALUE;
    temp = Integer.MAX_VALUE;
    index = Integer.MAX_VALUE;

    for (int j = i; j < numAry.length; j++) {
        if(minValue > numAry[j]){
            minValue = numAry[j];
            index = j;
        }
    }
    temp = numAry[i];
    numAry[i] = numAry[index];
    numAry[index] = temp;
}

 

1. 이중 for문을 활용한다. 첫 번째 for문은 반복횟수를 나타내고 두 번째 for문으로 버블정렬 처리
   
   인덱스 주의 + for문의 형태 + 버블 정렬하는 로직 주의

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

 

 

 

1. 이중 for문을 활용한다. 첫 번째 for문은 반복횟수를 나타내고 두 번째 for문으로 버블정렬 처리
   
   인덱스 주의 + for문의 형태 + 버블 정렬하는 로직 주의

for(int i = 1; i < numAry.length; i++){
    int j = i;
    int temp = numAry[j];

    while(j > 0 && numAry[j-1]>numAry[j]){
        temp = numAry[j-1];
        numAry[j-1] = numAry[j];
        numAry[j] = temp;
        j--;
    }
}

 

 

---

3. 소스 인증

 

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        //Integer N = Integer.valueOf(); //wrapper객체로 반환
        //String str1 = Integer.toString(123);
        //String str1 = String.valueOf(123);
        /*
        String.valueOf는 내부적으로 Integer.toString()을 사용하지만
        null값의 경우 에러가 발생하지 않는다.
        */
        
        
        int [] numAry = new int[N];

        for (int i = 0; i < N;i++ ) {
            numAry[i] = Integer.parseInt(br.readLine());
        }
        int index, temp, minValue;
        
        for (int i = 0; i < numAry.length; i++) {
            minValue = Integer.MAX_VALUE;
            temp = Integer.MAX_VALUE;
            index = Integer.MAX_VALUE;
            
            for (int j = i; j < numAry.length; j++) {
                if(minValue > numAry[j]){
                    minValue = numAry[j];
                    index = j;
                }
            }
            temp = numAry[i];
            numAry[i] = numAry[index];
            numAry[index] = temp;
        }
        
        for (int i = 0; i < numAry.length; i++){
            System.out.println(numAry[i]);
        }
    }
}

 

 

 

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int [] numAry = new int[N];

        for (int i = 0; i < N;i++ ) {
            numAry[i] = Integer.parseInt(br.readLine());
        }
        for(int i = 0; i < numAry.length - 1; i++){ //맨 끝은 계산할 필요 없으니
            for(int j = 0; j < numAry.length - 1 - i; j++){ //맨 끝은 numAry[j+1]로 계산한다 + 뒤에서 i 자리는 이미 정렬 
                if(numAry[j] > numAry[j+1]){
                    int temp = numAry[j];    //대각선 스왑 
                    numAry[j] = numAry[j+1]; //대각선 스왑
                    numAry[j+1] = temp;      //대각선 스왑
                }
            }
        }
        
        for (int i = 0; i < numAry.length; i++){
            System.out.println(numAry[i]);
        }
    }
}

 

 

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int [] numAry = new int[N];
        
        for(int i = 0; i < N; i++ ){
            numAry[i] = Integer.parseInt(br.readLine());
        }

        for(int i = 1; i < numAry.length; i++){
            int j = i;
            
            /*
                int j = i 는 그 앞들의 모든 값과 비교해서 작으면 맨 앞으로 보내야 하기 때문에 
                while     는 그 앞들의 모든 값과 비교해서 작으면 맨 앞으로 보내야 하기 때문에 
                j > 0     는 j-- 떄문에 필요함
                
            */
            while(j > 0 && numAry[j] < numAry[j-1]){ 
                int temp = numAry[j-1];  //대각선스왑
                numAry[j-1] = numAry[j]; //대각선스왑
                numAry[j] = temp;        //대각선스왑
                j--;
            }
        }

        for(int i : numAry){
            System.out.println(i);
        }
    }
}

 

 

 

- 실패 소스코드 -

 

 

 

 

 

 

 

---

4.추가 개념

 

 

1. 알고리즘 개요:

• 선택 정렬은 주어진 리스트를 순차적으로 정렬하는 비교 기반 정렬 알고리즘입니다.
• 리스트에서 최소값을 찾아 첫 번째 요소와 교환하고, 다음 최소값을 찾아 두 번째 요소와 교환하는 방식으로 진행됩니다.

2. 작동 방식:

• 첫 번째 루프: 리스트의 첫 번째 요소부터 마지막 요소까지 반복합니다.
• 두 번째 루프: 최소값을 찾기 위해 현재 위치에서 끝까지 탐색합니다.
• 교환: 최소값을 현재 위치에 있는 요소와 교환합니다.

3. 시간 복잡도:

• 평균 및 최악의 경우: O(n^2)
• 최선의 경우: O(n^2)
  • 예 ) 5,4,3,2,1 의 순차로 배열되어 있는경우
    • 5+4+3+2+1  첫 자리 5는 5번 , 두번째 자리는 4번, 3번째 자리는 3번, ... 이렇게 반복해서 살펴봐야 한다.
    • 등차수열의 공식으로 풀어서 보면 N * ( N + 1 ) / 2 이므로 5 * ( 5 + 1 ) / 2 = 15번 이다.
    • 근데 무한히 큰 수를 대입해보면 1000000*(1000000+1) / 2 에서 +1과 / 2는 큰 의미가 없다.
      이미 1000000 * 1000000이 시간을 다잡아먹는다. 
    • 그래서 결론은 O(N^2) 이다.
    • N이 많아질수록 속도가 2차 함수 형태로 증가한다.

4. 공간 복잡도:

• O(1) (제자리 정렬 알고리즘)

5. 특징:

• 간단하고 구현이 쉬움.
• 작은 데이터셋에 적합.
• 안정적이지 않음(같은 값의 원소가 순서를 유지하지 않음).

위키백과

 

---

 

 

1. 알고리즘 개요:

• 버블 정렬은 인접한 두 요소를 비교하여 정렬하는 비교 기반 정렬 알고리즘입니다.
• 배열을 반복적으로 순회하며, 인접한 두 요소를 비교하고 필요에 따라 교환하여 정렬을 완료합니다.

2. 작동 방식:

• 첫 번째 루프: 배열의 끝에서 끝까지 반복합니다.
• 두 번째 루프: 각 요소를 인접한 요소와 비교하여 필요하면 교환합니다.
• 가장 큰 요소가 배열의 끝으로 ‘버블’처럼 올라옵니다.

 

3. 시간 복잡도:

• 평균 및 최악의 경우: O(n^2)
• 최선의 경우: O(n) (이미 정렬된 경우)
• 선택정렬과 복잡도는 동일하지만 매번 버블정렬을 해주기 때문에 가장 효율이 안좋다.

 

4. 공간 복잡도:

• O(1) (제자리 정렬 알고리즘)

 

5. 특징:

• 간단하고 이해하기 쉬움.
• 작은 데이터셋에 적합.
• 안정적인 정렬(같은 값의 원소가 순서를 유지함).

 

---

 

1. 알고리즘 개요:

• 삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 요소를 하나씩 정렬된 부분에 삽입하여 정렬하는 알고리즘입니다.

2. 작동 방식:

• 두 번째 요소부터 시작하여, 현재 요소를 정렬된 부분과 비교하면서 올바른 위치에 삽입합니다.
• 정렬된 부분은 항상 오름차순을 유지합니다.

3. 시간 복잡도:

• 평균 및 최악의 경우: O(n^2)
• 최선의 경우: O(n) (이미 정렬된 경우)
• 선택,버블 정렬과 복잡도는 동일하지만 "거의 정렬된 상황에서는" 가장 효율이 좋다. 2,3,4,5,1 일때 ..

4. 공간 복잡도:

• O(1) (제자리 정렬 알고리즘)

5. 특징:

• 단순하고 구현이 쉬움.
• 작은 데이터셋에 적합.
• 안정적인 정렬(같은 값의 원소가 순서를 유지함).

 

---

5. 참조 블로그

---

 

불편함을 느끼실 경우 연락 주시면 곧 바로 삭제하도록 하겠습니다.

 

---