전공과목 정리/자료구조

[자료구조💾] 8장 정렬

최연재 2024. 1. 21. 09:02

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스)

 

8.1 정렬의 종류

1) 정렬

- 주어진 원소(레코드)들을 원하는 기준에 의해 나열하는 작업

- 내부 정렬(internal sort) : 정렬 작업을 주 메모리에서 처리한다.

- 외부 정렬(external sort) :  정렬 작업을 외부 기억장치에서 처리한다.

 

2) 외부 정렬

- 정렬한 원소 개수가 메모리 개수보다 큰 경우 수행한다.

- 정렬 과정 (전체 원소의 수 : n, 메모리의 크기 : m)

  1. n개의 원소를 m으로 나누어 n/m개의 세그먼트로 분할한다.
  2. 각 세그먼트를 주 메모리에 로드하여 내부 정렬 알고리즘으로 정렬한 후 다시언래의 하드 디스크 위치에 저장한다.
  3. 정렬된 2개의 세그먼트 쌍에 대해서 합병 정렬을 수행한다.
  4. 하나의 정렬된 세그먼트가 생성될 때까지 3번 과정을 반복한다.

 

 

8.2 선택 정렬 (selection sort)

1) 선택 정렬

- 정렬할 원소 집합에서 최솟값(또는 최댓값)을 탐색하여 정렬 리스트로 이동시키고 정렬 대상에서 제외한다.

- 남은 원소들에 대해 위의 과정을 반복하여 순서대로 최솟값(또는 최댓값)을 탐색하여 정렬을 수행한다.

- 시간 복잡도 : O(n2)

- 알고리즘

for 정렬 대상 집합에 원소가 남아있는 경우:
    집합에서 최댓값/최솟값 원소를 탐색한다.
    기준 수와 탐색한 최댓값/최솟값 원소를 교환한다.
    교환된 원소를 정렬 대상 집합에서 제외한다.

 

2) 최솟값 우선 선택 정렬 코드

class SelectionSort:
  def __init__(self, num):
    self.num = num
    self.size = len(num)
    print("Selection Sort", self.num)

  def __str__(self):
    for i in range(self.size):
      print("%2d " %self.num[i])

  def swap(self, a, b):
    self.num[a], self.num[b] = self.num[b], self.num[a]

  def sort(self):
    n = self.size
    for i in range(i+1, n):
      min = i
      for j in range(i+1, n):
        if self.num[j] < self.num[i]:
          min = j
      self.swap(i, min)
      print(self.num)

 

 

8.3 버블 정렬 (bubble sort)

1) 버블 정렬

- 리스트 왼쪽부터 인접한 원소들을 비교하여 큰 값을 오른쪽으로 이동시키는 정렬 방법

- 오른쪽으로 이동한 최댓값은 정렬 과정에서 제외하고 남은 원소들에 대해 위 과정을 반복한다.

- 시간 복잡도 : O(n2)

- 알고리즘

  1. 리스트 왼쪽의 인접한 두 수를 비교하여 오름차순으로 정렬되도록 구현한다.
  2. 오른쪽으로 1칸을 이동하여 같은 방식으로 두 수를 정렬하고 리스트 오른쪽 끝에 도달할 때까지위과정을 반복한다.
  3. 최댓값이 오른쪽 끝에도달하면 이 원소를 제거하고,원소가 한 개 남을 때까지 남은 원소들에 대해 1번 과정부터 반복한다.

 

2) 버블 정렬 코드

class BubbleSort:
  def __init__(self, num):
    self.num = num
    self.size = len(num)
    print("Bubble Sort", self.num)

  def __str__(self):
    for i in range(self.size):
      print("%2d " %self.num[i])

  def swap(self, a, b):
    self.num[a], self.num[b] = self.num[b], self.num[a]

  def sort(self):
    n = self.size
    for i in range(n-1):
      flag = 0  # 교환이 없음.
      for j in range(0, n-1-j):
        if self.num[j] > self.num[j+1]:
          self.swap(j, j+1)
          flag = 1
      if flag == 0:
        break
      print(self.num)

 

 

8.4 삽입 정렬 (insertion sort)

1) 삽입 정렬

- 정렬된 리스트에 새로운 원소를 추가하는 작업

- 정렬 대상에서 가장 왼쪽 원소 1개를 이미 정렬된 리스트로 사용한다.

- 정렬 리스트의 바로 옆 원소를 왼쪽으로 이동시켜 올바른 위치에 삽입한다.

- 모든 원소가 추가될 때까지 위 과정을 반복한다.

- 알고리즘

  1. 주어진 리스트에서 첫 번째 항목을 이미 정렬이 완료된 리스트이다.
  2. 정렬 리스트의 바로 오른쪽 원소가 정렬된 위치를 찾을 때까지 왼쪽으로 이동시킨다.
  3. 정렬되지 않은 원소가 없을 때까지 2번 과정을 반복한다.

 

2) 삽입 정렬 코드

class InsertionSort:
  def __init__(self, num):
    self.num = num
    self.size = len(num)
    print("Insertion Sort", self.num)

  def __str__(self):
    for i in range(self.size):
      print("%2d " %self.num[i])

  def swap(self, a, b):
    self.num[a], self.num[b] = self.num[b], self.num[a]

  def sort(self):
    for i in range(i, self.size):
      pivot = self.num[i]
      j = i-1
      while j >= 0 and pivot < self.num[j]:
        self.num[j+1] = self.num[j]
        j -= 1
      self.num[j+1] = pivot
      print(self.num)

 

 

8.5 쉘 정렬 (Shell sort)

1) 쉘 정렬

- 삽입 정렬의 기능을 개선하기 위한 알고리즘으로 1959년 도널드 쉘(Donald Shell)에 의해서 개발되었다.

  • 삽입 정렬에서는 인접한 원소드를 비교하기 때문에 작은 수가 리스트의 뒤쪽에 있을 때 정렬 위치를 찾을 때까지 비교 횟수가 많아진다.
  • 떨어져 있는 원소들 간에 삽입 정렬을 수행하여 정렬 속도를 개선한다.

- 평균적인 시간 복잡도 : O(n3/2)

- 알고리즘

  1. 정렬할 원소의 수가 n개일 때, 비교할 원소 간의 거리를 gap이라고 정의한다.
  2. gap이 홀수가 되도록 n/2 혹은 (n/2)+1로 계산한다.
  3. gap만큼 떨어져 있는 원소들간에 삽입정렬을 수행한다.
  4. gap이 1보다 크다면 2번 과정부터 반복하고 gap이 1이 되면 종료한다.

- 쉘 정렬은 각 단계 수행 후 a[i] < a[i+gap]이 성립한다.

 

2) 쉘 정렬 코드

class ShellSort:
  def __init__(self, num):
    self.num = num
    self.size = len(num)
    print("Shell Sort", self.num)

  def __str__(self):
    for i in range(self.size):
      print("%2d " %self.num[i])

  def swap(self, a, b):
    self.num[a], self.num[b] = self.num[b], self.num[a]

  def sort(self):
    global prev
    n = self.size
    gap = n//2

    while gap > 0:
      if gap % 2 == 0:
        gap += 1
      for i in range(gap, gap*2):
        h = 0
        while i+gap*h < n:
          j = i + gap*h
          temp = self.num[j]
          while j >= gap:
            if temp < self.num[j-gap]:
              self.num[j] = self.num[j-gap]
            else:
              break
            j -= gap
          self.num[j] = temp
          h += 1
          if self.num != prev:
            print(gap, self.num)
      gap //= 2
      print()

 

 

8.6 퀵 정렬 (quick sort)

1) 퀵 정렬

- 기준 수(x)를선택하여 정렬한 원소들을 x값보다 작은 세그먼트와 큰 세그먼트로 분할하는 방식으로 정렬을 수행한다.

- 분할이 완료되면 x는 두 세그먼트 사이로 이동한다.

- 양쪽의 각 세그먼트는 재귀적으로 퀵 정렬을 적용하여 전체 정렬을 완료하다.

- 퀵 정렬 알고리즘

  1. 리스트의 가장 왼쪽 원소를 기준 수(x)로 지정하여 x보다 작은 세그먼트와 큰 세그먼트로 리스트를 분할한다. 더 이상 분할이 일어나지 않으면 종료한다.
  2. x는 분할된 두 세그먼트 사이로 옮긴다.
  3. 각 세그먼트를 퀵 정렬 알고리즘으로 정렬한다.

- 퀵 정렬의 리스트 분할 알고리즘

  1. 기준수(x)는 리스트의가장왼쪽 수로 정하고, x의 오른쪽 옆을 i로, 리스트의 가장 오른쪽 끝을 j로 지정한다.
  2. x보다 큰 값을 찾을 때까지 i를 오른쪽으로 이동시키고, x보다 작은 값을 찾을 때까지 j를 왼쪽으로 이동시킨다.
  3. 과정 2를 수행 후
    1. i < j 일 경우 : i와 j 위치의 원소를 교환한 후 과정 2번을 반복한다.
    2. i ≥ j 일 경우 : 분할이완료되었으므로 기준수(x)와 j 위치 원소를 교환 후 종료한다.

 

2) 퀵 정렬 코드

class QuickSort:
  def __init__(self, num):
    self.num = num
    self.size = len(num)
    print("Quick Sort", self.num)

  def __str__(self):
    for i in range(self.size):
      print("%2d " %self.num[i])

  def swap(self, a, b):
    self.num[a], self.num[b] = self.num[b], self.num[a]

  def sort(self, left, right):
    if left < right:
      i = left
      j = right + 1

      pivot = self.num[left]
      while True:
        while True:
          i += 1
          if i > right or self.num[i] >= pivot:
            break
        while True:
          j -= 1
          if j < left or self.num[j]<=pivot:
            break

        if i < j:
          self.swap(i, j)
          print(self.num)
        else:
          break
      self.swap(left, j)
      if left != j :
        print(self.num)
      self.sort(left, j-1)
      self.sort(j+1,right)

 

 

8.7 합병 정렬 (merge sort)

1) 합병 정렬

- 정렬된 리스트들을 하나로 합치는 합병(merge) 작업을 활용하는 알고리즘

- 정렬된 두 개의 서브 리스트를 하나로 합친다.

- 최솟값 원소끼리 비교하여 더작은 값을 먼저 정렬 리스트로 이동하는 작업을 반복한다. 

- 알고리즘

  1. 리스트를 반으로 나눠 2개의세그먼트트리로 분할한다.
  2. 분할된 각 세그먼트를 합병 정렬 알고리즘으로 정렬한다.
  3. 정렬된 두세그먼트를 합병(merge)하여 정렬을 완료한다.

 

2) 합병 정렬 코드

class MergeSort:
  def __init__(self, num):
    self.num = num
    self.size = len(num)
    print("Merge Sort", self.num)

  def __str__(self):
    for i in range(self.size):
      print("%2d " %self.num[i])

  def swap(self, a, b):
    self.num[a], self.num[b] = self.num[b], self.num[a]

  def mergesort(self, left, right):
    if right > left:
      mid = (right + left) // 2
      self.mergesort(left, mid)
      self.mergesort(mid+1, right)
      self.merge(left,mid+1, right)
      print(self.num)

  def merge(self, left, mid, right):
    pos = left
    left_end = mid - 1
    n = right - left + 1
    temp = [None] * self.size
    while left <= left_end and mid <=right:
      if self.num[left] <= self.num[mid]:
        temp[pos] = self.num[left]
        pos += 1
        left += 1
      else:
        temp[pos] = self.num[mid]
        pos += 1
        mid += 1
    while left <= left_end:
      temp[pos] = self.num[left]
      left += 1
      pos += 1
    while mid <= right:
      temp[pos] = self.num[mid]
      mid += 1
      pos += 1
    for i in range(n):
      self.num[right] = temp[right]
      right -= 1

'전공과목 정리 > 자료구조' 카테고리의 다른 글

[자료구조💾] 10장 최단 경로와 작업 네트워크  (0) 2024.01.24
[자료구조💾] 9장 그래프  (2) 2024.01.23
[자료구조💾] 7장 최대 힙  (0) 2024.01.20
[자료구조💾] 6장 이진 트리  (0) 2024.01.18
[자료구조💾] 5장 연결 리스트  (0) 2024.01.17

'전공과목 정리/자료구조'의 다른글

  • 현재글[자료구조💾] 8장 정렬

관련글

티스토리툴바