[JAVA][알고리즘] 정렬 알고리즘 ( 선택 삽입 버블 )

💡 선택정렬 ( Selection Sort )

가장 원시적인 방법의 정렬 알고리즘

데이터가 무작위로 여러개 있을 때, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해

앞에서 두번째 데이터와 바꾸는 과정을 반복한다.

시간 복잡도 : O(N²)

장점

• 추가적인 메모리 소비가 작다.

단점

• 안정 정렬이 아니다.
• 시간복잡도가 O(N^2) 이다.

 

public void sort(int[] arr) {
        for(int i=0; i<arr.length-1; i++){
            int min_index = i;
            for(int j=i+1; j<arr.length; j++){
                if(arr[j]<arr[min_index])
                    min_index = j;
            }
            int temp = arr[i];       
            arr[i] = arr[min_index]; 
            arr[min_index] = temp; 
        }
}

 

 

💡 삽입정렬 ( Insertion Sort )

데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입한다.

 

선택정렬에 비해 실행 시간 측면에서 더 효율적이며, 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을때 더욱 효과적이다.

 

삽입정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.

정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다.

 

시간복잡도 : O(N^²)

장점

• 추가적인 메모리 소비가 작다.
• 거의 정렬된 경우 매우 효율적이다. 즉 최선의 경우 O(N)의 시간복잡도를 가진다.
• 안정정렬이 가능하다.

단점

• 역순에 가까울수록 매우 비효율적이다. 즉 최악의 경우 O(N^2)의 시간복잡도를 가진다.
• 데이터의 상태에 따라서 성능 편차가 매우 크다.

 

public void sort(int[] arr) {
        for(int i=1; i<arr.length;i++){
            int temp=arr[i];
            int j;
            for(j=i-1; j>=0;j--){ // 한 칸씩 왼쪽으로 이동
                if(temp < arr[j])
                    arr[j+1] = arr[j];
                else break; // 자기보다 작은 값을 만나면 그 위치에서 멈춤
            }
            arr[j+1] = temp;    
        }
}

 

 

💡 버블정렬 ( Bubble Sort )

두 개의 인접한 원소를 비교하여 정렬하는 방식

시간복잡도 : O(N2)

장점 

• 추가적인 메모리 소비가 작다.
• 구현이 매우 쉽다.
• 안정정렬이 가능하다.

단점

• 다른 정렬 알고리즘에 비해 교환 과정이 많아 많은 시간을 소비한다.

public void sort(int[] arr) {
        for(int i=0; i<arr.length-1; i++){
            for(int j=0; j<arr.length-i-1; j++){
                if(arr[j]>arr[j+1]){
                    int tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                }
            }
        }
 }