[자료구조] 6가지 Sort 알고리즘 완벽 총정리(코드, 시간복잡도, Stable sort, 서울대 기출)

1. Insertion sort

• $a_{k}$원소 이전의 $a_{k-1}$까지는 전부 정렬돼있음. $a_k$를 $a_0$~$a_{k-1}$까지의 올바른 자리에 삽입하기.

• 정렬되어 있는 배열에 나를 삽입하기.

• 수행시간

  • Best: O(n) → 완전 정렬돼있을 때. 각 원소마다 자기 하나 왼쪽의 원소랑이랑만 딱 한번 비교 수행. 이미 자기 왼쪽 배열의 최대(k-1)보다 자기가 큼으로 삽입이 일어나지 않음.
  • Worst: O($n^2$) → k번의 원소마다, k-1번의 삽입을 위한 비교가 일어남.

• 코드

  • target이 현재 값.
  • num[cur]가 num[i-1]부터 num[0]까지 내려가면서, target보다 큰 값이 없을 때까지 cur를 감소시킴.
    num[cur]가 target보다 작다면 루프 멈추고, num[cur+1]에 target값을 넣어준다.

  #define num 7
  int number[num]  = {4, 2, 1, 5, 3, 7, 6};
  for (int i = 1; i < num; i++) {
      int target = number[i];  // 기준
      int cur = i - 1;   // 비교할 대상
      while (cur >= 0 && target < number[cur]) {
          // 비교대상이 큰 경우 오른쪽으로 밀어냄
          number[cur + 1] = number[cur];   
          cur--;
      }
      number[cur + 1] = target;  // 기준값 저장
  }
  

2. Bubble sort

• 인접 값끼리 비교하며 정렬. i를 length-i-1까지 올리는 정렬
• 수행시간
  • Best case: O(n) - 모두 정렬되어 있는 경우
  • Worst case: O($n^2$) - 역순으로 정렬돼있는 경우

3. Selection sort

• $a_k$원소 이전의 $a_{k-1}$까지는 전부 정렬돼있음. $a_{k}$부터 $a_n$까지중의 최소값 $a_j$를 찾아준 다음에, $a_k$와 교환.
• 정렬되지 않은 애들에서 최소값 찾아서 정렬된 애의 최댓값으로 만들기.
• 수행시간
  • 모든 경우에 대해 O($n^2$) (왜냐면 비교하는 대상이 정렬되지 않았으니까)
• 코드

  def selection_sort(arr):
      n = len(arr)
      
      for k in range(n - 1):
          min_index = k
          for j in range(k + 1, n):
              if arr[j] < arr[min_index]:
                  min_index = j
  
          # a[k]와 a[min_index]를 교환
          arr[k], arr[min_index] = arr[min_index], arr[k]
  

4. Heap sort

• 순서

  1. 주어진 배열에서 Max heap 생성(최댓값이 root에 있게됨) ($O(N)$이라고함)
  2. root를 빼낸 다음 가장 leaf와 바꿈
  3. Heapify를 통해 다시 max heap의 형태로 바꿔줌(root를 자식들이랑 계속 비교= $O(logN)$)

• 수행시간

  • Best case: $O(N)$ - 이미 정렬돼있는 경우
  • Worst case: Heapify과정이 n개의 원소를 다 정렬할 때까지 반복됨으로 최종 힙정렬 시간복잡도: $O(NlogN)$

• 코드

  // i 노드가 가장 큰 노드인 힙트리를 만들기 위한 함수
  // 힙 사이즈는 n
  void heapify(int arr[], int n, int i)
  {
      int largest = i; // 루트를 가장 큰 노드로 초기 설정
      int l = 2 * i + 1; 
      int r = 2 * i + 2; 
  
      // l이 범위내 존재하는지 확인하고
      // 왼쪽 자식 노드가 가장 큰 노드보다 크다면
      // 가장 큰 노드가 왼쪽 자식 노드
      if (l < n && arr[l] > arr[largest])
          largest = l;
  
      if (r < n && arr[r] > arr[largest])
          largest = r;
  
      // 만약, 가장 큰 노드가 '루트'가 아니면 스왑
      if (largest != i) {
          swap(arr[i], arr[largest]);
  
  // 재귀적으로 heapify
          heapify(arr, n, largest);
      }
  }
  
  // 힙 정렬 함수
  void heapSort(int arr[], int n)
  {
      // maxheap을 우선 생성
      for (int i = n / 2 - 1; i >= 0; i--)
          heapify(arr, n, i);
  
      for (int i = n - 1; i > 0; i--) {
          // 루트노드를 끝 노드로 스왑
          swap(arr[0], arr[i]);
  
          // 줄어든 힙에서 maxheap 구성
          heapify(arr, i, 0);
      }
  }
  

5. Merge sort

Divide and Conquer

순서

• 1. return 조건: left ≥ right
  2. doMergeSort( left, mid )
  3. do mergeSort( mid+1, right )
  4. sorted 된 두 리스트를 aux에 병합
  5. 한 리스트의 모든 원소가 aux에 담겨있음. 나머지 리스트의 남은 원소들도 그대로 aux에 복사.
  6.  
  7.  수행시간
     • $O(NlogN)$ : 원소 생김새에 관계 x
• 공간복잡도
  • External sorting임으로(Internal sorting의 반대) $O(N)$의 공간복잡도 발생: 크기 N인 aux배열을 새로 생성해서 결과를 담아줘야함.
• 코드

def mergeSort(arr, l, r):
  if l < r:
  	m = (l+r)//2

  mergeSort(arr, l, m) # 왼쪽 반
  mergeSort(arr, m+1, r) # 오른쪽 반
  merge(arr, l, m, r)

6. Quick sort

• Divide and Conquer

• 순서

  1. 피봇값을 제일 왼쪽애로 설정
  2. 피봇보다 오른쪽 배열을 관찰. left에서부터 오른쪽으로 가면서 피봇보다 큰 값 m, right에서부터 왼쪽으로 가면서 피봇보다 작은 값 n을 찾는다.
  3. (a) m이 n보다 왼쪽에 있다면, m과 n을 스왑
     (b) m이 n보다 오른쪽에 있다면(제대로 돼있음), n과 피봇을 스왑. → 피봇기준으로 왼쪽은 모두 피봇보다 작음.(아직 정렬까지는 아님)
  4. 여기서 각 왼쪽, 오른쪽 집합에 대해서 반복해 줌.

• 순서

  1. return 조건: left ≥ right
  2. 피봇: a[left] 설정 후에, (partition함수를 통해) 피봇 왼쪽에는 피봇보다 작은 값들을, 피봇 오른쪽 에는 피봇보다 큰 값들을 둔다
  3. quickSort( left, p-1 )
  4. quickSort( p+1, right )

• 시간복잡도

  • Best: $O(N logN)$

    • pivot이 중앙값이 돼서 파티셔닝된 배열의 크기가 반으로 주는경우!!
    • (Partion 내부에서 비교횟수: N) x (순환깊이 $logN)$

  • 평균: $O(N logN)$

  • Worst: $O(N^2)$

    • 정렬되어있거나 역순으로 정렬되어 있을 때 뿐임
    • → 파티셔닝 이후에 피봇이 제일 앞이나 뒤로 이동하기 때문에, 파이셔닝된 배열의 크기가 (1, N-1)임.

• 코드

  void quickSort(){
      if (l < r){
          int p = partition(arr, l, r)
          quickSort(arr, l, p-1) 
          quickSort(arr, p+1, r)
      }
  }
  

Sort 추가내용:

Stable sort

• Stable sort

  • 정렬을 했을 때 중복된 값들의 순서가 변하지 않으면 안정(Stable) 정렬

  • Insertion sort, Merge sort, Bubble sort

In-place algorithm

• 추가적인 메모리 공간이 거의(아예가 아니다) 안 드는 정렬
• Insertion sort, selection sort, bubble sort, heap sort, quick sort
• 아닌 것: Merge sort

 

 

서울대학교 컴퓨터공학부 대학원 21년도 구술면접 기출문제

💡 insertion sort, quick sort, merge sort 3가지 알고리즘이 있을때, 아래의 상황에서 어떠한 알고리즘이 제일 좋은가?

1. 숫자가 다 다른 배열

• 평균복잡도 제일 낮은 Quick/Merge: O(nlogn)

2. 숫자가 다 같은 배열

• ↔ 이미 정렬돼있는상황
• Insertion sort: O(n)

3. 이미 정렬된 배열

• Insertion sort: O(n)

4.이미 정렬은 되었으나 역순으로 정렬된 배열

• • Merge sort: O(nlogn)
  • 주의) Quick sort는 $O(n^2)$임