정렬 (버블정렬, 삽입정렬, 퀵정렬, 병합정렬)

버블정렬

• 인접한 두 원소를 순서대로 보면서 정렬해 나가는 알고리즘
• 오름차순 예시
  • A[i]와 A[i+1]을 비교할 때
  • A[i] > A[i+1] 이면 A[i]와 A[i+1]를 교환(swap)한다.

 

• 위 과정을 i=1~N-1까지 순서대로 한번 수행 하는 것을 순회라고 한다. (N은 배열의 길이)
• 버블 정렬은 순회를 N-1번 반복한다.
• ex) [4, 5, 2, 3, 1]
  • i=1)  [4, 5, 2, 3, 1]
  • i=2)  [4, 2, 5, 3, 1]
  • i=3)  [4, 2, 3, 5, 1]
  • i=4)  [4, 2, 3, 1, 5]
  • 첫 번째 과정을 수행하면 가장 큰 수 5가 맨 뒤에 위치
  • i=1)  [2, 4, 3, 1, 5]
  • i=2)  [2, 3, 4, 1, 5]
  • i=3)  [2, 3, 1, 4, 5]
  • 두 번째 과정을 수행하면 두번째로 큰 수 4가 맨 뒤에서 두번째에 위치
  • i=1)  [2, 3, 1, 4, 5]
  • i=2)  [2, 1, 3, 4, 5]
  • 세 번째 과정을 수행하면 세번째로 큰 수 3이 맨 뒤에서 세번째에 위치
  • i=1)  [1, 2, 3, 4, 5]
  • 정렬 끝.

 

• 시간 복잡도
  • 길이가 N인 배열을 한 번 순회할 때
  • 비교 N-1번(최대)
  • 교환 N-1번(최대)
  • i번째 순회에서 i번째로 큰 값이 뒤에서 i번째 위치로 이동
  • 순회를 N-1번 반복하면 모든 수가 올바른 위치로 이동
  • 즉, (N-1)^2번 연산을 수행하므로 O(N^2)

---

삽입정렬

• 적절한 위치에 원소를 삽입함으로써 정렬해 나가는 알고리즘
• i=2~N인 i에 대해서 순서대로 다음 과정을 수행
• i번째 작업: A[i]를 부분 배열 [1,i]가 정렬된 상태가 되도록 적절한 위치에 삽입
• ex) [4, 5, 2, 3, 1]
  • i=2)  [4, 5, 2, 3, 1]
  • i=3)  [2, 4, 5, 3, 1]
  • i=4)  [2, 3, 4, 5, 1]
  • i=5)  [1, 2, 3, 4, 5]
  • i번째 과정을 수행하면 부분배열 [1,i]가 정렬된 상태

 

• 시간 복잡도
  • best: O(N)
  • worst: O(N^2)
  • average: O(N^2)

---

퀵정렬

• 배열이 주어지면 다음 작업을 수행하는 함수 sort를 정의
• sort(int A[])
  • 배열 A의 길이가 0또는 1이면, 이미 정렬된 배열이므로 함수 종료
  • 배열A에 있는 아무 원소를 pivot으로 잡은 후, pivot보다 작은 원소를 pivot의 왼쪽으로 옮기고 pivot보다 큰 원소를 pivot의 오른쪽으로 옮긴다.
  • pivot을 기준으로 왼쪽에 있는 배열에 대해 다시 sort 호출.(왼쪽 배열을 다시 정렬) 
  • pivot을 기준으로 오른쪽에 있는 배열에 대해 다시 sort 호출.(오른쪽 배열 다시 정렬)

 

• ex) [4, 5, 2, 3, 1]
  • [4, 5, 2, 3, 1]        //4를 pivot으로 설정
  • [2, 3, 1, 4, 5]
  • [2, 3, 1]               //왼쪽배열 다시 정렬, 2를 pivot으로 설정
  • [1, 2, 3]
  • [1, 2, 3, 4, 5]
  • 정렬 끝.

 

• 시간 복잡도
  • best / average: O(NlogN)  //매번 고르는 pivot이 왼쪽과 오른쪽 배열을 정확히 절반씩 나누는 경우
  • worst: O(N^2)  //매번 고르는 pivot이 불균형하게 나누는 경우

---

병합 정렬

• 배열이 주어지면 다음 작업을 수행하는 함수 sort를 정의
• sort(int A[])
  • 배열 A의 길이가 0또는 1이면, 이미 정렬된 배열이므로 함수 종료
  • 배열 A를 다음 두 배열로 나눔
    • 왼쪽 절반을 L, 오른쪽 절반을 R이라고 하면,
    • sort(L)을 호출 (왼쪽 배열을 정렬)
    • sort(R)을 호출 (오른쪽 배열을 정렬)
  • 정렬된 두 배열 L과 R을 합쳐서 정렬된 배열 A를 반환

 

• ex) [4, 5, 2, 3, 1]
  • 배열을 나누는 과정
    • [4, 5, 2, 3, 1]
    • [4, 5, 2] [3, 1]
    • [4, 5] [2] [3] [1]
    • [4] [5]
  • 배열을 합치는 과정
    • [4, 5]
    • [2, 4, 5] [1, 3]
    • [1, 2, 3, 4, 5]
    • 각 배열의 앞 숫자 비교해서 합치기

 

• 시간 복잡도
  • best / average / worst : O(NlogN)    //퀵 정렬의 best 경우와 동일