[알고리즘]정렬(Sort)

정렬 (Sort)

입력으로 주어진 숫자를 작은 순으로 나열하는 것을 말한다.

1. 버블 정렬 (Bubble Sort)

오른쪽에서 시작하여 왼쪽으로 인접한 두 숫자를 비교하여 교체하는 작업을 반복하는 정렬

버블 정렬은 1라운드에서 n-1회, 2라운드에서 n-2회, n-1라운드에서 1회 비교한다. 따라서 비교 횟수는 n^2/2 로 비교 횟수는 입력 데이터의 순서와 관계없이 일정하다.

숫자의 교체 횟수는 입력 데이터에 따라 달라진다. 극단적으로 생각하면 입력 데이터가 우연히 작은 순서대로 배치되었다면 한 번도 교체하지 않을 수도 있고 반대로 숫자가 큰 순서대로 나열 된 경우 비교할 때마다 교체해야 한다. 따라서 버블 정렬의 계산 시간은 O(n^2) 이다.

2. 선택 정렬 (Selection Sort)

수열에서 최소값을 찾아서 가장 왼쪽의 숫자와 교체하는 작업을 반복하여 정렬

1. 수열을 선형 탐색하여 최솟값을 찾는다 → 가장 왼쪽 수와 교체한다.
2. (n-1)개의 수열을 탐색하여 최솟값을 찾는다 → 가장 왼쪽 수와 교체한다.

선택 정렬은 선형 탐색을 위해 1라운드에서 n-1회, 2라운드에서 n-2회, n-1라운드에서 1회 비교한다. 따라서 비교 횟수는 버블 정렬과 동일하게 n^2/2 를 갖게 된다.

또한 숫자 교체는 각 라운드에서 최대 1회(혹은 0회)로 계산 시간 역시 버블 정렬의 계산과 동일한 O(n^2)이다.

3. 삽입 정렬 (Insertion Sort)

수열의 왼쪽부터 순서대로 정렬한다. 알고리즘의 정렬에 따라 왼쪽의 수는 점차 정렬되고 오른쪽의 미탐색 영역에서 숫자를 하나씩 꺼내어 정렬이 끝난 영역의 적절한 위치에 삽입해 나가며 정렬은 완성한다.

삽입 정렬은 각 라운드의 미탐색 영역의 첫 번째 숫자를 그 왼쪽의 숫자와 비교한다.
만약 왼쪽의 수가 더 작다면 더 이상 비교하지 않고 라운드를 종료하지만 꺼낸 숫자가 정렬이 완료된 모든 영역의 숫자보다 작다면 그 숫자가 가장 왼쪽에 도달할 때 까지 비교하고 교체한다.

구체적으로는 k라운드에서 k-1회 작업이 발생하게 된다. 따라서 최악의 경우 2라운드에서 1회, 3라운드에서 2회, n라운드에서 n-1회 교체가 발생하게 되므로 계산 시간은 버블,선택 정렬과 동일하게 O(n^2) 이다.

4. 힙 정렬(Heap Sort)

힙 데이터 구조를 사용한다.(힙은 내림차순이 되도록 구성한다.)

힙에 모든 데이터 숫자를 삽입한다. ( 내림차순 힙은 큰 값부터 데이터를 순서대로 꺼내는 성질이 있기 때문에 꺼낸 숫자를 역순으로 나열하면 정렬이 완료된다.)

힙 정렬 초기에 힙에 숫자를 삽입할 때 걸리는 시간은 O(nlogn)이다. 이는 빈 상태에서 하나씩 데이터를 추가하면 되는데 힙의 높이는 log2n 이하이므로 한개의 숫자를 추가하는데는 O(log n)의 시간이 소요되기 때문이다. → 한 개의 숫자당 걸리는 시간 (log n) * 데이터 개수 (n)

버블, 선택, 삽입 정렬에 비해 속도가 빠르지만, 힙이라는 복잡한 구조를 사용하기 때문에 구현이 복잡하다.

5. 병합 정렬(Merge sort)

정렬이 필요한 수열을 거의 같은 길이의 수열 2개로 분할한다. 더 이상 분할할 수 없게 되면 ( 즉, 각 그룹의 숫자가 1이되면) 그룹끼리 통합하기 시작한다. = 분할 정복 ( divide and conquer)
통합할 때는 정렬된 수열 두 개를 통합하여 하나로 정렬한다. 수열이 다시 하나가 될 때까지 이 과정을 반복한다.

• 숫자를 분할하는 작업의 계산시간은 고려하지 않는다.
• 두 수열을 병합하는 과정은 각 수열의 가장 앞 숫자를 비교하여 작은 숫자를 위로 옮기는 작업을 반복하기 때문에 두 수열의 길이에 비례한다. 따라서 하나의 층을 병합하는 계산 시간은 그 층에 있는 숫자의 수를 따른다.
• 어떤 층을 봐도 숫자는 n개 이므로 각 층의 계산시간은 O(n)이다. n개의 숫자가 하나가 될 때 까지 절반씩 분할해 나가면 log2n층이므로 전체 연산시간은 O(nlogn) 으로 힙 정렬과 동일하다.

  이해를 돕기 위한 설명
  1. 배열을 반으로 나누는 과정 (분할과정)
  a. 배열을 반씩 나누어 더 이상 나누어지지 않을 때 까지 분할한다.
  b. 예를 들어 데이터가 8인데 2개씩 계속 나누는 연산은 log2 8 을 의미한다.
  c. 따라서 배열을 나누는 단계는 log2 n 만큼 이루어지므로 시간 복잡도는 O(log n)이다.
  2. 두 부분의 배열을 병합하는 과정 (병합과정)
  두 개의 정렬 된 배열을 하나로 합칠 때, 각 배열의 전체 크기에 비례한다.
  맨 앞 숫자만 비교해서 더 작은 걸 위로 올리니까 각각의 길이에만 비례해서 n개라고 할 수있음
  3. 전체 연산 → 분할과정 * 병합과정 = O (nlogn)

6. 퀵 정렬 (Quick Sort)

기준이 되는 수 (=피봇(pivot))을 임의로 선택하고, 피봇 이외의 수를 ‘피봇보다 작은 수’ 와 ‘피봇보다 큰 수’ 두 그룹으로 나누고 [피봇보다 작은 수] < 피봇 < [피봇보다 큰 수] 의 순서로 배치한다. 이제 각 []의 안을 정렬하면 전체가 정렬된다.
(* [] 내부를 정렬할 때도 다시 퀵 정렬 방식을 사용한다.)

• 퀵 정렬은 재귀를 사용한 분할 정복법에 해당한다.
• 연산 시간은 병합 정렬과 마찬가지로 O(nlogn)에 해당한다.