[이코테] CHAPTER 06 정렬- 선택정렬,삽입정렬- 파이썬(Python), 자바(Java)

정렬 : 데이터를 특정한 기준에 다라서 순서대로 나열 하는 것

1) 선택정렬(selection sort)

: 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정 반복

데이터가 무작위로 여러 개 있을 때, 이중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복

ex ) 

 파이썬(Python)

#파이썬- 선택 정렬
array = [7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)):
    min_index=i #가장 작은 원소의 인덱스
    for j in range(i+1,len(array)):
        if array[min_index]>array[j]:
            min_index=j
    array[i],array[min_index]=array[min_index],array[i]# 스와이프해서 집어넣기
print(array)

결과화면

자바(Java)

//Java - 선택 정렬

public class e01_6_1 {
    public static void main(String[] args) {
        int[] array= {7,5,9,0,3,1,6,2,4,8};

        for(int i=0;i<array.length;i++){
            //가장 작은 원소의 인덱스
            int min_index=i;
            for(int j=i+1;j< array.length-1;j++){
                if(array[j]<array[min_index]){
                    min_index=j;
                }
            }
            int min_num=array[min_index];
            array[min_index]=array[i];
            array[i]=min_num;
        }
        for(int i:array){
            System.out.print(i+" ");
        }
    }
}

결과화면

 

 

선택 정렬의 시간 복잡도 : 

처음 숫자의 경우 N-1 번만큼 비교 연산 필요하고, 그 담에는 N-2번, N-3번....

따라서 시간 복잡도는 (N-1) + (N-2) + (N-3) + .... + 1 = N x (N-1) /2 = O(N^2) -> 빅오 표기법 

 

---

백준 문제 - 2750번

백준 -2750 (수 정렬하기)

2) 삽입 정렬 (Insertion Sort)

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

삽입 정렬 구현 난이도 > 선택 정렬 구현 난이도 , but 삽입 정렬 시간 효율 > 선택 정렬 시간 효율 (* 특히 정렬이 완료된 경우 훨씬 효율적) 

왜냐하면 삽입 정렬의 경우 현재 데이터의 상태와 상관없이 무조건 모든 원소와 비교하는 것에 반해 삽입 정렬은 적절한 위치에 삽입 하기 때문이다.

특정한 데이터의 왼쪽에 있는 데이터들은 이미 정렬된상태이므로 자기보다 작은 데이터를 만났다면 더 이상 데이터를 살펴볼 필요 없이 그 자리에 삽입된다. 

 

파이썬(Python)

#파이썬- 삽입 정렬
array=[7,5,9,0,3,1,6,2,4,8]

for i in range(1,len(array)):#첫번째 인덱스는 이미 정렬되었다고 가정하므로
    for j in range(i,0,-1):#인덱스 i부터 1까지 1씩 감소하며 반복
        if array[j]<array[j-1]:#한칸씩 왼쪽으로 이동
            array[j],array[j-1]=array[j-1],array[j]#swap
        else: #자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break
print(array)

결과화면

자바(Java)

package s11_greedy;

public class e01_6_3 {
    public static void main(String[] args) {
        int[] array= {7,5,9,0,3,1,6,2,4,8};;
        for(int i=1;i<array.length;i++){
            for(int j=i;j>0;j--){
                if(array[j]<array[j-1]){
                    int num=array[j];
                    array[j]=array[j-1];
                    array[j-1]=num;
                }else break;
            }
        }
        for(int i:array){
            System.out.print(i+" ");
        }
    }
}

결과화면

 

삽입 정렬의 시간 복잡도 :

삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. 최선의 경우 O(N)의 시간 복잡도를 가진다. 보통은 삽입정렬이 비효율적이나 정렬이 거의 되어 있는 상황에서는 퀵 정렬 알고리즘보다 더 강력