알고리즘(4) - 정렬 (기본적인 정렬)

정렬 알고리즘

---

정렬이란, n의 개의 원소를 기준에 따라 순서대로 배열하는 것을 의미한다.

정렬 알고리즘의 수행시간은 대부분 O(nlogn)~O(n²)을 지닌다.

다만, 정렬하고자 하는 값이 특수한 성질을 만족하면 O(n) 수행시간도 가능하다.

 

정렬 알고리즘 분류

• 기본적인 정렬 -평균 θ(n²)
  • 선택 정렬 selection sort
  • 버블 정렬 bubble sort
  • 삽입 정렬 insert sort
• 고급 정렬 - 평균θ(nlogn)
  • 병합정렬 merge sort
  • 퀵 정렬 quick sort
  • 힙 정렬 heap sort
• 특수 정렬 - 평균 θ(n)
  • 계수 정렬
  • 기수 정렬

 

 

기본적인 정렬 알고리즘

---

단어 그대로 기본적이며 간단히 구현 가능한 알고리즘이다. 계수가 작을 때는 타 알고리즘에 비해 더 빠른 결과를 얻을 수도 있다.

선택 정렬 selection sort

1. 입력 원소들 중에서 최대원소를 선택한다. (n-1번의 비교가 필요)
2. 최대 원소를 제외한 나머지 원소들 중에서 최대 원소를 선택하고 자리를 바꾼다.
3. 이 작업을 반복한다.

선택 정렬

선택 정렬 단순 코드 구현

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

 

2번의 비교 횟수가 전체 수행시간을 좌우한다. 이를 기반으로 봤을 때 수행시간은 Θ(n²)이다.

 

 

 

버블 정렬 bubble sort

1. 서로 인접한 원소끼리 비교하여 순서에 맞지 않으면 자리를 바꾼다. (최대 원소를 뒤로 보낼 수 있음)
2. 자리가 정해진 최대 원소를 제외한 나머지 원소들을 같은 방법으로 처리한다.

버블 정렬의 예

버블 정렬 단순 코드 구현

버블 정렬도 선택 정렬과 마찬가지로  Θ(n²) 시간을 가진다.

다만 변형된 버블 정렬의 수행시간은 조금 다르다.

버블 정렬 변형의 예

이 변형 알고리즘에서 배열이 이미 정렬된 최선의 경우 best-case 수행시간은  Θ(n)이다.

2번에서 원소교환이 전혀 일어나지 않으면 3번에서 알고리즘이 종료되기 때문이다.

그렇다고 해도, 변형된 버블 정렬의 수행시간은 여전히 O(n²)이다. 쎄타가 아닌 이유는 변형된 알고리즘에서 정렬을 하지 않는 경우에 따라 수행시간 n²이 더 빠를 수 있기 때문이다.

 

 

삽입 정렬 insertion sort

1. 이미 정렬돼 있는 배열이 있다고 보고 다른 원소를 그 배열에 삽입한다.
2. 이러한 작업을 반복한다.

삽입 정렬의 예

수행시간은 O(n²)이다. 이미 정렬된 최선의 경우엔 각 단계에서 1번의 비교만 일어나고 자리이동은 일어나지 않기 때문에 Θ(n)이다. 물론 평균과 최악은 모두 Θ(n²)이다.