[Computer Science] 정렬(선택, 버블, 삽입)

정렬이란?

• 물건을 크기 순으로 나열하는 것 (오름, 내림차순)
• 많은 정렬 알고리즘들이 존재
  • 단순하지만 긴 수행시간 : 삽입정렬, 선택정렬, 버블정렬
  • 복잡하지만 짧은 수행시간 : 퀵정렬, 히프정렬, 합병정렬, 기수정렬
• 모든 경우에 최적인 알고리즘은 없음 → 환경에 맞추어 선택!
• 정렬 알고리즘의 평가
  • 비교 횟수
  • 이동 횟수
  • 안정성

---

선택정렬 (selection sort)

• 정렬이 안된 곳에 최소값 선택 → 정렬된 끝 위치와 교환

• 시간복잡도 : O(n^2)
  
  • 최소값 선택 : O(n)
  • 최종 : 최소값 선택 * n번 반복 = O(n^2)

// 선택 정렬
void selection_sort(int list[], int n){
  int i, j, least, temp;

  // 마지막 숫자는 자동으로 정렬되기 때문에 (숫자 개수-1) 만큼 반복한다.
  for(i=0; i<n-1; i++){
    least = i;

    // 최솟값을 탐색한다.
    for(j=i+1; j<n; j++){
      if(list[j]<list[least])
        least = j;
    }

    // 최솟값이 자기 자신이면 자료 이동을 하지 않는다.
    if(i != least){
        SWAP(list[i], list[least], temp);
    }
  }
}

---

버블 정렬 (bubble sort)

• 서로 인접한 두 원소를 검사하고, 조건에 맞지 않으면 서로 교환

• k회전 마다, 배열의 끝 k개의 요소는 정렬이 완료

// 버블 정렬
void bubble_sort(int list[], int n){
  int i, j, temp;

  for(i=n-1; i>0; i--){
    // 0 ~ (i-1)까지 반복
    for(j=0; j<i; j++){
      // j번째와 j+1번째의 요소가 크기 순이 아니면 교환
      if(list[j]<list[j+1]){
				swap(list[j], list[j+1], temp);
      }
    }
  }
}

---

삽입 정렬 (insertion sort)

• 정렬되어 있는 부분에 새로운 값을 적절한 위치에 삽입

• 거의 정렬되어 있는 배열에 효율적
• 안정된 정렬방법

// 삽입 정렬
void insertion_sort(int list[], int n){
  int i, j, key;

  // 인텍스 0은 이미 정렬된 것으로 볼 수 있다.
  for(i=1; i<n; i++){
    key = list[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사

    // 현재 정렬된 배열은 i-1까지이므로 i-1번째부터 역순으로 조사한다.
    // j 값은 음수가 아니어야 되고
    // key 값보다 정렬된 배열에 있는 값이 크면 j번째를 j+1번째로 이동
    for(j=i-1; j>=0 && list[j]>key; j--){
      list[j+1] = list[j]; // 레코드의 오른쪽으로 이동
    }

    list[j+1] = key;
  }
}

---

간단한 정렬의 비교

• 3가지 모두 구현과 이해가 쉬운 정렬 (선택, 버블, 삽입)
• 시간복잡도 ← 복잡한 정렬에 비해서는 오래 걸림
  • 모든 경우에 O(n^2)  : 선택, 버블
  • 평균적으로는 O(n^2), 거의 정렬된 상태에서는 O(n) : 삽입
  시간 복잡도로는 선택과 버블이 동일하지만, 일반적으로 자료 교환(swap) 과정이 더 복잡하기에 버블이 더 오랜 시간 소요됨
• 정렬의 안정성
  • 안정 정렬 - 동일한 값에 대해 기존 순서가 유지 (버블, 삽입)
  • 불안정 정렬 - 동일한 값에 대해 기존 순서가 유지되지 않는 정렬 (선택)
• ex) {2, 3, 2, 1} 을 정렬한다고 생각해보자.
• 처음에 있는 2와 세번째 있는 2의 순서적 위치가 정렬 후에 바뀌는가?
• {1, 2, 2, 3} : 버블, 삽입
• {1, 2, 2, 3} : 선택
• 차후에 복잡한 정렬 알고리즘에 대해서도 합병 정렬과 기수 정렬에 대해서만 안정성이 보장
•  
• [예시] 백준 | 버블 소트 1377번 https://www.acmicpc.net/problem/1377
• 문제 내용 요약 ⇒ 버블소트를 한 후, 기존 인덱스 출력 

  • bool change = false;
    for (int i=1; i<=n+1; i++) {
        change = false;
        for (int j=1; j<=n-i; j++) {
            if (a[j] > a[j+1]) {
                change = true;
                swap(a[j], a[j+1]);
            }
        }
        if (change == false) {
            cout << i << '\\n';
            break;
        }
    }
    

  • 진짜 버블 소트로 짜면... → 시간 초과
  • Collection의 Sort 메소드를 활용하면... → 틀렸습니다
  • How...?
• 문제 내용 요약 ⇒ 버블소트를 한 후, 기존 인덱스 출력
• 차후에 복잡한 정렬 알고리즘에 대해서도 합병 정렬과 기수 정렬에 대해서만 안정성이 보장
• {1, 2, 2, 3} : 버블, 삽입

[예시] 백준 | 버블 소트 1377번 https://www.acmicpc.net/problem/1377

문제 내용 요약 ⇒ 버블소트를 한 후, 기존 인덱스 출력[예시] 백준 | 버블 소트 1377번 https://www.acmicpc.net/problem/1377 

[예시] 백준 | 버블 소트 1377번 https://www.acmicpc.net/problem/1377

문제 내용 요약 ⇒ 버블소트를 한 후, 기존 인덱스 출력

{1, 2, 2, 3} : 버블, 삽입

{1, 2, 2, 3} : 선택

{1, 2, 2, 3} : 버블, 삽입

{1, 2, 2, 3} : 선택

{1, 2, 2, 3} : 버블, 삽입

{1, 2, 2, 3} : 선택

---

정렬 알고리즘의 비교

(성능 비교 데이터 출처 : http://wonjayk.tistory.com/225)