Sorting and Searching -(1)

📍 섹션6. Sorting and Searching

(정렬, 이분 검색과 결정 알고리즘)

Sorting and Searching -(1)

⬛ 선택 정렬 | Selection Sorting

• 대상에서 가장 큰 or 작은 데이터 찾아 선택을 반복하며 정렬하는 방식
• 전체 원소들 중, 기준 위치(i)에 맞는 원소를, 남은 원소들 중에서 (j) 찾아 선택 후, 자리 맞교환
• 시간 복잡도 O(n2) 비효율적이라 사용 小
• i번째 단계에서 i번째 자리 확정
• n개 원소에 대해 n-1번 반복함

---

6-1. 선택 정렬

import java.util.ArrayList;
import java.util.Scanner;

/* 6-1. 선택 정렬
 * N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
 * 정렬하는 방법은 선택정렬입니다.
 * */
public class Main1 {
    //솔루션 함수
    public int[]solution(int n, int[] arr){

         //정렬 모두 마치면 마지막 값은 어차피 가장 큰 수만 남음
        for(int i = 0; i<n-1; i++) {
            //기준 i 인덱스값
            int idx = i;
            //j가 i+1 ~ n 까지 돌며 가장 작은 작은 값의 idx값을 세팅함
            for(int j = i+1; j<n; j++) {
                if(arr[j] < arr[idx]) idx = j;
            }
            //for 탈출하면 idx에는 i기준 뒤쪽을 j가 돌며 가장 작은 값의 idx를 세팅한 상태
            //따라서 기준 i의 값 <-> idx로 찍은 최소값 swap
            int tmp = arr[i];
            arr[i] = arr[idx];
            arr[idx] = tmp;
        }
        return arr;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main1 T = new Main1();

        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i<n; i++) {
            arr[i] = kb.nextInt();
        }
        //출력
        for(int x : T.solution(n, arr)) {
            System.out.print(x + " ");
        }
    }
}

---

⬛ 버블 정렬 | Bubble Sorting

• 데이터의 인접 요소끼리 비교하고, swap 연산 수행하며 정렬하는 방식
• 단계별로 첫 원소 ~ 마지막 원소까지 인접한 두 개 원소끼리 비교 후 자리 교환
• 시간 복잡도 O(n2) 비효율적
• 각 단계 끝날 때마다 뒤에서 i번째 요소 자리 확정 가능
• n개 원소에 대하여 n-1번 반복 행

---

6-2. 버블 정렬

import java.util.Scanner;

/* 6-2. 버블 정렬 
N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
정렬하는 방법은 버블정렬입니다.*/
public class Main2 {
    //솔루션 함수 
    public int[] solution(int n, int[] arr) {
        for(int i = 0; i<n-1; i++) {
            // 각 단계 끝날 때마다 뒤에서 i번째 요소 자리가 확정되어야 함 
            for(int j = 0; j<n-i-1; j++) {
                //인접 두 수 비교후 뒷 요소가 더 작으면 swap
                if(arr[j] > arr[j+1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
        return arr;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main2 T = new Main2();

        Scanner kb = new Scanner(System.in);
        int n =kb.nextInt();
        int[] arr = new int[n];

        for(int i = 0; i<n; i++) {
            arr[i] = kb.nextInt();
        }
        //츨력
        for(int x : T.solution(n, arr)) System.out.print(x + " ");
    }
}

⬛ 삽입 정렬 | Injection Sorting

• 선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 방식
• 정렬된 S집합 마지막 원소부터 ~ 정렬안된 U집합 첫 원소 비교하며, S집합 속에 삽입할 위치 찾아서 삽입하는 방식
• 평균 시간 복잡도 O(n2) 느린 편
• [정렬 전] 첫 원소는 이미 정렬된 상태로 가정하고 i=1 부터 돈다.

---

6-3. 삽입 정렬

import java.util.Scanner;

/* 6-3. 삽입 정렬 
 * */
public class Main3 {
    //솔루션 함수 
    public int[] solution(int n, int[] arr) {

        for(int i = 1; i<n; i++) {
            int tmp = arr[i], j;
            for(j = i-1; j>=0; j--) {
                //tmp를 삽입할 위치 찾은 경우.
                if(arr[j] > tmp) {
                    //뒤로 밀려야 됨
                    arr[j+1] = arr[j];
                }
                else break;
            }
            //j가 멈춘 지점이 됨
            arr[j+1] = tmp;
        }

        return arr;
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main3 T = new Main3();
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i<n; i++) arr[i] = kb.nextInt();

        //출력
        for(int x : T.solution(n, arr)) System.out.print(x + " ");
    }
}