💡 Algorithm
Algorithm - [ 정렬 ]
date
Jun 21, 2023
slug
algorithm-02
author
status
Public
tags
Python
Algorithm
summary
연속된 데이터를 기준에 따라서 정렬하기 위한 알고리즘
type
Post
thumbnail
category
💡 Algorithm
updatedAt
Jul 28, 2023 07:04 AM
선택 정렬
매번 가장 작은 것을 선택해서 맨 앞의 데이터와 바꾸는 과정 반복
# 선택 정렬 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] print(array)
삽입 정렬
데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는 과정 반복
(데이터가 정렬되어 있을 때 효율적)
# 삽입 정렬 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] 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 print(array)
퀵 정렬
기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 과정 반복
(데이터가 무작위로 입력되는 경우 평균 시간 복잡도
# 퀵 정렬 (직관적인 코드) array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] def quick_sort(array, start, end): if start >= end: return 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[right], array[pivot] = array[pivot], array[right] else: array[left], array[right] = array[right], array[left] quick_sort(array, start, right - 1) quick_sort(array, right + 1, end) quick_sort(array, 0, len(array) - 1) print(array)
# 파이썬의 장점을 살린 퀵 정렬 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] def quick_sort(array): if len(array) <= 1: return array pivot = array[0] tail = array[1:] left_side = [x for x in tail if x <= pivot] right_side = [x for x in tail if x > pivot] return quick_sort(left_side) + [pivot] + quick_sort(right_side) print(quick_sort(array))
계수 정렬
일반적으로 모든 범위를 담을 수 있는 크기의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담음
(데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합)
# 계수 정렬 array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] count = [0] * (max(array) + 1) for i in range(len(array)): count[array[i]] += 1 for i in range(len(count)): for j in range(count[i]): print(i, end=' ')
(출처: 이것이 코딩 테스트다)