[Algorithm]Sort, 정렬(1)

정렬은 말 그대로 순서대로 정리하는 것을 의미한다. 뒤죽박죽인 숫자를 오름차순, 내림차순으로 정렬할 수 있다. 뭐 그런 것들.. 데이터들을 정리할때 필요하다.

 

정렬 알고리즘은 여러가지가 있지만 내가 배운 몇 개만 다뤄볼 것이다.

1. Insertion sort

2. Bubble sort

3. Selection sort

4. Quick sort

5. Merge sort

6. Heap sort

7. Radix sort -> 특정한 경우에 사용

---

오름차순 정렬로 예시를 들었다.

 

1. Insertion sort(삽입 정렬)

앞 원소가 정렬되었다고 가정하고 정렬되지 않은 뒤의 원소를 정렬된 원소들 사이에 삽입한다. 이때 크기를 비교하고 적절한 위치에 넣는다.

그림으로 예시를 들자.

노란색은 정렬 된 부분, 흰 색은 정렬되지 않은 부분이다. 23은 이미 정렬이 되었고 나머지 흰색 4개의 숫자를 정렬해야 한다.

 

① arr[1] 11

11은 23보다 작으므로 23 앞에 가야한다. 코드상 순서로는 ..  0) 알맞은 자리를 찾는다. 1) tmp에 arr[1]을 넣는다. 2) 자리를 이동한다. 3) 알맞은 자리에 tmp를 넣는다.

*파랑은 정렬 할 값

 

0) 알맞은 자리는 arr[0]이다.

1) 11을 copy 해서 tmp에 넣는다.

2) 알맞게 자리를 이동한다.

3) 알맞은 자리(arr[0])에 tmp를 넣는다.

4) 정렬 완료!

이런식으로 작업을 반복한다.

 

② arr[2] 37

이미 정렬되어있으므로 continue; (코드상으로는 arr[0], arr[1]과 다 비교한다.)

countinue 하기

정렬 완료!

 

③ arr[3] 8

0) 알맞은 자리를 찾는다. 1) tmp에 arr[3]을 저장한다. 2) 알맞게 자리를 이동한다. 3) 알맞은 자리에 tmp를 넣는다.

 

0) 알맞은 자리는 arr[0]이다.

1) tmp에 arr[3]을 저장한다.

2) 알맞게 자리를 이동한다.

3) 알맞은 자리에 tmp를 넣는다.

 

4) 정렬 완료!

 

 

 

④ arr[4] 21

0) 알맞은 자리를 찾는다. 1) tmp에 arr[4]를 저장한다. 2) 알맞게 자리를 이동한다. 3) 알맞은 자리에 tmp를 넣는다.

 

0) 알맞은 자리는 arr[2]이다.

1) tmp에 arr[4]를 저장한다.

 

2) 알맞게 자리를 이동한다.

3) 알맞은 자리에 tmp를 넣는다.

4) 정렬 완료!

 

 

public static void insertion_sort(int[] arr, int size){
    int i, j, k, tmp;
    // i는 이번 순서를 뜻함, arr[i]는 이번에 정렬할 값
    // k는 arr[i]의 알맞은 자리

    for(i=1;i<size;i++){
        for(j=0;j<i;j++){ // 정렬되지 않은 값(arr[i]) 넣을 자리 찾기
            if(arr[j] > arr[i]) // 정렬된 배열 안에서 arr[i]의 알맞은 자리를 찾은 경우
                break;
        }
        if(j == i) // 예외처리, arr[i]의 현재 자리가 알맞은 자리인 경우 == arr[i]가 arr[i-1]보다 큰 수
            continue; // 정렬되어있으므로 다음 값 확인

        // arr[i]를 정렬된 배열 사이에 삽입
        tmp = arr[i]; // arr[i] tmp에 저장

        for(k=i;k>j;k--){ // arr[i-1]부터 한 칸씩 뒤로 미루기
            arr[k] = arr[k - 1];
        }
        
        arr[k] = tmp; // arr[i]를 알맞은 자리에 넣기
    }
    return ;
}

 

시간복잡도는 O(n^2)이다.

n까지 도는 루프가 2중으로 있기 때문..

---

2. Bubble sort

---

3. Selection sort