정렬 - 이것이 코딩 테스트다

🦊 선택정렬

• 선택 정렬: for i 마다 나머지중에 제일 작은 걸 찾아서 맨 앞자리랑 바꾸기
• 시간 복잡도: O(N^2)

🦊 삽입정렬

• for i마다 i보다 앞에 있는 부분에서 정렬된 자리를 찾아 들어가는것
• 시간복잡도: O(N^2)이지만 만약 자료가 거의 정렬되어 있다면 O(N)에 수렴하는 시간복잡도를 갖음

🦊 퀵정렬

• 삽입정렬과 반대로 정렬이 되어있으면 되어있을수록 시간이 많이 걸림

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    if start >= end: # 원소가 1개인 경우 종료
        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 = [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))

🦊 계수 정렬

🦊 정렬 알고리즘 비교

from random import randint
import time

array = []
for _ in range(10000):
	array.append(randint(1, 100))

	start_time = time.time()

	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]

end_time = time.time()
print("선택 정렬 성능 측정:", end_time - start_time)

array = []
for _ in range(10000):
	array.append(randint(1, 100))

start_time = time.time()

array.sort()

end_time = time.time()
print("기본 정렬 라이브러리 성능 측정:", end_time - start_time)

이상하게 array를 100개만 입력하면 작동하는데 10000개하면 작동이 안됨