버블, 삽입, 선택 정렬

정렬

특정 값을 기준으로 데이터를 순서대로 배치하는 방법

구현 난이도는 쉽지만 속도는 느린 알고리즘
-> 버블 정렬, 삽입 정렬, 선택 정렬

구현 난이도는 어렵지만, 속도는 빠른 알고리즘
-> 합병 정렬, 힙 정렬, 퀵 정렬, 트리 정렬(bst)

하이브리드 정렬
-> 팀 정렬, 블록 병합 정렬, 인트로 정렬

기타 정렬 알고리즘
-> 기수 정렬, 카운팅 정렬, 셸 정렬, 보고 정렬

버블 정렬

인접한 데이터를 비교하며 자리 바꾸는 방식 : O(n^2)

step1때 1번째로 큰수가 뒤로 감

O(n^2) : (n-1) + (n-2) ..... + 2 + 1 = n(n-1) / 2

삽입 정렬

앞의 데이터를 정렬 해가면서 삽입 위치를 찾아 정렬하는 방식 : O(n^2)

Step1 : 1번 인덱스부터 시작해서 우선 본인 앞쪽과 비교
-> 더 작으면 앞쪽으로 삽입

Step2 : 7이 앞의 5보다 크기 떄문에 비교 종료

Step3 : 1의 경우 앞에 모든 요소들과 비교를 진행해야 함

앞에 데이터가 정렬되어 있음을 유의하자

worst case : 5 4 3 2 1
-> 평균적으로는 버블 정렬보다 빠름

선택 정렬

최소 또는 최대 값을 찾아서 가장 앞 또는 뒤부터 정렬하는 방식 : O(n^2)

버블,삽입,선택 정렬 구현

package org.example;

import java.util.Arrays;

public class Main {
    // 버블 정렬
    public static void bubbleSort(int[] arr){
			for(int i = 0; i < arr.length; i++){
            	for(int j = 0; j < arr.length-1-i; j++){
                  if(arr[j] > arr[j+1]){
                      swap(arr,j,j+1);
                  }
            	}
        	}

        // for(int i = arr.length - 1; i > 0; i--){
        //      for(int j = 0; j < i; j++)}{
    }

    // 삽입 정렬
    public static void insertionSort(int[] arr){
        for(int i = 1; i < arr.length; i++){
            for(int j = i; j > 0; j--){
                if(arr[j-1] > arr[j]){
                    swap(arr,j-1,j);
                }else{
                    break;
                }
            }
        }
    }

    // 선택 정렬
    public static void selectionSort(int[] arr){
        for(int i = 0 ; i < arr.length; i++){
            int minIndex = i;
            for(int j = i+1; j < arr.length; j++){
                if(arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            swap(arr,i,minIndex);
        }
    }

    public static void swap(int[] arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {3,5,2,7,1,4};
        bubbleSort(arr);
        System.out.println("버블 정렬 : " + Arrays.toString(arr));

        arr = new int[]{3,5,2,7,1,4};
        insertionSort(arr);
        System.out.println("삽입 정렬 : " + Arrays.toString(arr));

        arr = new int[]{3,5,2,7,1,4};
        selectionSort(arr);
        System.out.println("선택 정렬 :" + Arrays.toString(arr));

    }
}