• 레코드들을 키 값의 순서로 재배열하는것.

선택정렬

원소 가장 작은거 앞으로 보내는.

• 반복적으로 최소값을 찾아 정렬하는 방식

• 알고리즘 매우 간단. 효율 x 이며 안정성 x
  

삽입정렬

한큐에 쭉쭉감. 어디 사이에 넣을지 바로바로 고민후 삽입

• 알고리즘이 동작하는 동안 계속 정렬 진행.
• O(N^2) 이긴 하지만, 정렬되어있는 상태면 빠르게 동작.

버블 정렬

• 인접한 두개의 데이터를 비교
  

• 배열에서 모든 다른 요소들과 교환되어야함

• 제일 느리지만 단순.

머지 소트

• DP를 기반으로 한 정렬 알고리즘.
• O(nlogn)
• 효율적
• 안정적이며 데이터의 초기 분산 순서에 영향을 덜받음

퀵정렬

• 피벗 사용
• 분할정복법을 사용하며, 평균적으로 가장 빠름
• 하나의 리스트를 피벗을 기준으로 분할하고 정렬
• 1.분할 2. 정복 3.결합
• 최악 O(n^2), 최선 O(nlogn), 평균 O(nlogn)

python 간결한 퀵소트

array = [5, 7, 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))

계수 정렬(Count Sort)

데이터 크기 범위가 제한(백만 안팍) + 정수일때!

• 흔히 아는 0 배열로 개수 세기
• 시간복잡도는 O(N+K)

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=" ")

파이썬 sort key

길이별로 문자열 정렬

• 문자열 목록이 있고 길이별로 정렬하려면 'len' 함수를 키로 사용할 수 있습니다.

words = ["apple", "banana", "cherry", "date"]
words.sort(key=len)
# Result: ['date', 'apple', 'banana', 'cherry']

특정 요소별로 튜플 정렬

• 튜플의 요소 중 하나를 기준으로 정렬

tuples = [(1, 'apple'), (3, 'banana'), (2, 'cherry')]
tuples.sort(key=lambda x: x[0])  # Sort by first element
# Result: [(1, 'apple'), (2, 'cherry'), (3, 'banana')]

복잡한 기능을 사용한 정렬

• 문자열의 숫자를 숫자로 간주하는 방식으로 문자열을 정렬합니다.

data = ["item12", "item3", "item23", "item1"]
data.sort(key=lambda x: int(''.join(filter(str.isdigit, x))))
# Result: ['item1', 'item3', 'item12', 'item23']

대소문자를 구분하지 않는 문자열 정렬

names = ["alice", "Bob", "david", "Carol"]
names.sort(key=str.lower)
# Result: ['alice', 'Bob', 'Carol', 'david']

속성을 기준으로 개체 정렬

• 개체 목록이 있는 경우 개체의 속성을 기준으로 정렬할 수 있습니다.

class Fruit:
    def __init__(self, name, weight):
        self.name = name
        self.weight = weight

fruits = [Fruit("apple", 180), Fruit("banana", 150), Fruit("cherry", 10)]
fruits.sort(key=lambda fruit: fruit.weight)
# Result: sorted by weight