[Java] 알고리즘 - 선택정렬 / 버블정렬 / 삽입정렬 구현

[Java] 알고리즘 - 선택정렬 / 버블정렬 / 삽입정렬

1. 선택정렬

선택 정렬(Selection Sort)은 정렬할 리스트 중에서 가장 작은 값을 찾아서 맨 앞에 위치한 값과 교환하고,

두 번째로 작은 값을 찾아서 두 번째 위치한 값과 교환하고,

그 다음 작은 값을 찾아서 그 다음 인덱스의 값으로 교환을 반복하는 방식으로 정렬을 수행하는 알고리즘입니다.

선택 정렬 알고리즘의 구현 방법은 다음과 같습니다.

구현코드(Java)

외부로부터 입력값 두 줄을 입력받으며
첫 줄에 배열의 길이,
둘째줄에 배열의 각 원소가 순차적으로 주어진다고 가정하겠습니다.

import java.util.*;
class Main{
    public static void main(String[] args){
        Main m = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr =new int[n];
        for(int i=0; i<n; i++) arr[i] = sc.nextInt();
        for(int x : m.solution(n, arr)) System.out.println(x+" ");

     }

     public int[] solution(int n, int[] arr){
        for(int i=0; i<n-1; i++){
          
           int index = i;
            for(int j=i+1; j<n; j++){
                if(arr[j]<arr[i]) index = j;
            }
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }

        return arr;
     }


}

리스트의 첫 번째 원소를 고정
리스트의 두 번째 원소부터 마지막 원소까지 돌면서, 최솟값을 찾음
최솟값과 첫 번째 원소의 값을 swap
리스트의 두 번째 원소를 고정

2), 3) 4) 반복

위와 같이 배열에서 가장 작은 값을 찾아 그 값을 배열의 첫 번째 위치와 교환하는 방식으로 진행되며, 그 다음 작은 값을 찾아 두 번째 위치와 교환합니다. 이 과정을 배열의 끝까지 반복하면 배열이 정렬됩니다.

2. 버블정렬

버블 정렬은 맨 왼쪽부터 인접한 두 원소를 비교하여 큰 값을 오른쪽으로 이동시키는 과정을 반복합니다. 이 과정을 여러 번 반복하면 배열의 오른쪽부터 정렬되어 가장 작은 값이 왼쪽으로 이동합니다.

인접한 두 값씩 비교하여 한 턴을 돌 때마다

그 중 max값이 가장 오른쪽에 위치하게 됩니다.

즉, 배열의 길이가 n일 때

처음에는 배열의 길이 -1 만큼 for문을 돌며 인접한 두 값을 비교하게 되고그 결과 가장 오른쪽에 최댓값이 위치합니다.

그 다음턴에서는, 이미 최댓값이 가장 오른쪽으로 이동하였으므로 두 번째로 큰 값을 찾기 위한 for문을 도는데그 때는 전체 배열의 길이 -2만큼 for문을 돌며 마찬가지로 인접한 두 값을 비교,그 결과 전체 배열 중 두 번쨰 큰 값이 오른쪽 두 번째에 위치하게 됩니다.

그렇기 때문에 이중 for문을 돌되

가장 바깥쪽 for문은 0~ n-1까지,

안쪽 for문은 바깥쪽 for문이 한 번 돌 때마다 그 중 최댓값이 정해져

비교해야할 배열의 길이가 1씩 감소하므로

0~n-i-1까지 돌아야합니다.

이중 for문을 돌면서

arr[j]와 arr[j+1]의 값을 비교하고,

더 큰 값을 tmp에 저장합니다.

안 쪽 for문 한 겹이 끝나면 tmp에는 탐색을 완료한 리스트 중 가장 큰 값이 담기게 되며,

그 값을 arr[j+1] 담습니다.

구현코드(Java)

외부로부터 입력값 두 줄을 입력받으며
첫 줄에 배열의 길이,
둘째줄에 배열의 각 원소가 순차적으로 주어진다고 가정하겠습니다.

import java.util.*;
class Main{
    public static void main(String[] args){
        Main m = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr =new int[n];
        for(int i=0; i<n; i++) arr[i] = sc.nextInt();
        for(int x : m.solution(n, arr)) System.out.println(x+" ");

     }

     public int[] solution(int n, int[] arr){
        for(int i=0; i<n-1; i++){
            for(int j=0; j<n-i-1; j++){
                if(arr[j] > arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1]  = tmp;
                }
            }
        }
        return arr;
     }


}

3. 삽입정렬

삽입 정렬은 배열의 두 번째 원소부터 값을 고정하여

해당 원소의 왼쪽 요소들과 비교하며, 그 중 자기 자신의 자리를 찾아 옮기는 방식으로 정렬을 진행합니다.

즉, 선택한 원소를 왼쪽의 정렬된 부분 배열과 비교하여 알맞은 위치에 삽입합니다.

이 과정을 배열의 끝까지 반복하면 배열이 정렬됩니다.

구현코드(Java)

solution함수에서 인자값으로 배열의 길이 n , 그리고 배열 arr을 받았다고 가정하겠습니다.

import java.util.*;
class Main{
    public static void main(String[] args){
        Main m = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr =new int[n];
        for(int i=0; i<n; i++) arr[i] = sc.nextInt();
        for(int x : m.solution(n, arr)) System.out.println(x+" ");

     }

     public int[] solution(int n, int[] arr){
        for(int i=1; i<n; i++){
            int tmp = arr[i];
            int j;
            for(j=i-1; j>=0; j--){
                if(arr[j]>temp) arr[j+1] = arr[j];
                else break;
            } 
            arr[j+1] = tmp;
        }
        return arr;
     }
}

구현을 위해서

두 번째 인덱스부터 마지막 인덱스까지 도는 외부 for문,

그리고 외부포문의 마지막 값 -1 부터 0까지 도는 내부 for문이 필요합니다.

먼저, 두 번째 인덱스를 고정하고두 번째 인덱스와 해당 인덱스의 왼쪽 인덱스를 비교, 만약 왼쪽 인덱스 값이 더 크다면, 그 값을 오른쪽으로 한 칸 옮깁니다.그리고 자기 자신을 그 자리에 넣습니다.

두 번째 턴에는 세 번째 인덱스를 고정하고

세 번째 인덱스와 왼쪽에 위치한 인덱스들을 가까운 순으로 순서로 비교,

만약 왼쪽 인덱스 값이 더 크다면, 그 값을 오른쪽으로 한 칸 옮기는 것을 반복합니다.

만약 왼쪽인덱스 값이 더 작다면, 자기 자신을 그 인덱스의 오른쪽에 넣습니다.

위와 같이 반복을 하다 보면,

턴을 한 번 돌 때마다 비교한 값들 중 최솟값이 가장 왼쪽에 위치하게 됩니다.

시간복잡도

이 세 가지 알고리즘은 기본적인 정렬 알고리즘이지만, 시간 복잡도는 O(n^2)입니다.

따라서 큰 데이터셋에서는 효율성이 떨어지므로 더 효율적인 정렬 알고리즘(예: 퀵정렬, 병합정렬)을 사용하는 것이 좋습니다.

저작자표시 비영리 동일조건

'Algorithm (Java) > 알고리즘 개념' 카테고리의 다른 글

[자바 /Java] 피보나치 구현 - 재귀 / 반복문 (0)	2023.04.07

🌱코딩새싹 코린이의 코딩일기🖥️

[Java] 알고리즘 - 선택정렬 / 버블정렬 / 삽입정렬 구현