[algorithms] 비교 기반 정렬 알고리즘 (선택정렬, 삽입정렬, 퀵정렬)

(23.05.14)

정렬 알고리즘 정리!!

https://github.com/gompaang/algorithm_python

GitHub - gompaang/algorithm_python

---

 

selection sort : 선택 정렬

1. 가장 작은 수를 선택하여 맨 앞의 수와 자리를 바꾼다.

2. 그 다음으로 가장 작은 수를 선택하여 맨 앞에서 두번째 수와 자리를 바꾼다.

3. 위의 과정을 반복한다. 

 

def selection_sort(array):
  for i in range(len(array)):
    min_index = i
    for j in range(i+1, len(array)):
      if array[j] < array[min_index]:
        min_index = j
    array[i], array[min_index] = array[min_index], array[i]
  
  return array

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
print(selection_sort(array))

 

---

 

insertion sort : 삽입 정렬

1. 가장 앞의 원소는 정렬되어있다고 생각하여 앞에서 두번째 원소부터 시작한다.

2. 앞의 정렬된 원소들과 비교하여 적절한 자리에 삽입한다.

3. 그 다음 원소들도 같은 과정을 통해 적절한 자리에 삽입한다.

 

필요할 때에만 위치를 바꾸기 때문에 "데이터가 거의 정렬되어 있을 때" 효율적이다.

 

def insertion_sort(array):
  for i in range(1, len(array)):
    for j in range(i, 0, -1):
      if array[j] < array[j-1]:
        array[j], array[j-1] = array[j-1], array[j]
      else:
        break

  return array

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
print(insertion_sort(array))

 

 

 

 

---

 

Quick sort : 퀵 정렬

1. pivot을 정한다.

2. 왼쪽부터는 pivot 보다 큰 원소, 오른쪽부터는 pivot보다 작은 원소를 고른다.

3. 두 원소의 자리를 바꿔준다. 단, 두 원소가 엇갈릴 경우 pivot보다 작은 원소와 pivot을 바꾼다.

4. 위의 과정을 반복한다.

def quick_sort(array, start, end):
  if start >= end:
    return array
  
  pivot = start
  left = start + 1
  right = end

  while left <= right:
    while left <= end and array[left] <= array[pivot]:
      left += 1
    while right > start and array[right] >= array[pivot]:
      right -= 1
    
    if left > right:
      array[pivot], array[right] = array[right], array[pivot]
    else:
      array[left], array[right] = array[right], array[left]
    
  quick_sort(array, start, right-1)
  quick_sort(array, right+1, end)


array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
quick_sort(array, 0, len(array)-1)
print(array)

 

# quick sort (python)

def quick_sort_python(array):
    if len(array) <= 1:
        return array

    pivot = array[0]
    data = array[1:]

    left = [x for x in data if x <= pivot]
    right = [x for x in data if x > pivot]

    return quick_sort_python(left) + [pivot] + quick_sort_python(right)


array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
print(quick_sort_python(array))

 

quick sort는 데이터가 정렬되어 있고, pivot이 가장 왼쪽인 경우에 매우 느리다.

(insertion sort가 데이터가 정렬되어있을 때 빠르다는 것과는 반대인 것이다.)

 

 

 

선택정렬, 삽입정렬, 퀵정렬의 시간 복잡도 비교

 

 

 

 

 

 

 

참고자료: 이것이 코딩 테스트다 (나동빈)

https://github.com/ndb796/python-for-coding-test